Autor Wątek: Sprawdzanie czy ciąg jest zamknięty na mapie dwuwymiarowej (ogrodzenie) i ...  (Przeczytany 1669 razy)

Offline gadeawzuki

  • Użytkownik

# Marzec 12, 2016, 23:49:39
... czy punkt znajduje się wewnątrz ogrodzenia [Koniec tematu]

Witam.

Projektując moją aplikację przyszło mi się zmierzyć z problemem matematycznym. Przyznam, że zależy mi na jak najmniej zasobożernym rozwiązaniu, ponieważ funkcja będzie wywoływana dość często. Nie oczekuję konkretnych przykładów, raczej teorię i pseudokod, jednak dodam, że docelowo skrypt będzie wykonywany w PHP i (lub) JS.

Problem:
- Na mapie dwuwymiarowej (x,y), o wymiarach dla przykładu 12x12 (docelowo ok 50x50), w obiekcie przechowywane są dane o zajętych punktach czyli tytułowym ogrodzeniu. Celem funkcji jest sprawdzenie czy ogrodzenie:
a) jest zamknięte, styka się bokami, nie rogami (warunek konieczny)

prawda


fałsz


b) czy wewnątrz ogrodzenia znajdują się elementy i jakie
c) czy poza ogrodzeniem znajdują się elementy i jaki



Ciemno zielone elementy są wewnątrz, jasno zielone na zewnątrz, wynik to maja być dwie tablice bądź false jeżeli ogrodzenie jest niezamknięte.

Moim pomysłem jest wykonanie pętli na wszystkich polach, najpierw zebranie informacji czy ogrodzenie jest zamknięte, jeżeli tak, to kolejna pętla na mapie zbierająca informacje o elementach i dodająca je do konkretnych tablic.

Jeżeli ktoś wie gdzie znajduje się artykuł traktujący o tym zagadnieniu, będę wdzięczny za informacje i porady. Pozdrawiam.

Offline Mr. Spam

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

Offline albireo

  • Użytkownik

  • +1
# Marzec 13, 2016, 00:22:01
Zakładam, że masz ograniczenie, że ogrodzenie nie może być przy samej krawędzi (jeśli może, to dokładasz sobie ramkę po jednym pikselu z każdej strony), wtedy zapuszczasz floodfill (w wersji przechodzącej też po skosach) startując np z lewego górnego rogu, po zakończeniu komórki które oznaczył floodfill są "na zewnątrz", te których nie oznaczył, są "wewnątrz", jeśli nie ma żadnej które jest "wewnątrz", to znaczy że ogrodzenia nie ma lub nie jest zamknięte. Sprawdzenie czy obiekty są na zewnątrz czy wewnątrz to wtedy proste sprawdzenie czy leżą na komórkach oznaczonych jako wewnętrzne czy zewnętrzne.

Offline gadeawzuki

  • Użytkownik

# Marzec 13, 2016, 00:40:07
Super sprawa, dziękuję, na początku nie zrozumiałem zamysłu tego rozwiązania ale wikipedia pomogła. Dziękuję, jutro na pewno wykonam testy.