Uzyskaj unikalny hash kształtu niezależnie od jego rotacji, odbicia lustrzanego lub położenia - algorytm, algorytm graficzny

Kontekst

Tworzę generator labiryntu (właściwiebardziej jak generator map) oparty na „komorach”, które chcą się ze sobą łączyć. Czytam je z plików tekstowych, a następnie konwertuję na format wewnętrzny skomponowany z LocatedNodes które są zasadniczo typem węzła i współrzędnymi x-y. Przegrupowałem je NodeList gdzie umieściłem wszystkie funkcje, aby obrócić / zwiercić / znormalizować te węzły. ZA Map to zbiór komór, więc ma jeden NodeList zawierające te.

Podsumowując hierarchię: Mapa <- NodeList <- Lokalizowane węzły

Problem

Aby połączyć komory, porównuję kształty otwarcia pierwszej mapy i kształt obszaru wokół otwarcia drugiej mapy. Zacznijmy od przykładu:

>>> print map6.nodes # nodes of the entire map
1 1
0    5    0 2
o⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
0 |#############
|#...........#
|#...........#
|#...........#
|#............
5 |#............
|#........
|#........
|#........
|#........
10 |#########

>>> print map6.openings() # just the nodes placed on the opening
1
8   2
o⎯⎯⎯⎯⎯
4 |    .
|.....
|.
|.
|.
9 |.

>>> print map7.nodes # map we want to connect with the other
1   1
0    5    0   4
o⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
0 |    ###########
|    ..........#
|    ..........#
|..............#
|..............#
5 |..............#
|..............#
7 |###############

>>> print map7.joinable_on() # area around the map7.openings()
-
1   3
o⎯⎯⎯⎯⎯
1 |    .
|.....
|.
|.
|.
6 |.

>>> map7.joinable_on().normalized(x=0,y=0) == map6.openings().normalized(x=0, y=0)
True

Nie jest trudno porównać map6.openings () et map7.joinable_on (), ponieważ gdy pozycje węzłów są znormalizowane, mogę dokonać porównania jeden do jednego.

ALE, trudna część jest teraz: Chcę móc porównywać te kształty niezależnie od ich położenia, obrotu lub odbicia lustrzanego.

Co próbowałem

Szukając pomysłów znalazłem funkcja parowania (ta funkcja łączy dwa int z unikalnym int, więckażda współrzędna x-y staje się unikalną int). Dzięki temu mogłem jednoznacznie zidentyfikować kształt, stosując rekurencyjnie tę funkcję na współrzędnych (x, y). Pierwszy problem, unikalny int jest naprawdę wyjątkowy, więc nawet przy obrocie o 90 ° int zmienia się, więc nie mogę porównać dwóch kształtów w ten sposób.

Pytanie

Czy masz pomysł lub rozwiązanie, które pomogłoby mi uzyskać unikalny identyfikator kształtu, który nie zmienia się, gdy ten kształt zostanie odzwierciedlony, przetłumaczony lub obrócony?

Odpowiedzi:

1 dla odpowiedzi № 1

Istnieje ogólny schemat tworzenia identyfikatorównie zmieniaj, gdy kształt jest dublowany, tłumaczony lub obracany. Zacznij od identyfikatora, który troszczy się o dublowanie, tłumaczenie i obracanie. Kiedy otrzymasz kształt, rozważ wszystkie możliwe dublowanie, obracanie i tłumaczenie oraz oblicz identyfikator dla każdego przypadku, co daje dużą liczbę identyfikatorów, więc po prostu wybierz najmniejszy numer.

W przypadku tłumaczenia może być inny pomysłbyć bardziej praktycznym - przed (i / lub po) robieniem tego wszystkiego, przetłumacz kształt tak, aby jego środek ciężkości znajdował się u jego początku lub tak blisko początku, jak to możliwe.

---

1 dla odpowiedzi nr 2

Wygląda na to, że powinieneś mieć swoją listę kształtówbez tłumaczenia, obracania lub dublowania. Następnie, aby utworzyć mapę indeksującą kształt i udostępniającą macierz transformacji. Twój plik wejściowy wyglądałby następująco:

Shapes
shape1
shape2
shape3
etc.

Te kształty są zbudowane u źródła i nie mają tłumaczenia.

Twoja mapa stanie się wtedy:

Map
0 (index to shape1), transformation matrix (scaling, rotation, translation, mirroring)
2 (index to shape3), transformation matrix
0 (index to shape1), different transformation matrix

Następnie wszystko, co musisz zrobić, aby określić, czy dwa kształty na mapie są takie same, to porównać ich indeksy.

---