identify groups of congruent points

Question

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']]

Answer 1

Calculate Distance

To check the distance between points, you can zip together two points to get corresponding coordinates. Every point is denoted by X, Y, Z, so zip(point1, point2) will give you pairs (X1, X2), (Y1, Y2), (Z1, Z2). Furthermore, you can use sum to get the total of any iterable, rather than hard-coding indices. Applying this to your distance function:

import math

def calculate_distance(p1, p2):
    """
    Takes the euclidean distance between two points. They are assumed
    to be of equal length:

        p1 = [a1, a2, ..., an]
        p2 = [b1, b2, ..., bn]

    Where n is any integer
    """
    sq_dist = sum((a - b)**2 for a, b in zip(p1, p2))
    return math.sqrt(sq_dist)

This allows you to handle any point, and cleanly pairs up corresponding points.

Generating Combinations of Distances

There's no need to re-create a combinatorics function, one exists for you in itertools.combinations. They also include a sample recipe if you want to try it on your own, but theirs is great. It has the added benefit that you don't store the combinations in memory by default, that's totally up to you.

It looks like you are trying to find pairs of points across both lists that share the same distance. You have lots of nested loops here, so let's look at it one step at a time. A dict is a great way to group these points together, with the keys being distance and the values being the pairs of points.

To keep track of where sets of points come from, we can return separate dictionaries for fast membership testing:

def combine(l1, l2):
    """
    Create your master dictionary by using the dict
    constructor on the list of key: value pairs (key is str, val is list)
    """
    d = dict(l1)
    d2 = dict(l2)

    return d, d2

Ok, using itertools to generate pairs, you want to group based on the euclidean distance between points. Let's do that. We will use a defaultdict of set to hold our list of names based on a distance key. The set will make sure that the names pairs are unique:

from collections import defaultdict
from itertools import combinations


def get_pairs(d1, d2):
    """
    p1 and p2 are dictionaries of points
    we will construct a defaultdict that will take the combinations
    of points and construct the euclidean distance as our key, and a set of
    names as the values
    """
    groups = defaultdict(set)

    # unpack the names and the points using dict.items()
    pairs_dict = {**d1,**d2}
    for (name1, p1), (name2, p2) in combinations(pairs_dict.items(), 2):
        check_1 = name1 in d1 and name2 in d1
        check_2 = name1 in d2 and name2 in d2
        if check_1 or check_2:
            # skip since they lie in the same dictionary
            continue
        dist = calculate_distance(p1, p2)

        for k in groups:
            # this will give you that tolerance you are looking for
            if math.isclose(dist, k, rel_tol=0.1):
                groups[k].add((name1, name2))
        groups[dist].add((name1, name2))

    return groups

Why do it this way? Well, you avoid most of your nested loops, and you are returned pairs of names based on the distances. The reason I say most is that you want to check against existing distances in your group dictionary to pair up approximately equal distances. Then you are grouping not only by exact distance, but also by approximate distance. Now, as the dictionary grows, this will be an O(N) operation, and you aren't necessarily going to avoid that. Add that to an O(M) loop, where M is the number of combinations, and N*M can get quite big, but comparing to your recursive function:

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
 # can't get this to line up, indentation should be the same                     
 recursive_finder(p1,nextlist[i+1:],masterdict,dnew,ans)

You have a recursive function containing an O(N) loop inside another O(N) loop, so the O(M*N) is no worse than the existing code. Furthermore, while this may look like I'm modifying a dict while iterating over it, I'm really not. The state of the keys is constant while I iterate the keys, and I only inject a key after the loop. Your outer build_master_dict function, however, does modify a dict while iterating over the keys, since the recursive function is nested inside that loop.

This makes it really easy to look them up from your master dictionary:

# assume list1 and list2 are the same and in the namespace already
import math
import json # for formatting
from collections import defaultdict

d1, d2 = combine(list1, list2)

groups = get_pairs(d1, d2)

# to look up your points
points = groups[5.579426493825329]

for p1, p2 in points:
    print(d[p1], d[p2])
[1.2, 3.6, 4.5] [1.1, 2.2, 9.9]
[11.2, 3.6, 4.5] [11.1, 2.2, 9.9]

Or, to show in a more succinct way:

for dist, points in groups.items():
    print(dist)
    for p1, p2 in points:
        print(p1, d[p1], p2, d[p2])

9.455686120002081
a [1.2, 3.6, 4.5] b [3.2, -5.4, 6.6]
v [11.2, 3.6, 4.5] x [13.2, -5.4, 6.6]
5.579426493825329
a [1.2, 3.6, 4.5] c [1.1, 2.2, 9.9]
v [11.2, 3.6, 4.5] y [11.1, 2.2, 9.9]
...

It's now easy to filter groups by len as well:

res = dict(filter(lambda x: len(x[1]) >= 3, groups.items()))

{10.0: {('c', 'y'), ('a', 'v'), ('b', 'x'), ('d', 'z'), ('d', 'v')}, 15.146286673637205: {('e', 'y'), ('c', 'x'), ('a', 'x'), ('d', 'y')}, 11.363538181394032: {('b', 'v'), ('b', 'y'), ('a', 'y'), ('c', 'v'), ('d', 'v')}, 12.223338332877807: {('c', 'v'), ('b', 'v'), ('b', 'y')}, 11.448143954370945: {('c', 'v'), ('d', 'v'), ('b', 'y')}, 22.03156826011258: {('e', 'z'), ('e', 'v'), ('e', 'x'), ('d', 'x'), ('b', 'z')}, 14.664924138910505: {('e', 'y'), ('c', 'x'), ('d', 'y')}, 19.03811965504997: {('e', 'v'), ('d', 'x'), ('c', 'z')}}

And to get your values:

res = list(map(list, dict(filter(lambda x: len(x[1]) >= 3, groups.items())).values()))

[[('c', 'y'), ('a', 'v'), ('b', 'x'), ('d', 'z'), ('d', 'v')], 
 [('e', 'y'), ('c', 'x'), ('a', 'x'), ('d', 'y')], 
 [('b', 'v'), ('b', 'y'), ('a', 'y'), ('c', 'v'), ('d', 'v')], 
 [('c', 'v'), ('b', 'v'), ('b', 'y')],  
 [('c', 'v'), ('d', 'v'), ('b', 'y')], 
 [('e', 'z'), ('e', 'v'), ('e', 'x'), ('d', 'x'), ('b', 'z')], 
 [('e', 'y'), ('c', 'x'), ('d', 'y')], [('e', 'v'), ('d', 'x'), ('c', 'z')]]

# to format your keys:
pairs = [['_'.join(x) for x in sub] for sub in res]

[['c_y', 'a_v', 'b_x', 'd_z', 'd_v'], 
 ['e_y', 'c_x', 'a_x', 'd_y'], 
 ['b_v', 'b_y', 'a_y', 'c_v', 'd_v'], 
 ['c_v', 'b_v', 'b_y'], 
 ['c_v', 'd_v', 'b_y'], 
 ['e_z', 'e_v', 'e_x', 'd_x', 'b_z'], 
 ['e_y', 'c_x', 'd_y'], 
 ['e_v', 'd_x', 'c_z']]
```

Answer 2

Sum generator

    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)

can be

    dis = sum((p2 - p1)**2 for p1, p2 in zip(point1, point2))

Type hints

PEP484 type hints will help the static analysis and readability of your code. For example,

def calculate_distance(point1: Sequence[float], point2: Sequence[float]) -> float:

Variable naming

Never call anything list1 or list2. What do the lists actually contain? What are they for? Are they full of license plates? Death certificates? Deeds to property on the moon?

Typo

interalist = intra-list.

Point tuples

From what I can tell, many of your sequences are actually three-dimensional points. There are easier or at least more legible ways to represent this, perhaps as a namedtuple:

from collections import namedtuple

Point = namedtuple('Point', ('x', 'y', 'z'))
# ...
list1 = [['a', Point(1.2,3.6,4.5)] ...

f-strings

p2[0]+'_'+list1[i][0]

can be

f'{p2[0]}_{list1[i][0]}'

or, if you use named tuples - and assuming that this is a Point -

f'{p2.x}_{list1[i].x}'

Loop like a native

    for i in range(len(list1)):
            p1 = list1[i][1]

can become

for item1 in list1:
    p1 = item1[1]

In other words, don't use C-style indexing when you can just iterate over the items in an iterable.

Use isclose

if abs(dis1-dis2) < 0.1:

is better represented with a call to isclose.

Null conditions

Don't do this:

    if len(list1) == 0:
            pass
    else:

Just write

if len(list1) != 0:
    # ...

List creation

This:

   #make empty list
   newl = []
   #store old group in newl
   newl.extend(d)

should simply be

new1 = list(d)

Answer 3

Indentation

Use four (4) spaces for indentation, not eight (8).

Checking List Existence

This

if len(list1) == 0:
    pass
else:

should be this (Thanks to @Reinderien for pointing this out)

if list1:
    ...

Parameter Spacing

There should be spaces between parameters and the commas. For example, from this

def recursive_finder(p1,list1,masterdict,d,ans):

to this

def recursive_finder(p1, list1, masterdict, d, ans):

Type Hints

This allows you to show what functions are accepting/returning. These are added to function headers. For example, from this

def find_groups(list1, list2):

to this

def find_groups(list1: list, list2: list) -> list:

String Formatting

Doing this

p1 = c1[0]+'_'+c2[0]
p2 = c1[1]+'_'+c2[1]

can be simplified using an f"" stringike so

p1 = f"{c1[0]}_{c2[0]}"
p2 = f"{c1[1]}_{c2[1]}"

Operator Spacing

This

dis += math.pow((point2[0]-point1[0]),2)
dis += math.pow((point2[1]-point1[1]),2)
dis += math.pow((point2[2]-point1[2]),2)

should be spaced out like this

dis += math.pow((point2[0] - point1[0]),2)
dis += math.pow((point2[1] - point1[1]),2)
dis += math.pow((point2[2] - point1[2]),2)

Simplification

The above can even be reduced to one statement

dis = math.pow((point2[0] - point1[0]), 2) + \
      math.pow((point2[1] - point1[1]), 2) + \
      math.pow((point2[2] - point1[2]), 2)

The \ allows the addition to span multiple lines, increasing readability.

Your calculate_distance function can now be reduced to one statement:

def calculate_distance(point1: list, point2: list) -> float:
    """
    Returns the distance between the two points
    """
    return math.sqrt(
        math.pow((point2[0] - point1[0]), 2) + \
        math.pow((point2[1] - point1[1]), 2) + \
        math.pow((point2[2] - point1[2]), 2)
    )