如何判断多面体是否凸？

Question

我正在寻找一种确定多面体是否为凸面体的有效算法。

我首先检查欧拉特征是否为 2。我还检查每个面都是凸面。但这仍然没有抓住很多案例。

Answer 1

看看这个：http://liam.flookes.com/cs/geo/

基本上：

• 在多面体中选择一个点
• 从该点向每个面发送一条光线
• 确保光线只与选定的面相交

Answer 2

我有另一个想法：对于每个面，检查所有其他顶点是否位于该面的​​同一侧。

您可以通过计算每个面的法向量（通过叉积）然后计算从（面的）一个顶点到所有其他顶点的每个向量的点积来检查这一点。符号必须相同。

这两种算法都应该有效，但计算时间可能不同。