CODEWITHSUNDEEP
pythonpython-3.x
Binh Thien
Binh Thien

Reputation: 395

How to find which lists are symmetric/translated?

The figure below has 6 pictures from a) to f) which each depicts points A, B, C, D, E with point positions in 2 dimension. a) and c) shape like trapezoid, while b) and d) look like V character. Also, e) and f) have same point arrangement. I'd like to collect 3 groups:

(a, c)
(b, d)
(e, f)

a = [
[[0.000, 0.500], [0.125, 0.250], [0.250, 0.000], [0.250, 0.500], [0.375, 0.250]],
[[0.000, 0.500], [0.125, 0.250], [0.250, 0.000], [0.375, 0.250], [0.500, 0.500]],
[[0.375, 0.250], [0.500, 0.000], [0.500, 0.500], [0.625, 0.250], [0.750, 0.500]],
[[0.375, 0.250], [0.500, 0.500], [0.625, 0.750], [0.750, 0.500], [0.875, 0.250]],
[[0.000, 0.000], [0.250, 0.500], [0.500, 0.000], [0.500, 0.500], [0.750, 0.500]],
[[0.125, 0.250], [0.375, 0.250], [0.375, 0.750], [0.625, 0.250], [0.875, 0.750]]
]

Output:

[
[[0.000, 0.500], [0.125, 0.250], [0.250, 0.000], [0.250, 0.500], [0.375, 0.250]],
[[0.375, 0.250], [0.500, 0.000], [0.500, 0.500], [0.625, 0.250], [0.750, 0.500]]
]
================
[
[[0.000, 0.500], [0.125, 0.250], [0.250, 0.000], [0.375, 0.250], [0.500, 0.500]],
[[0.375, 0.250], [0.500, 0.500], [0.625, 0.750], [0.750, 0.500], [0.875, 0.250]]
]
================
[
[[0.000, 0.000], [0.250, 0.500], [0.500, 0.000], [0.500, 0.500], [0.750, 0.500]],
[[0.125, 0.250], [0.375, 0.250], [0.375, 0.750], [0.625, 0.250], [0.875, 0.750]]
]

enter image description here

Upvotes: 2

Views: 90

Answers (1)

Nathan
Nathan

Reputation: 3648

You can find your answer as following:

  1. Define your lists
  2. For each list, check if it matches any of the previous unique lists.
  3. Each list has 4 possible mirrored versions (2 along x and 2 along y) so check all 4 of those

Step 1:

a = [[[0.000, 0.500], [0.125, 0.250], [0.250, 0.000], [0.250, 0.500], [0.375, 0.250]],
     [[0.000, 0.500], [0.125, 0.250], [0.250, 0.000], [0.375, 0.250], [0.500, 0.500]],
     [[0.375, 0.250], [0.500, 0.000], [0.500, 0.500], [0.625, 0.250], [0.750, 0.500]],
     [[0.375, 0.250], [0.500, 0.500], [0.625, 0.750], [0.750, 0.500], [0.875, 0.250]],
     [[0.000, 0.000], [0.250, 0.500], [0.500, 0.000], [0.500, 0.500], [0.750, 0.500]],
     [[0.125, 0.250], [0.375, 0.250], [0.375, 0.750], [0.625, 0.250], [0.875, 0.750]]]

Step 2:

graphs = []
for i in range(len(a)):
     matched = False
     for j in range(len(graphs)):
          if compare_mirrored_lists(graphs[j][0], a[i]):
               graphs[j].append(a[i])
               matched = True
               break
     if not matched:
          # If no matches were found, it's a new list and can be added
          graphs.append([a[i]])

Step 3:

def set_at_origin(lst):
    # Make sure the list will always have the same order
    lst = sorted(lst)
    # Make sure the first element is at [0, 0]
    return [[i[0] - lst[0][0], i[1] - lst[0][1]] for i in lst]

def compare_lists(a, b, error=0.001):
    # Check if a list of lists is the same
    for i in range(len(a)):
        for j in range(len(a[i])):
            if abs(a[i][j] - b[i][j]) > error:
                return False
    return True

def compare_mirrored_lists(list_1, list_2):
    list_1 = set_at_origin(list_1)
    list_2 = set_at_origin(list_2)

    # Check all 4 mirrored options
    for mirror_x in [-1, 1]:
        for mirror_y in [-1, 1]:
            list_2_mirrored = [[mirror_x * i[0], mirror_y * i[1]] for i in list_2]
            list_2_mirrored = set_at_origin(list_2_mirrored)

            if compare_lists(list_1, list_2_mirrored):
                return True

    return False

Upvotes: 2

Related Questions