Biorąc pod uwagę współrzędne punktu, w jaki sposób mogę określić, czy ma on dowolny kształt?określić, czy punkt znajduje się wewnątrz dowolnego kształtu?
Kształt definiowany jest przez tablicę punktów, nie wiem, gdzie kształt jest "zamknięty", część, której naprawdę potrzebuję pomocy, to ustalenie, gdzie kształt jest zamknięty.
Oto obraz, aby zilustrować, co mam na myśli trochę lepiej:
Najprostszym sposobem na to jest odlewana promień od tego punktu i policz ile razy przecina granicę. Jeśli jest dziwne, punkt jest w środku, nawet punkt jest na zewnątrz.
Wiki: http://en.wikipedia.org/wiki/Point_in_polygon
Zauważ, że to działa tylko dla różnorodnych kształtach.
Fantastyczne. Dzięki za przypomnienie mi o tym! – ambrus
Właściwie, jeśli podano tablicę punktów można sprawdzić bliskość kształcie następująco:
Rozważmy pary punktów P[i] i P[i+1] podane w tablicy - tworzą one pewien odcinek granicy kształtu . Należy sprawdzić, czy istnieją dwa takie przecinające się segmenty, które można sprawdzić w czasie O(N^2) (wystarczy sprawdzić wszystkie możliwe pary takich segmentów). Jeśli istnieje przecięcie, oznacza to, że twój kształt jest zamknięty.
Uwaga: należy uważać, aby nie zapomnieć o sprawdzeniu również segmentu P[0],P[n-1] (tj. Pierwszy i ostatni punkt w tablicy).
Kiedy krzyżują się p [i], p [i + 1] i p [j], p [j + 1]? Myślę, że można by powiedzieć, czy kształt jest prostym wielokątem, czy złożonym wielokątem. Ponadto nie odpowiedziałeś na oryginalne pytanie, jak znaleźć punkt w wielokącie. –
@logic_max: Cóż, odpowiedziałem na część pytania o to, jak sprawdzić, czy kształt jest zamknięty, i, zgodnie z instrukcją problemu, nie musi to być wielokąt, może to być dowolna polilinia. Obecność każdego skrzyżowania p [i], p [i + 1] i p [j], p [j + 1] powie nam tylko, że kształt ma część zamkniętą. A co z punktem w środku - odpowiedź Mikola jest prawidłowa. –
To nie działa. Co się stanie, jeśli weźmiesz zamknięty wielokąt, a następnie dodasz do niego zwisającą krawędź? Właściwie nie jestem pewien, co dokładnie testujesz i jak jest ono powiązane z pytaniem? – Mikola
Jeśli chcesz określić, czy punkt P ma arbitralny kształt, po prostu uruchomię wypełnienie powodziowe zaczynające się od P. Jeśli wypełnienie powodziowe pozostawia ustaloną ramkę ograniczającą, oznacza to, że znajdujesz się poza tym kształtem. W przeciwnym razie, jeśli wypełnienie powodzi się skończy, jesteś w kształcie :)
Wierzę, że ten algorytm to O (N^2), gdzie N to liczba punktów, ponieważ maksymalna powierzchnia jest proporcjonalna do N^2.
Wikipedia: Flood Fill
kształt nie jest otwarty ... ja po prostu nie wiem, gdzie ona jest zamknięta. – gibo
Musisz powiedzieć, w jaki sposób kształt jest definiowany przez tablicę punktów. Jeśli masz na myśli, że tablica punktów jest zbiorem punktów w kształcie, to pytanie jest banalne. – sawa
Obraz w moim poście może wyjaśnić to nieco lepiej .. Znam punkty wzdłuż niebieskiej linii, ale nie wiem, gdzie krzyż zamyka kształt – gibo