问题标签 [non-convex]

您能否向我提供一些关于 2D 非凸图形的良好碰撞检测算法的信息（或建议一篇文章）？

谢谢！

我有一个问题，我有一系列简单的非凸多边形的点（我希望我的术语是正确的）。但这些点不一定是按顺序排列的（即顺时针或逆时针）。为了让 Flash 的绘图 API 正确绘制填充区域，我需要让这些点在边缘周围按顺序排列（最终与起点连接）。

有什么方法可以按顺时针或逆时针方向对笛卡尔坐标列表进行排序，这样我就可以在不“举笔”的情况下从一个点到另一个点绘制我的形状？

我看到一篇文章对多边形的 4 点进行排序，但我认为这只是 4 点的特例。我的形状至少有 6 分。在列表中，每个条目都保证与其相邻的至少一个相邻（顺时针或逆时针顺序）相邻（前一点或后一点）。例如：A、B、D、C... 或 B、A、D、C... 但不是A、C、B、D...（我需要排序，所以我得到 A、B、C , D 或 D, C, B, A)。我找到了这篇文章，但似乎没有答案：将点列表排序为多边形

CPU性能是个问题。但是，即使是一个“缓慢”的解决方案，如果它易于实现和理解（对于下一个程序员），如果我能想出一个有效的缓存机制，也可能没问题。

我想附上一张图片来展示我需要做什么但还没有 10 个声望点的例子。无论如何，如果我有办法在这个多边形列表中对第三个示例的顶点进行排序，那将是完美的：http: //upload.wikimedia.org/wikipedia/commons/1/1f/Assorted_polygons.svg

我真的很感激任何和所有的帮助，谢谢！

编辑：我确实可以保证坐标系的中心点——它将是屏幕的中心。所有点都将介于 0 和屏幕宽度/高度之间（原点显然是宽度/高度 / 2）。我不能保证多边形将在其内部包含原点。这是一个罕见的例外情况，但我需要考虑它。

顺便说一句，我的片段不一定按顺序排列的原因是因为它们是使用 Conrec 生成的：http://paulbourke.net/papers/conrec/ （它们是等高线）。我使用以下命令对 Conrec 生成的轮廓线段进行排序：如何使用 Conrec 为轮廓线组装连续点的数组 现在的问题案例是地图上的外轮廓线。这些将与地图的边缘相交（即，不形成封闭的多边形）。在这种情况下，我在地图边界的边缘绘制，直到我重新连接线开始的位置（在地图的边缘）或兄弟线进入地图（重复直到我最终回到我的起点观点）。然后我可以绘制一个区域并让填充 API 工作。希望这些信息有所帮助。我认为最好的办法是生成多边形顶点的有序列表，但也许需要另一种方法。

我是使用 COcos2d IOS 的 Box2d 新手，并开始制作不同的简单实体，现在我在获取某些形状（即 mySprite.png）的顶点时遇到问题，例如不凸的不规则形状。如何将这些形状转换为凸形，以便它们的身体碰撞准确工作？

我是否必须将这些凹形分解成较小的凸形部分，这是一项繁重的任务，这是他们的任何简单方法或某种算法。

还请提供帮助材料链接

我将非常感谢您的帮助和关心。

问候阿比..

我使用了convexHull 算法来找到一些……不规则形状的轮廓。虽然还不够好...

很可能是因为我不能保证我的形状是凸的......

我有一组矩形，我希望能够获得轮廓外部的所有点 - 但不要抛出任何轮廓点。

凸包算法效果很好 - 但它就像右边的例子一样，所以我丢失了一些关于轮廓的信息。

我想要更接近左边版本的东西，保留外角，只消除里面的点......

有这样的算法吗？

或者，有没有办法将这样的形状（多边形）分解成凸形，以便凸包算法可以正确处理它？

从一个链接到另一个链接，我一直在试图弄清楚如何设置某种算法，比如 Hertel-Mehlhorn 算法——但我不知道在这种情况下使用相交线会做什么......

谢谢你的任何建议。

给定一个三维三角形网格，我怎样才能知道它是凸的还是凹的？有算法可以检查吗？如果是这样，定义公差范围以忽略小凹面将很有用。

^{图片来源：http ://www.rustycode.com/tutorials/convex.html}

我的问题与Plough 的问题非常相似；但有这个区别：

如何找到可以适合非凸区域的最大凸区域？

例如，考虑这个非凸区域：

任何想法或解决方案将不胜感激，谢谢。

是否有任何方法或算法可以从外部（周长）确定区域的凸（或非凸）属性？

一种方法是在周长的每个点上绘制切线，并讨论这条线与周长点相交的次数。如果没有显示相交（对于周长的所有点），我们可以断定区域是凸的。在其他情况下，区域是非凸的。

第二种方法是确定周长每个点的内角，并讨论它是否大于180。如果周边至少有一个点存在，则该区域是非凸的，它的内角大于 180。

还有其他更简单的方法吗？

任何想法或解决方案将不胜感激，谢谢。

我有一个已解决的模型，返回单个输出值并绘制它。根据这些值，我使用从 1-35 变化的 x 值和从 1-39 变化的 y 值绘制一个曲面，并将返回值作为 z 轴上的值。见下文。

该图不根据定义的函数运行，它只是输出值的图。

我一直在尝试使用我创建的随机优化算法来尝试找到全局最大值，但这需要很长时间并且并不总是正确的（与我用作的网格搜索算法相比比较）。创建的表面有细微的变化，足以产生多个麻烦的局部最小值和最大值。我正在寻找一种以相对快速的方式找到这个非凸面的全局最大值的方法。

编辑：

35 x 39 是搜索区域，它尽可能大。x 和 y 轴的值是模型的输入值（可能应该提到过），因此每个 z 值都与 x 和 y 输入坐标相关联。我最初的猜测通常是在搜索区域的中间轻拍。

该图的创建大约需要 50 分钟，因为 1365 个 z 值中的每一个都需要大约 3 秒来计算。我想这样做而不必使用详尽的枚举（评估每个点的 z 值）。我希望这需要大约 5 分钟而不是 50 分钟。

编辑（2）：

对困惑感到抱歉。下图是一个 35×39 的 z 值网格，仅供参考。在程序的实际执行中，我所拥有的只是 x 和 y 坐标，并且我试图在尽可能少的函数评估中找到全局最大 z 值，以节省时间。所以horchler，关于你的评论，后者。

编辑（3）：

这个数字只是一个例子。当我使用来自单独来源的数据时，会形成多个不同的图形（即左侧在此示例中可能无趣，但对于单独的一组数据，它可能包含也可能不包含全局最大值）。这增加了复杂性。从数据中无法判断全局最大值的位置。一些表面非常光滑，而另一些表面则具有大而频繁的峰值。

我和这里有同样的问题：如何在一个简单的非凸多边形中对顶点进行排序， 但没有我可以使用的解决方案。

我有点坐标，需要找到一些多边形。一个点列表有更多解决方案并不重要。我需要一些算法来找到其中一个。无所谓是哪一个。我真的不知道如何解决这个问题。

（我已将坐标存储在数组中，我想在 Javascript 中使用一些算法）

非常感谢。

这是二维计算几何中的一个问题。

假设我在没有孔的平面上有一个紧凑的集合 X（即它是简单连接的）。设 w 为向量，并考虑 X 与 X+w 的交集（即 X 被 w 平移）。如果以下情况属实，我说这个交叉点很复杂：

1. X 与 X+w 相交
2. 如果我们让 Y 是通过填充有界孔从 (X union X+w) 获得的简单连接区域，那么当我们绕过 Y 的边界时，我们可以找到循环顺序为 a,b,c,d 的 4 个点在边界上，使得 a 和 c 在 X 中但不在 X+w 中，而 b 和 d 在 X+w 中但不在 X 中。

为简洁起见，我们将 X 与 X+w 的交集复杂的 w 集合称为 X 的凹壳（注意：这与 alpha 集合无关；它只是一个名称）。

我想知道一种快速实用的算法来计算 X 的凹壳，其中 X 是（比如说）一个多边形盘。除此之外，我可能会对凹形船体的优雅表征感兴趣，也许用不同的术语。最后，我将非常感谢任何讨论这个问题的文献的指点。

以下是一些说明：

1. X 的凹壳是空的当且仅当 X 是凸的（因此得名）；这是因为如果 X 是凸的，并且 X 与 X+w 相交，那么 Y 的边界正好落入两个分量中，一个在 X 中，另一个在 X+w 中（从下面的第 3 点开始反过来）。
2. 多边形的凹壳应该是一个开放的多边形（即去除了边界），因此可以（例如）作为（开放）三角形的有限联合给出答案。
3. 如果 X 是非凸的，我们可以如下找到凹壳的一部分：设 L 是 X 的支撑线，它在两组 P 和 Q 中与 X 相交，它们之间有间隙 I。如果 J 是 X 的边界在 P 和 Q 之间的线段，那么 I 和 J 的并集在 X 的补集中界定了一个开盘 D，如果 p+ 是 P 的最接近 Q 的极值点，则 D-p+是在凹壳中。将这些区域在所有支撑线上的结合称为内凹壳；它看起来比较容易计算，但我认为它应该比一般的凹壳小。