Определить группы конгруэнтных точек

Question

У меня есть два набора точек в списках list1 и list2, приведенных ниже

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, х, у и г соответственно. В настоящее время я написал код на Python, который может выводить группы пар при условии двух входных списков, используя метод сравнения парных расстояний. Он вычисляет комбинаторные расстояния интралистов в списках list1 и list2 и сравнивает эти расстояния между списками для определения пар. Например,расстояние (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']]