6

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

为此，我计划测试给定的顶点，如果是凹的，则将顶点分成组，测试每个组的凹度，并重复直到一组完整的凹形结果看起来就像放在一起时的原始形状

我想知道的是...

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

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

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

谢谢！

4

5 回答 5

6

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

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

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

递归现在是您的朋友：对您刚刚制作的每个子形状执行完全相同的过程。

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

于 2011-07-13T23:21:44.077 回答
4

昨天发布的Boost Geometry 库有一个. 一张图说了一千多个字： Convex Hull algorithm

在此处输入图像描述

尽管这构造了一个非凹形（即凸形）的“新”形状；这可能正是您想要的，也可能不是您想要的。但是，在此过程中，该算法必然能够将形状分类为凹/凸形状，因此您可能仍然对该库感兴趣。

凸包算法的一般信息：

由于 Adrian Japon 或多或少地建议“命中测试”（包含测试）是关心凸/凹几何的常见原因，因此我将重点介绍相应的 Boost Geometry 算法within：

再说一次，真的是因为这张照片太漂亮了。请注意，尽管图片建议针对多边形查询一个点，但算法是完全通用的，可用于测试对另一个 -n维多边形的完全包含

在此处输入图像描述

于 2011-07-13T22:20:54.923 回答
3

好吧，只是将所有信息混合在一起：

图像 1

  • 最后，使用此 Powerpoint中的信息对现在的 Monotone 形状进行三角测量：

    1. 将 u1 和 u2 压入堆栈。
    2. j = 3 /* j 是当前顶点的索引 */
    3. u = uj
    4. 情况 (i)：u 与 v1 相邻，但不与 vi 相邻。添加对角线 uv2, uv3, ..., uvi。从堆栈中弹出 vi, vi-1, ..., v1。将 vi, u 推入堆栈。情况（ii）：u 与vi 相邻，但不与v1 相邻。当 i > 1 且角度 uvivi-1 <  添加对角线 uvi-1 pop vi from stack endwhile push u 情况（iii）：u 与 v1 和 vi 都相邻。添加对角线 uv2, uv3, ..., uvi-1。出口
    5. j = j + 1 转到步骤 3。 
**Note:**
By “adjacent” we mean connected by an edge in P.   
Recall that v1 is the bottom of the stack, vi is the top.    
By “Push” we mean push the item(s) to the back of the list

希望这对某人有所帮助......但我仍在寻找更好/更快的解决方案。

于 2011-07-15T02:21:57.623 回答
1

需要考虑的一些事情：

  • 左手角和右手角（叉积的符号很容易区分）。凸形中的所有角都是相同的手性。

  • 与在现有顶点之间添加边相比，扩展边并添加新顶点可能会给您带来更好的结果。

于 2011-07-13T22:31:17.680 回答
1

我假设您将多边形作为点列表，一种非常简单的方法是绕过多边形并考虑连续点（A，B，C）的三元组序列。

然后你只需检查 det(AB,BC) 是否在某一时刻改变了它的符号，其中

det(AB,AC) = (x_a-x_b)(yc-yb) - (x_c-x_b)(y_a-y_b)

于 2011-07-13T23:23:29.267 回答