Szukam wydajnego algorytmu, który określa, czy wielościan jest wypukły.Jak określić, czy wielościan jest wypukły?
Zacząłem od sprawdzenia, czy charakterystyka Eulera wynosi 2. Sprawdzam również, czy każda twarz jest wypukła. Ale to wciąż nie przynosi wielu przypadków.
Miałem inny pomysł: dla każdej twarzy sprawdź, czy wszystkie e inne wierzchołki leżą po tej samej stronie tej twarzy.
Można to sprawdzić, obliczając normalny wektor dla każdej powierzchni (według produktu krzyżowego), a następnie obliczając produkt punktowy dla każdego wektora z jednego wierzchołka (powierzchni) na wszystkie pozostałe. Znaki muszą być takie same.
Algorytmy powinny działać, ale mogą różnić się czasem obliczeniowym.
to sprawdzić: http://liam.flookes.com/cs/geo/
Zasadniczo:
Świetnie, dzięki. Czy średnia z wierzchołków zawsze jest wewnętrzna w stosunku do wypukłego wielościanu? –
Ten punkt nie może być wybrany losowo, a będziesz miał fałszywy alarm, prawda? – Kryptos
@ Charles: Tak, jest, biorąc pod uwagę wypukłe ciało. @Kryptos Można wybrać losowo, ale musisz sprawdzić akord między punktem P i powierzchnią A dla przecięcia ze wszystkimi płaszczyznami ścian. Akord P-A może przecinać płaszczyznę twarzy B - na zewnątrz twarzy B_. –