如何判断多面体是否凸?
How do I determine if a polyhedron is convex?
我正在寻找一种确定多面体是否为凸面体的有效算法。
我首先检查欧拉特征是否为 2。我还检查每个面都是凸面。但这仍然没有抓住很多案例。
看看这个:http://liam.flookes.com/cs/geo/
基本上:
- 在多面体中选择一个点
- 从该点向每个面发送一条光线
- 确保光线只与选定的面相交
我有另一个想法:对于每个面,检查所有其他顶点是否位于该面的同一侧。
您可以通过计算每个面的法向量(通过叉积)然后计算从(面的)一个顶点到所有其他顶点的每个向量的点积来检查这一点。符号必须相同。
这两种算法都应该有效,但计算时间可能不同。