Autor Wątek: Domknięcie wielokąta  (Przeczytany 710 razy)

Offline hubo

  • Użytkownik

# Czerwiec 24, 2009, 22:12:42
Mam nadzieje, ze tytul jest trafny.

Problem jest nastepujacy:
Mam siatke, powiedzmy 20x20, kazde pole tej siatki to kwadrat. Siatka ta reprezentuje plansze, moge zaznaczac dowolne pole na tej siatce - wtedy zmienia ono swoj stan na 'zaznaczony'. Moge naraz zaznaczyc wiecej niz jedno pole (powiedzmy wstawiajac klocek, jeden z takich jak w grze tetris). Nakladajac na siatke klocki w pewnym momencie powinny one otoczyc obszar. I teraz musze wyznaczyc moment w ktorym klocki otocza obszar, oraz zaznaczyc wszystkie pola tego obszaru. Dodatkowo klocek jest polaczony z innym klockiem tylko bokiem, a wiec kazdy klocek ma 4 sasiadow (skosy mnie nie interesuja).
Jak to zrobic efektywnie?
Zastanawialem sie np nad czyms takim jak rastrowe algorytmy wypelniajace, tylko one potrzebuja seed, czyli punkt z ktorego rozpoczynam wypelnianie, wtedy moglbym okreslic, czy mozna 'wyplynac' na krawedz mapy, czy obszar jest ograniczony (ale nie mam seeda, mam tylko punkty obwodu). Tak sobie kombinuje, moze graf i znajdowanie cyclu, albo znajdowanie minimalnego obwodu dla punktow - tylko ze ten algorytm zawsze mi polaczy punkty, trzeba by wymusic to sasiedztwo, ale nie wiem czy to nie jest juz zbedne kombinowanie. Wydaje mi sie ze juz tysiace ludzi takie cos rozwiazywalo i problem moze byc banalny, ale nie moge nic ciekawego znalezc.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 24, 2009, 22:35:12
Cytuj
(ale nie mam seeda, mam tylko punkty obwodu)
Możesz wziąć dowolny punkt, który nie jest zaznaczony. Albo wypełnisz zaznaczony obszar, albo wszystko na zewnątrz - tak, czy inaczej, będziesz wiedział co jest w środku, a co na zewnątrz. Pamiętaj tylko o przypadku, gdy użytkownik przedzieli całe pole gry na dwie części od krawędzi do krawędzi, nie zamykając pola.

Cytuj
Tak sobie kombinuje, moze graf i znajdowanie cyclu
Znajdowanie cyklu to też sensowne podejście (powinno być nawet szybsze. Nie musisz do tego mieć grafu, bo masz go w sposób niejawny (wierzchołkami są pola, dla każdego pola znasz sąsiadów). Ze znajdowaniem cykli jednak będzie trochę zabawy gdy pojawią się cykle zdegenerowane (np. blok 2x2 z zapełnionych pól), albo gdy tych cykli będziesz chciał mieć więcej niż jeden.

Offline wafello

  • Użytkownik

# Lipiec 01, 2009, 14:33:03
Mam pomysł na rozwiązanie:

1.Wrzucamy wszystkie pola na kolejkę.
2.Każdy element obwodu oznaczamy jako odwiedzony
3.Dla każdego elementu kolejki:
   a) Jeśli odwiedzony - nic
   b) Jeśli nie odwiedzony:
        - puszczamy jakiś algorytm zalewający który może chodzić tylko po nieodwiedzonych i zapisujemy sobie wszystkie odwiedzone tym algorytmem pola na stos. Jeśli nie osiągniemy ścianek na stosie mamy otoczony obszar.
        - wszystkie elementy stosu oznaczamy jako odwiedzone.

Ta metoda od razu rozpatruje przypadek gdy jest więcej niż jeden otoczony obszar.
Złożoność tego rozwiązania szacuje na O(ilość pól) gdyż każde pole jest rozpatrywane tylko raz i tylko raz może być odwiedzone przez algorytm zalewający.

Mam nadzieje że się przyda.

Offline matmis

  • Użytkownik

# Lipiec 13, 2009, 10:19:09
Wyobraź sobie graf, w którym wierzchołkami są pola, a krawędziami połączone są te pola, które są sąsiednie i są wolne. Czyli wstawienie klocka usuwa pewne krawędzie ten graf. A gdy klocki otoczą obszar, to w tym grafie powstaje nowa, osobna składowa spójna. Szczegół: można dodać sztuczny wierzchołek połączony z polami na brzegiem planszy i sprawdzać, czy po zmianie sąsiedzi usuwanego klocka są w innej spójnej składowej niż ten sztuczny wierzchołek. Czyli twój problem pasuje do problemu dynamicznej spójności grafu (w którym dodatkowo możemy jeszcze wstawiać krawędzie, czyli usuwać klocki - spoko). Czy zrozumiałem dobrze?

Na problem dynamicznej spójności grafu wymyślono w drugiej połowie lat 90'tych zaawansowane struktury danych które mają złożoności czasową operacji zmiany i sprawdzania logarytmiczną do niedużej potęgi. Jednak są dość skomplikowane, więc czy są szybsze od prostszych sposobów, to zależy od wielkości planszy.