我在下面给出的列表 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]]]
如果 list1 中的所有点都被旋转和/或平移，则点 a、b、c 和 d 分别与点 v、x、y 和 z 对齐。目前我已经编写了 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']]