如何将凸形状变成凹形状？

Question

如何将凸形状变成凹形状？

c++mathgraphicssfmlconcave

6

我正在尝试规避SFML C++库中只能形成凸多边形的规则。

为此，我计划测试给定的顶点，如果是凹多边形，则将顶点分成组，测试每个组的凹度，并重复此过程，直到产生一组完整的凹多边形，这些多边形在放在一起时看起来与原始形状相同。

我想知道的是...

- 检测形状凹度的方程式是什么？它是如何工作的？ - 如何分割凹多边形的顶点，以便最终形状由尽可能少的凸多边形组成？ - 实现我的目标的最佳实践是什么？

谢谢！

- Griffin

2

我认为你可能把术语搞反了。你想要将一个凹多边形分解成凸多边形吗？如果是这样，你可能需要研究一下多边形三角剖分。（三角形是最简单的凸多边形）。 - hammar

1

我之所以问这个问题，是因为凸多边形比凹多边形更容易处理，因此许多库只支持凸多边形是很常见的。我从未听说过只支持凹多边形的库。这个页面似乎证实了这一点。 - hammar

5个回答

4

昨天发布的Boost Geometry库实现了一个凸包算法。一张图片胜过千言万语：

enter image description here

虽然这个构造方法会创建一个非凹形状（即凸形），但这可能并不完全符合您的要求。然而，在此过程中，算法一定能够对形状进行凹/凸分类，因此您仍然可能会对该库感兴趣。

凸包算法的一般信息：

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

_{同样，真的因为图片太漂亮了。请注意，尽管图片暗示查询点是否在多边形内，但这些算法完全通用，并可用于测试另一个n-维多边形的完全包含性。}

enter image description here

- sehe

3

好的，将所有信息汇总如下：

要测试多边形的凹凸性，请参考Adrian Taylor提供的此页面
实现我的目标的一种方法是使用单调分解和三角剖分
您可以在这个可爱的网站了解单调分解：（下面是它的摘要）

最后，使用这个Powerpoint中的信息对现在的单调形状进行三角剖分：
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 从堆栈中弹出vi endwhile 推入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

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

- Griffin

1

一些需要考虑的事情：

左手和右手拐角（叉积的符号是一个简单的区分方法）。凸形状中的所有拐角都是相同的。
延伸边缘并添加新顶点可能会比在现有顶点之间添加边缘更好地改善结果。

- Ben Voigt

1

我假设你已经将多边形表示为点的列表，一个非常简单的方法是沿着多边形走，并考虑连续三个点（A，B，C）的序列。

然后，您只需检查在某一点上det（AB，BC）更改其符号，其中

det（AB，AC）=（x_a-x_b）（yc-yb）-（x_c-x_b）（y_a-y_b）

- fulmicoton

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adrian Taylor · Accepted Answer

您可以通过沿着所有的边缘并检查下一条边是否始终朝着同一个方向移动（左/右手定则）来测试形状是否为凸包。这是一种快速且便宜的算法。这里有一个实现： en.wikipedia.org/wiki/Graham_scan 如果您没有凸包，请执行一种包装算法以获得涵盖所有点的凸包（同样非常快）。en.wikipedia.org/wiki/Gift_wrapping_algorithm 现在，寻找在形状上但不在凸包上的点。对于每个这些点的运行，从这些点（加上凸包上的前后两个点）创建一个新形状。

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

我使用这些技术来测试点是否包含在任意形状内：即该点必须在凸包内（易于测试），但不在任何子形状或其子形状中。