c++ - 如何从凸形中形成凹形？

Question

我试图绕过只能在 SFML c++ 库中形成凸形的规则。

To do this I'm planning on testing given vertices, and if concave, splitting the vertices into groups, testing each groups' concaveness, and repeating until a full set of concave shapes results that look just like the original shape when put together

我想知道的是...

• 测试形状凹度的方程式是什么:它是什么以及它是如何工作的？

• 我如何拆分凹形的顶点，以便最终由尽可能少的凸形形成形状？

• 实现我的目标的最佳实践是什么？

谢谢!

---

Answer 1

您可以通过绕过所有边并检查下一条边始终沿同一方向(左/右手)移动来测试形状是否为凸包。这是一种快速且廉价的算法。这里有一个实现:en.wikipedia.org/wiki/Graham_scan

如果您没有凸包，请执行包裹包装算法以获得包含所有点的凸包(同样非常快)。 en.wikipedia.org/wiki/Gift_wrapping_algorithm

现在，寻找在您的形状上但不在凸包上的点。对于这些点的每次运行，从这些点创建一个新形状(加上凸包任一侧的 2 个)。

递归现在是你的 friend :对你刚刚制作的每个子形状执行完全相同的过程。

我已经使用这种技术来测试包含在任意形状内的点:即点必须在凸包内(易于测试)，但不是任何子形状或它们的子形状，或它们的子形状....