I have two sets of points in lists list1 and list2 given below
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]]]
If all the points in list1 are rotated and/or translated, points a
, b
, c
and d
align with points v
, x
, y
and z
respectively. Currently I have written Python code that can output the groups of pairs provided two input lists using a pairwise distance comparison method. It computes intra-list combinatorial distances within list1
and list2
and compares these distances between the lists to identify the pairs. For e.g. distance(ab) ~= distance(vx), distance(ac) ~= distance(vy)
and so on. The code is given below. My code works but is slow for larger lists. I would like to know if there is any faster or easier way to solve this problem.
Thanks
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)
Upon running the code, the correct answer is output. Groups larger than size of 3 are output.
[['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']]