确定全等点的组

Question

我在下面给出的列表列表1和列表2中有两组点

list1 = [['a',[1.2,3.6,4.5]],['b',[3.2,-5.4,6.6]],['c',[1.1,2.2,9.9]],['d',[5.5,12.5,2.9]],['e',[3.5,6.5,22.9]]]
list2 = [['v',[11.2,3.6,4.5]],['x',[13.2,-5.4,6.6]],['y',[11.1,2.2,9.9]],['z',[15.5,12.5,2.9]]]

如果列表1中的所有点都已旋转和/或平移，则点a、b、c和d分别与点v、x、y和z对齐。目前，我已经编写了Python代码，可以使用成对距离比较方法输出两个输入列表提供的成对组。它计算列表1和列表2内的列表内组合距离，并比较列表之间的这些距离，以识别对。例如，距离（ab）~=距离（vx）、距离（ac）~=距离（vy）等等。代码如下所示。我的代码可以工作，但对于较大的列表来说速度较慢。我想知道是否有更快或更简单的方法来解决这个问题

谢谢

def calculate_distance(point1,point2):
        #function calculates distance
        dis = 0
        dis += math.pow((point2[0]-point1[0]),2)
        dis += math.pow((point2[1]-point1[1]),2)
        dis += math.pow((point2[2]-point1[2]),2)
        distance = math.sqrt(dis)
        return distance

def make_masterdict(list1,list2):
        # calculate interalist combinitorial pairs of points with
        # their distances and store into dicts
        list1pairs = {}
        list2pairs = {}
        for i in range(len(list1)):
                p1 = list1[i][1]
                for p2 in list1[i:]:
                    if list1[i][0] != p2[0]:
                        dist = calculate_distance(p1,p2[1])
                        #store both the pairs in the dictionary
                        list1pairs.update({list1[i][0]+'_'+p2[0]:dist})
                        list1pairs.update({p2[0]+'_'+list1[i][0]:dist})


        for i in range(len(list2)):
                p1 = list2[i][1]
                for p2 in list2[i:]:
                    if list2[i][0] != p2[0]:
                        dist = calculate_distance(p1,p2[1])
                        list2pairs.update({list2[i][0]+'_'+p2[0]:dist})
                        list2pairs.update({p2[0]+'_'+list2[i][0]:dist})

        # calculate interlist pairs between list1 and list2
        masterlist = []
        for i in list1:
                for j in list2:
                        masterlist.append([i[0],j[0]])

        masterdict = {}
        # for each combinatorial pair in masterlist
        for i in range(len(masterlist)-1):
                c1 = masterlist[i]
                key1 = c1[0]+'_'+c1[1]
                masterdict.update({key1:[]})
                for j in range(i+1,len(masterlist)):
                        c2 = masterlist[j]
                        # if the same point is not repeated in the pairs
                        if c1[0] != c2[0] and c1[1] != c2[1]:
                                #collect and compare the distances
                                p1 = c1[0]+'_'+c2[0]
                                p2 = c1[1]+'_'+c2[1]
                                dis1 = list1pairs[p1]
                                dis2 = list2pairs[p2]
                                if abs(dis1-dis2) < 0.1:
                                        #if same distance, then store in masterdict
                                        key2 = c2[0]+'_'+c2[1]
                                        masterdict[key1].append(key2)
        return masterdict                               

def recursive_finder(p1,list1,masterdict,d,ans):
        # if lenght of d is more than 2, store that list in ans
        if len(d) > 2:
                ans.append(d)

        # if lenght of list is 0, do not do anything
        if len(list1) == 0:
                pass
        else:
                other = []
                nextlist = []
                #loop through each value in list1 as p1
                for i in list1:
                        if i in masterdict[p1]:
                                #make empty list
                                newl = []
                                #store old group in newl
                                newl.extend(d)
                                #add new member to old group
                                newl.append(i)
                                #store this list
                                other.append(newl)
                                #store new member
                                nextlist.append(i)
                #repeat for each successful value in nextlist                
                for i in range(len(nextlist)):
                        #collect p1 and dnew 
                        p1 = nextlist[i]
                        dnew = other[i]
                        #repeat process
                        recursive_finder(p1,nextlist[i+1:],masterdict,dnew,ans)

def find_groups(list1,list2):
        #make master dictionary from input lists
        masterdict = make_masterdict(list1,list2)
        ans = []
        #use recursive function to identify groups
        for mainkey in masterdict:
                if len(masterdict[mainkey]) > 1:
                        for i in range(len(masterdict[mainkey])):
                                p1 = masterdict[mainkey][i]
                                recursive_finder(p1,masterdict[mainkey][i+1:],masterdict,[mainkey,p1],ans)

        return ans

#define two lists with a,b,c and d matching v,x,y, and z respectively
list1 = [['a',[1.2,3.6,4.5]],['b',[3.2,-5.4,6.6]],['c',[1.1,2.2,9.9]],['d',[5.5,12.5,2.9]],['e',[3.5,6.5,22.9]]]
list2 = [['v',[11.2,3.6,4.5]],['x',[13.2,-5.4,6.6]],['y',[11.1,2.2,9.9]],['z',[15.5,12.5,2.9]]]
answer = find_groups(list1,list2)
print(answer) 

运行代码后，将输出正确答案。输出大于3的组

[['a_v', 'b_x', 'c_y'], ['a_v', 'b_x', 'c_y', 'd_z'], ['a_v', 'b_x', 'd_z'], ['a_v', 'c_y', 'd_z'], ['b_x', 'c_y', 'd_z']]