Autor Wątek: Otoczka (nie)wypukła  (Przeczytany 1141 razy)

Offline .Dexter.

  • Użytkownik

# Czerwiec 26, 2011, 12:54:31
Cześć, zastanawiam się ostatnio jak można znaleźć otoczkę, ale niewypukłą. Do wypukłej wiadomo - Graham na przykład. Chodzi mi o np. coś takiego jak tu:
http://zagram.org/animstop.gif

Pewnie jest prosty sposób, a ja sobie wymyślam jakieś skomplikowane rzeczy :P

Offline Mr. Spam

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

Offline owyn

  • Użytkownik

# Czerwiec 26, 2011, 14:49:20
1. Sortujesz punkty względem x.
2. Bierzesz punkt położony najbardziej na lewo (z najmniejszą współrzędną x, nazwijmy go x0) i najbardziej na prawo (x1).
3. Dodajesz x0 do dolnej części otoczki.
4. Iterujesz po wszystkich pozostałych punktach, zaczynając od lewej. Jeśli punkt x leży powyżej prostej wyznaczonej przez punkty x0 i x1, to dodajesz go do górnej części otoczki. Jeśli leży poniżej lub na prostej, to dodajesz go do dolnej części otoczki.
5. Dodajesz x1 do dolnej części otoczki.
6. Na końcu masz dwie części otoczki: górną i dolną, wystarczy je połączyć.

// Edit: a, jeszcze zapomniałem napisać co gdy kilka punktów ma taką samą współrzędną x - wtedy oczywiście do górnej części bierzesz ten najwyżej, a do dolnej - ten najniżej.
« Ostatnia zmiana: Czerwiec 26, 2011, 14:53:40 wysłana przez owyn »

Offline nembutal

  • Użytkownik

# Czerwiec 26, 2011, 22:18:52
jak można znaleźć otoczkę, ale niewypukłą.
Otoczkę czego? Zbiór punktów jest tylko zbiorem punktów - potrzeba dodatkowych informacji opisujących ten wklęsły kształt.

Offline .Dexter.

  • Użytkownik

# Czerwiec 26, 2011, 22:47:19
No właśnie tak to czytam i chyba za mało informacji podałem. Konkretnie chodzi mi o grę w kropki:
http://pl.wikipedia.org/wiki/Kropki_%28gra%29
http://zagram.org/ <- tu można zagrać.

Ciekawi mnie jak tu ta otoczka jest realizowana... ma ktoś pomysły? Bo ja siedzę nad kartką już dłuższy czas i nie mogę nic sensownego wymyślić.

edit:
Na razie myślałem o takim czymś, żeby jakoś lecieć po kropkach przesuwając się na sąsiadującą i jak wrócę do tej od której zacząłem to jest otoczka, tylko kwestia jeszcze jak sprawdzić czy wewnątrz tej otoczki jest kropka przeciwnika. No i jak to takie bardzo ogólne, pewnie jakbym zaczął takie coś realizować w kodzie to napotkałbym jeszcze z 10 problemów.
« Ostatnia zmiana: Czerwiec 26, 2011, 23:09:51 wysłana przez .Dexter. »

Offline mINA87

  • Użytkownik

# Czerwiec 27, 2011, 12:23:42
Nie wiem czy to rozwiązanie jest dobre dla wszystkich możliwych warunków, ale wydaje się być sensowne.
Najpierw starasz się z punktów stworzyć graf - dla każdej kropki-wierzchołka szukasz sąsiadów i wyznaczasz listy połączeń.
Teraz jak masz już taki graf - szukasz w nim cykli, najdłuższy cykl powinien być Twoją otoczką. Żeby poszukać cykli w takim grafie możesz np. wybrać jeden wierzchołek, "pokolorować go" i teraz "rekrencyjnie" (w praktyce można użyć jakiegoś stosu do zapisu poszczególnych węzłów i dla każdego węzła kolorujesz również odwiedzone już połączenia ) śledzisz wszystkie połączenia - gdy podczas tego napotkasz na już jakiś pokolorowany węzeł to voila - masz znaleziony cykl i używając stosu możesz dokładnie wyznaczyć go i jego długość.

Co do sprawdzania czy kropka jest zawarta w otoczce - znajdujesz kropki otoczki będące na tej samej lini w pionie i później poziomie, wybierasz najbardziej wysuniętą kropkę z jednej strony - ona otwiera Twój "przedział", jeśli następna kropka w linii jest połączona z tą, to nic nie robisz, jeśli jest nie połączona, to zamknie Ci przedział. Robisz tak na zmianę wyznaczając kolejne przedziały otwarte/zamknięte i w trakcie tego możesz sprawdzić jak to się ma do pozycji sprawdzanej kropki. Jeśli sprawdzana kropka jest w przedziałach zamkniętych otoczki w pionie i poziomie, to należy do otoczki.
Być może trochę przekombinowane, ale bazując na tym, że kropek nie da się podkradać i de facto sprawdzasz tylko kropki dostawione pomiędzy utworzeniem przedostatniej i ostatniej otoczki to będzie to powinno to działać sensownie.