我正在寻找一种高效的算法来确定一个多面体是否是凸的。
我首先检查欧拉特征是否为2。我还在检查每个面是否为凸面。但这仍然无法涵盖很多情况。
2个回答
5
请查看：http://liam.flookes.com/cs/geo/
基本上：
- 在多面体内选择一个点。 - 从该点向每个面发射一条光线。 - 确保光线只与所选面相交。
- 在多面体内选择一个点。 - 从该点向每个面发射一条光线。 - 确保光线只与所选面相交。
- Buddy
7
太好了，谢谢。凸多面体的顶点平均值是否总是在内部？ - Charles Taylor
这个点不能随意选择，否则会有误报，对吗？ - Kryptos
@ Charles：是的，如果给定一个凸体的话，就可以这样做。
@ Kryptos：可以随机选择，但必须检查点P和面A之间的弦是否与所有面的平面相交。弦P-A可能会在面B的平面之外与面B相交。 - DasKrümelmonster
1@Kryptos 是的，我认为你是正确的，随机选择可能会给你错误的结果。 - Buddy
@DasKrümelmonster，这没意义：在任何给定的多面体中，您总是会与多个平面相交。 - Kryptos
显示剩余2条评论
4
我有另一个想法：对于每个面，检查所有其他顶点是否位于该面的同一侧。
您可以通过计算每个面的法向量（通过叉积）并计算从一个顶点（面的顶点之一）到所有其他顶点的每个向量的点积来检查这一点。符号必须相同。
这两种算法都应该有效，但计算时间可能不同。
- DasKrümelmonster
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接