Algorytm do znalezienia, jeśli zbiór wypukły punkt opisuje enveloppe

Question

Chciałbym sprawdzić, czy zestaw punktów N opisać wypukłego wielokąta lub nie

Zastanawiałem się, czy nie jest to dobry algorytm do tego?

Oto niektóre podejścia myślałem:

algorytm

---

1.Convex Otoczka:

Jeśli zestaw jest równa jego wypukłej wtedy jest wypukła. Złożoność takiego algorytmu to O (n * LN (N)). Ale miałem przeczucie, że to jak rozbicie motyla na kole.

---

3.Looking w kątami

Następnie, że na sprawdzenie czy kąty 2 kolejne wektory nie przekracza 180 ° C. Ale ponieważ moje punkty nie są zamówione, muszę sprawdzić wszystkie kombinacje 3 kolejnych punktów i to sprawia, że ​​jest to złożoność O (n3). (Powinien być sposób, aby to zrobić lepiej)

Próbuję wybrać punkty od prawej do lewej, na przykład, ale wyniki nie zawsze są jednym z oczekiwaniami:

na przykład w tym przypadku uważam kształt wypukły, jeśli biorę od lewej do prawej:

Więc dla tego rozwiązanie Być może potrzebuję dobrego algorytmu do wyboru punktów.

---

3. patrząc środka ciężkości:

myślę, że sprawdzenie, czy środek symetrii wszystkich 3 consecutives punkt znajduje się wewnątrz kształtu powie mi, czy kształt jest wypukła o nie.

Oto co mam na myśli (G jest środek symetrii każdego trójkąta):

dla tego rozwiązania można wybrać punkty od lewej do prawej bez problemów. jeśli złożoność sprawdzania, czy G ma kształt O (N), wówczas ogólna złożoność byłaby trochę jak O (N2).

Czy możesz mi doradzić na dobry algorytm, aby rozwiązać ten problem lub poprawić rozwiązania Myślę

Dzięki z góry

Answer 1

Jeśli twoje wejście jest prostym wielokątem, możesz zrobić to w liniowym czasie, ale nie jest to wcale oczywiste. Istnieje długa historia błędnych rozwiązań tego problemu, które można przeczytać na poniższej stronie internetowej:

http://cgm.cs.mcgill.ca/~athens/cs601/

Dziś jest powszechnie akceptowane, że najprostszym/najlepszym sposobem rozwiązania tego problemu jest użycie Melkman użytkownika algorytm:

http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm#Melkman%20Algorithm

Jeśli nie masz wielokąt prosty, to w najgorszym przypadku jest to tak trudne, jak zwykłej wypukłej (ponieważ można po prostu wziąć każdy zwykły wypukłą problemu kadłuba i połączyć punkty arbitralnie, aby uzyskać jakiś bezsensowny wielokąt).

Answer 2

Myślałam zaczynając od Wikipedii na Grahams Scan:

Do wszystko aż do "sortowania punktów za pomocą kąta biegunowego z punktami [1]" włącznie.

następnie:

for i = 3 to N: 
    if ccw(points[i-2], points[i-1], points[i]) < 0: # Note this inequality might need checking 
     return NotConvex 
return Convex 

Zarówno sortowania i sprawdzanie wypukłości nadają się również do zrównoleglenia i może nawet zostać połączone do dalszego przyspieszenia w razie potrzeby.