Ich bin auf der Suche nach einem effizienten Algorithmus, der bestimmt, ob ein Polyeder konvex ist.Wie kann ich feststellen, ob ein Polyeder konvex ist?
Ich begann mit der Überprüfung, dass die Euler-Eigenschaft 2 ist. Und ich überprüfe auch, dass jedes Gesicht konvex ist. Aber das fängt immer noch nicht viele Fälle ein.
Ich hatte eine andere Idee: Für jedes Gesicht überprüfen, dass alle th Die anderen Eckpunkte liegen auf derselben Seite des Gesichts.
Sie können dies überprüfen, indem Sie den Normalvektor für jede Fläche berechnen (nach Produkt) und dann das Skalarprodukt für jeden Vektor von einem Eckpunkt (des Gesichts) zu allen anderen berechnen. Die Zeichen müssen gleich sein.
Die Algorithmen sollten beide funktionieren, aber sie können sich in der Rechenzeit unterscheiden.
Check this out: http://liam.flookes.com/cs/geo/
Grundsätzlich:
Großartig, danke. Liegt der Durchschnitt der Scheitelpunkte immer im Inneren eines konvexen Polyeders? –
Dieser Punkt kann nicht zufällig gewählt werden, und Sie werden falsch-positiv, richtig? – Kryptos
@ Charles: Ja, ist es, einen konvexen Körper gegeben. @Kryptos Es kann zufällig gewählt werden, aber Sie müssen den Akkord zwischen dem Punkt P und dem Gesicht A für den Schnitt mit allen Ebenen der Flächen überprüfen. Die Sehne P-A kann die Ebene der Fläche B außerhalb der Fläche B schneiden. –