Sto cercando un algoritmo efficiente che determini se un poliedro è convesso.Come determinare se un poliedro è convesso?
Ho iniziato verificando che la caratteristica di Eulero è 2. E sto anche verificando che ogni faccia è convessa. Ma questo non cattura ancora molti casi.
Ho avuto un'altra idea: per ogni faccia controllare che tutto e altri vertici si trovano sullo stesso lato di quella faccia.
È possibile controllare questo calcolando il vettore normale per ogni faccia (per prodotto incrociato) e quindi calcolando il prodotto punto per ciascun vettore da un vertice (della faccia) a tutti gli altri. I segni devono essere gli stessi.
Gli algoritmi dovrebbero funzionare entrambi, ma potrebbero differire nel tempo di elaborazione.
Check this out: http://liam.flookes.com/cs/geo/
Fondamentalmente:
Grande, grazie. La media dei vertici è sempre interna a un poliedro convesso? –
Questo punto non può essere scelto a caso e si avrà il falso positivo, giusto? – Kryptos
@ Charles: Sì, è dato un corpo convesso. @Kryptos Può essere scelto a caso, ma è necessario controllare l'accordo tra il punto P e la faccia A per l'intersezione con tutti i piani delle facce. L'accordo P-A può intersecare il piano della faccia B _ al di fuori della faccia B_. –