1）我将通过标记所有点并从每个集合中找到3个点的所有可能组合来解决此问题。
# normalize B data to same format as Aset_Bx, set_By = (set_B)set_B = []for i in range(len(set_Bx)): set_B.append([set_Bx[i],set_By[i]])'''set_B = [[2689.28, 2061.19], [3507.04, 3700.27], [2895.67, 2131.2], [1051.3, 1837.3], [1929.49, 2017.52], [1035.97, 80.96], [752.44, 3524.61], [130.62, 3821.22], [620.06, 3711.53], [2769.06, 1812.12], [1580.77, 1868.33], [281.76, 3865.77], [224.54, 3273.77], [3848.3, 2100.71]]'''list(itertools.combinations(range(len(set_A)), 3))list(itertools.combinations(range(len(set_B)), 3))
如何在Python中生成列表的所有排列
2）对于每个3点组，计算相应三角形的边；对A组和B组重复此过程。
dist = sqrt( (x2 - x1)**2 + (y2 - y1)**2 )
如何找到两点之间的距离？
3）然后减小每个边的比例，以使每个三角形的最小边等于1；另一侧的比例降低。
在两个相似的三角形中：
两个三角形的周长与边的比例相同。相应的边，中位数和高度都将以相同的比例变化。
http://www.mathopenref.com/similartrianglesparts.html
4）最后，对于每个来自A组的三角形，将其与来自B组的每个三角形进行比较，并逐个元素相减。然后将所得元素求和，并从A和B中找到总和最小的三角形。
list(numpy.array(list1)-numpy.array(list2))
5）给出匹配的三角形；就CPU / RAM而言，找到合适的缩放，平移和旋转应该相对简单。
ETA1：草稿脚本
ETA2：注释中讨论的修补错误：使用sum（abs（））而不是abs（sum（））。现在就可以了，速度也很快！
'''known correct solutionA = [[1894.41, 1957.065],[1967.31, 1960.865],[2015.81, 1981.665]]B = [[1051.3, 1837.3],[1580.77, 1868.33],[1929.49, 2017.52]]'''import numpy as npimport itertoolsimport mathimport operatorset_A = [[2015.81, 1981.665], [1967.31, 1960.865], [1962.91, 1951.365], [1964.91, 1994.565], [1894.41, 1957.065]]set_B = [[2689.28, 3507.04, 2895.67, 1051.3, 1929.49, 1035.97, 752.44, 130.62, 620.06, 2769.06, 1580.77, 281.76, 224.54, 3848.3], [2061.19, 3700.27, 2131.2, 1837.3, 2017.52, 80.96, 3524.61, 3821.22, 3711.53, 1812.12, 1868.33, 3865.77, 3273.77, 2100.71]]# normalize set B data to set A formatset_Bx, set_By = (set_B)set_B = []for i in range(len(set_Bx)): set_B.append([set_Bx[i],set_By[i]])'''set_B = [[2689.28, 2061.19], [3507.04, 3700.27], [2895.67, 2131.2], [1051.3, 1837.3], [1929.49, 2017.52], [1035.97, 80.96], [752.44, 3524.61], [130.62, 3821.22], [620.06, 3711.53], [2769.06, 1812.12], [1580.77, 1868.33], [281.76, 3865.77], [224.54, 3273.77], [3848.3, 2100.71]]'''print set_Aprint set_Bprint len(set_A)print len(set_B)set_A_tri = list(itertools.combinations(range(len(set_A)), 3))set_B_tri = list(itertools.combinations(range(len(set_B)), 3))print set_A_triprint set_B_triprint len(set_A_tri)print len(set_B_tri)'''set_A = [[2015.81, 1981.665], [1967.31, 1960.865], [1962.91, 1951.365], [1964.91, 1994.565], [1894.41, 1957.065]]set_A_tri = [(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]'''def distance(x1,y1,x2,y2): return math.sqrt((x2 - x1)**2 + (y2 - y1)**2 )def tri_sides(set_x, set_x_tri): triangles = [] for i in range(len(set_x_tri)): point1 = set_x_tri[i][0] point2 = set_x_tri[i][1] point3 = set_x_tri[i][2] point1x, point1y = set_x[point1][0], set_x[point1][1] point2x, point2y = set_x[point2][0], set_x[point2][1] point3x, point3y = set_x[point3][0], set_x[point3][1] len1 = distance(point1x,point1y,point2x,point2y) len2 = distance(point1x,point1y,point3x,point3y) len3 = distance(point2x,point2y,point3x,point3y) min_side = min(len1,len2,len3) len1/=min_side len2/=min_side len3/=min_side t=[len1,len2,len3] t.sort() triangles.append(t) return trianglesA_triangles = tri_sides(set_A, set_A_tri)B_triangles = tri_sides(set_B, set_B_tri)print A_triangles'''[[1.0, 5.0405616860744304, 5.822935502560814], [1.0, 1.5542012854321234, 1.5619803879976761], [1.0, 1.3832883678507584, 2.347214708755337], [1.0, 1.2141910838179129, 1.4096730529373076], [1.0, 1.1275138587537166, 2.0318412465223665], [1.0, 1.5207417600732074, 2.3589630093994876], [1.0, 3.2270326342163584, 4.13069930678442], [1.0, 6.565440477766354, 6.972550347780966], [1.0, 2.1606693015281997, 2.3635387983160885], [1.0, 1.589425903498476, 1.846471085870448]]'''print B_trianglesdef list_subtract(list1,list2): return np.absolute(np.array(list1)-np.array(list2))sums = []threshold = 1for i in range(len(A_triangles)): for j in range(len(B_triangles)): k = sum(list_subtract(A_triangles[i], B_triangles[j])) if k < threshold: sums.append([i,j,k])# sort by smallest sumsums = sorted(sums, key=operator.itemgetter(2))print sumsprint 'winner %s' % sums[0]print sums[0][0]print sums[0][1]match_A = set_A_tri[sums[0][0]]match_B = set_B_tri[sums[0][1]]print 'triangle A %s matches triangle B %s' % (match_A, match_B)match_A_pts = []match_B_pts = []for i in range(3): match_A_pts.append(set_A[match_A[i]]) match_B_pts.append(set_B[match_B[i]])print 'triangle A has points %s' % match_A_ptsprint 'triangle B has points %s' % match_B_pts'''winner [2, 204, 0.031415474959738399]2204triangle A (0, 1, 4) matches triangle B (3, 4, 10)triangle A has points [[2015.81, 1981.665], [1967.31, 1960.865], [1894.41, 1957.065]]triangle B has points [[1051.3, 1837.3], [1929.49, 2017.52], [1580.77, 1868.33]]'''
