Ustal, czy zestaw płytek na siatce tworzy zamknięty kształt

Biorąc pod uwagę zestaw płytek na siatce, chcę ustalić:

• Jeśli płytki tworzą zamkniętą figurę
• Jeśli płytki tworzą zamkniętą figurę, licząc boki planszy jako krawędź figury
• Jeśli jedno z dwóch poprzednich stwierdzeń jest prawdziwe, które dodatkowe płytki mieszczą się w załączonej figurze, początkowa forma płytek.

Gracz rozpocznie od naciśnięcia jednego kafelka, a następnie przeciągnięcia palcem na inne kafelki, aby utworzyć łańcuch płytek tego samego koloru. Będę sprawdzać, kiedy idę, aby sprawdzić, czy następny kafelek jest prawidłowy. Dawny. Jeśli gracz zaczyna na czerwonym kafelku, jego jedynym następnym prawidłowym ruchem jest sąsiadujący czerwony kafelek (przekątne się liczą). Kiedy użytkownik podnosi palec, muszę być w stanie sprawdzić 3 powyższe elementy.

Tak więc początkowo myślałem, że ponieważ za każdym razem, gdy szedłem, sprawdzałem ważność łańcucha , gdy gracz podniósł palec, mogłem sprawdzić, czy pierwszy i ostatni kafelek sąsiadują ze sobą. (Wiem już, że są tego samego koloru.) Gdyby były obok siebie, miałem przeczucie, że stworzyłem zamkniętą postać, i zamierzałem przyjść tutaj, aby sprawdzić, czy brakuje mi czegoś dużego, i dostać jakiś logiczny / matematyczny dowód, że moje przeczucie było prawidłowe (lub przykład, który dowodzi, że jest niepoprawny).

Ale wtedy pomyślałem o numerze 2: muszę także uwzględnić łańcuchy, które wykorzystują krawędź planszy jako bok załączonej figury. W takim przypadku pierwszy i ostatni element w łańcuchu nie przylegałyby do siebie, ale nadal miałbym zamkniętą figurę. Więc teraz wracam do punktu wyjścia.

Co mogę zrobić z tym łańcuchem współrzędnych siatki, aby dowiedzieć się, czy tworzą one zamkniętą figurę, czy nie? I raz ja nie wiem mam zamkniętą figurę, co jest najlepszym sposobem, aby uzyskać dodatkową listę wszystkich płytek, które mieszczą się wewnątrz jego granic?

Powyżej narysowałem zdjęcia 4 możliwych wyników tego testu.

1. Łańcuch nie tworzy zamkniętej figury.

2. Łańcuch tworzy zamkniętą figurę.

3. Jeśli policzysz boki planszy jako krawędź (lub więcej niż jedną krawędź) figury, łańcuch tworzy zamkniętą figurę.

4. Łańcuch tworzy zamkniętą figurę, ale istnieją dodatkowe punkty danych (prawnie wybrane przez użytkownika jako część łańcucha), które nie są częścią tworzonej figury.

Przypadek 4 jest najtrudniejszy, ponieważ musiałbyś wyodrębnić „dodatkowe” ogniwa łańcucha, aby znaleźć zamkniętą figurę i kawałki, które się w niej znajdują (ale nie wokół „niezamkniętego” obszaru).

Więc ... Czy ktoś ma pomysł na dobry sposób na rozwiązanie tego problemu, czy po prostu dla mnie punkt wyjścia? W tym momencie chodzę w kółko i przydałaby mi się kolejna para oczu.

1. Wykrywanie pętli płytek

Problem wydaje się podobny do wykrycia cyklu (pętli) na wykresie, patrz tutaj lub tutaj .

• Zestawem węzłów Vtego wykresu G=(V, E)są kafelki,
• e = (v1, v2)pomiędzy dwoma różnymi węzłami istnieje krawędź , jeśli płytki są sąsiadami bezpośrednimi lub ukośnymi

2. Postępowanie w przypadku obramowania ekranu

Obramowanie ekranu składa się z tych wyimaginowanych kafelków, które tworzyłyby krawędź o szerokości jednego kafelka wokół ekranu widocznych kafelków.

Zgodnie ze specyfikacją część obramowania ekranu stanowiłaby niejawną część zamkniętej pętli. Aby wykryć zamkniętą pętlę, wystarczy rozciągnąć wykres Gna wykres G', honorując połączenie za pomocą tej reguły:

• istnieje inna krawędź między dowolnymi dwoma różnymi węzłami, jeśli oba kafelki są umieszczone bezpośrednio w pobliżu krawędzi ekranu

Zatem płytki w (0,0) i (1,0) byłyby częścią zamkniętej pętli, razem z „płytkami granicznymi” (-1,0), (-1, -1), (0, -1) , (1, -1).

3. Wewnętrzna część zapętlonego obszaru

Chciałbym pójść w podobnym kierunku do tego, co sugerował użytkownik Arthur Wulf White :

Ograniczając zestaw płytek, musimy zbadać obwiednię płytek pętli.

Następnie za pomocą wypełnienia zalewowego wybierz wszystkie płytki w obwiedni, które są zewnętrzne lub wewnętrzne w zamkniętej pętli. Może to być tylko jeden z tych dwóch przypadków. Którego musimy się później dowiedzieć.

Dobrym pomysłem byłoby również rozszerzenie ramki ograniczającej o jedną płytkę w każdym kierunku, uzyskując extbb, więc kończymy z jednym połączonym zestawem punktów zewnętrznych, na wypadek, gdybyśmy rozpoczęli wypełnianie zalewowe płytką zewnętrzną.

Gdy już znajdziemy się na obszarze zalewowym, obliczymy również jego obwiednię, czyli ffbb. W przypadku, gdy zaczęliśmy od zewnętrznego kafelka, powinien on być identyczny z rozszerzoną ramką ograniczającą pętlę.

ffbb == extbb

W przypadku, gdy zaczęliśmy od płytki wewnętrznej, powinna ona dać wyraźnie mniejszą ramkę ograniczającą, ponieważ płytki pętli muszą być umieszczone pomiędzy obiema ramkami ograniczającymi.

ffbb < extbb

Początkowy kafelek początkowy dla wypełnienia powodziowego może być dowolnym kafelkiem, extbbktóry jest wolnym kaflem. Może najlepszym wyborem jest wybranie jednego losowo.

Gdybym wiedział wcześniej, że wnętrze jest mniejsze niż zewnętrzne, zacznę od środka masy punktów pętli, które znajdują się we wnętrzu dla wielu obszarów (przeciwny przykład: obszar w kształcie litery C), w przeciwnym razie na granicy extbb. Ale nie mam pojęcia, jak to oszacować.

Uwagi końcowe

Normalnie powiedziałbym, że wystarczy przejść od jakiegoś kafelka i prowadzić listę odwiedzonych kafelków, by wykryć cykl, ale ten warunek brzegowy ekranu może dać bardziej skomplikowany wykres, więc powinieneś być po bezpiecznej stronie z algorytmem graficznym .

Poniżej znajduje się przykład, w którym wnętrze nie jest podłączone, z drugiej strony wykrywanie cyklu powinno znaleźć dwie pętle w tym przypadku, jedną należy odrzucić.

Możesz rozwiązać ten problem poprzez:

1. Znajdowanie obwiedni tego kształtu.
2. Zwiększenie jego rozmiaru o 1 w każdym kierunku.
3. Iteracja nad ramą nowego, nieco powiększonego obwiedni i zastosowanie wypełnienia zalewowego.
4. Jeśli są jakieś płytki, których nie zaznaczyłeś wypełnieniem zalewowym, które nie znajdują się w tym łańcuchu, to są one dołączone. Podejrzewam, że z twojej definicji, jeśli są zamknięte płytki, kształt ma postać zamkniętą.

Aby zrobić jeden, iteracyjne nad wszystkich płytek na łańcuchu i znalezienie ich minX, minY, maxXa maxYi to jest Twój obwiednia lub AABB.

Dwa są banalne.

Iterowanie po ramie jest proste, upewnij się, że nie wypełniasz siatki poza siatką. Możesz dowiedzieć się, jak wypełnić Wikipedię .

W przypadku liczby czwartej możesz zacząć od sprawdzenia tylko płytek sąsiadujących z łańcuchem. Możesz wypełnić pole z dowolnego znalezionego kafelka, który nie jest zaznaczony, aby zlokalizować więcej kafelków.

Twoja intuicja jest słuszna, zakładając, że łańcuch kończy się, gdy tylko użytkownik spróbuje wybrać kafelek, który już wybrał. W takim przypadku kształt na ogół wygląda jak lasso na twoim zdjęciu (4). Jeśli potrafią przesuwać, mogą rysować wiele pętli, a sprawy stają się bardziej skomplikowane. To, co chcesz zrobić, to odpowiedzieć na pytanie wielokątów .

Najpierw musimy zdefiniować problem. Zakładam, że sytuacja wygląda jak (2), tzn. Każdy ogon został zdjęty, a koniec łączy się z powrotem na początku, tak że każda płytka ma dokładnie jednego „poprzednika” i dokładnie jednego „następcę” w łańcuchu (gdzie poprzednikiem następcy kafelka X jest zawsze kafelek X). Ponadto, jeśli wystarczająco długo śledzisz „następców”, w końcu wracasz do miejsca, w którym zacząłeś. Możesz użyć sugestii Gurgadurgena, aby wykryć, czy pętla faktycznie przecina się z powrotem w dowolnym momencie. Zakładając, że zakończysz wprowadzanie danych przez użytkownika, będzie to wyglądać jak seria węzłów w linii, a następnie pętla. Możesz zdjąć linię z pętli.

Teraz my dla każdego wiersza wykonaj następujące czynności:

1. Zacznij od lewej krawędzi i śledź wartość logiczną dla każdego kafelka, która mówi, czy jesteśmy IN, czy OUT. Ruszać w drogę.
2. Jeśli bieżący kafelek jest częścią łańcucha, spójrz zarówno na następcę, jak i poprzednika (które muszą sąsiadować). Jeśli któryś z nich znajduje się dokładnie powyżej (tj. Na północ, północny wschód lub północny zachód od bieżącego kafelka), ustaw stan bieżącego kafelka na przeciwległy do ​​kafelka po jego lewej stronie. W przeciwnym razie ustaw go tak samo jak kafelek po lewej stronie. Idź 4.
3. Jeśli bieżący kafelek nie jest częścią łańcucha, ustaw kafelek do stanu tytułu po lewej stronie. Idź 4.
4. Kafelek po prawej stronie jest teraz bieżącym kafelkiem. Idź 2.

Teraz weź wszystkie kafelki, które są IN, dodaj kafelki na granicy (w tym ogon, jeśli wcześniej go rozebrałeś, czy nie), i nazwij ten region.

Jeśli chcesz zezwolić użytkownikowi na używanie ramek, pamiętaj, że nie definiuje to i WEJŚCIE / WYJŚCIE na płycie, ale dzieli ją na dwie części. Możesz na przykład wybrać mniejszy region lub wymagać od użytkownika użycia dwóch sąsiednich stron (tj. Lewej i dolnej, ale nie górnej lub dolnej lub lewej / prawej).

Optymalizacja polega na tym, że wystarczy wykonać wiersze, które mają dowolne obramowanie (jeśli nie można użyć boków). Zakładam, że twoja tablica jest na tyle mała, że ​​iteracja po każdym kafelku i wykonywanie bardzo prostych obliczeń nie stanowi problemu, nawet w najsłabszym systemie mobilnym. (W końcu musisz je renderować, co jest znacznie bardziej skomplikowanym zadaniem).