是否有适用于凹多边形检测的好算法？目前我只找到了适用于凸多边形检测的算法，如有帮助将不胜感激。
凸多边形之间的碰撞检测算法
7
- Dariusz G. Jagielski
2
3你有没有看过那个问题的标题？它是关于凸多边形的，我的问题是关于凹多边形的。 - Dariusz G. Jagielski
我也来寻找答案，但我的解决方案是将凹多边形分解为凸多边形。我们可以用吃豆人的方法做到这一点，但是对于新月形呢？所以我正在前往下面的答案。 - Necktwi
3个回答
8
这篇2004年的论文探讨了一种高效的2D多边形碰撞检测算法，无论是凹多边形还是凸多边形都适用。
如果链接失效了，这里是作者和引用信息：
Juan José Jiménez, Rafael J. Segura, Francisco R. Feito
Departamento de Informática. E.P.S.J. Universidad de Jaén
Journal of WSCG, Vol.12, No.1-3, ISSN 1213-6972
- Ali Rasim Kocal
7
这篇文章虽然有些陈旧，但仍然很有参考价值。对于整体形状不变的多边形（可以旋转和缩放，但顶点之间的关系不能改变），有一些方法可以预处理顶点数据，以实现对多边形中的线进行一系列测试，以测试其他多边形是否与其碰撞。
我正在编写这个算法，所以我将向您提供其理论而非现成的算法：
传说：&&表示AND，||表示OR。
第一步a：
遍历多边形的线，并将每条线与其所有其他点进行测试，我们将分离出所有其他点位于该线上或“内部”一侧的线。
这些收集到的线形成了碰撞检测公式中的一个新节点，它们在彼此之间被视为逻辑AND检查。
第一步b：
将每个孤立的顶点组分别分离出来，并将它们单独馈送到下一步骤中：这些孤立的顶点组在彼此之间被视为逻辑AND。
第一步c：
如果在第3a/3b步到达时收集了任何线条，并且由于需要进入1a步骤而同时收集了多条线条，请重置在步骤3a / 3b中设置的任何变量并直接返回1a步骤。
第二步a：
遍历多边形的线，并将每条线与其所有其他点进行测试，我们将分离出所有其他点位于多边形的“外侧”（或更具体地说，全部位于线的非碰撞侧）的线。
这些收集到的线形成了碰撞检测公式中的一个新节点，它们在彼此之间被视为逻辑OR检查。
第二步b：
将每个孤立的顶点组分别分离出来，并将它们单独馈送到下一步骤中：这些孤立的顶点组在彼此之间被视为逻辑OR。
第二步c：
如果在第2a步骤中收集了任何线条，请重置在步骤3a / 3b中设置的任何变量并直接返回1a步骤。
第三步a：
进入此阶段意味着没有线条剩余，所有顶点都位于其中一条线的一侧。这意味着我们需要更积极地收集线条：
提高在步骤1a和2a中要收集的连续线条数量。这意味着除了所有顶点都位于一条线的一侧之外，它们必须至少位于收集到的线条之一的一侧（在1a中为内侧，在2a中为外侧）。一旦收集到任何线条，此值将重置为1。
第三步b：
如果要收集的连续线的数量超过图形中的线条数量，则将数字重置为2并允许收集非连续的线条（到达此处也是您的网格有点复杂并且您可能需要考虑将其缩小一点，不过达到3a并不是大问题，因为简单的星形必须输入才能解决）。
当使用生成的节点进行碰撞测试时，只需按顺序将要测试对象（点/线/圆）的形状提供给处理后的网格中的节点即可。
对于要进行碰撞测试的两个多边形，只需对其中一个进行此类处理。
创建示例多边形的公式：
1）将示例多边形提供给步骤1a： 在1a步骤之后的示例多边形 图片中的红线是所有其他顶点都在其内部的线，因此必须在其中找到一个形状以使其能够与多边形发生碰撞。
在1b之后，多边形将分为两个岛屿（A和B）。
2）将A和B提供给步骤2a： 在2a步骤之后的示例多边形 图片中的绿线是所有其他顶点都在其外部的线，因此如果形状在其中之一内部，则碰撞将发生。
在2b之后，A和B岛屿将进一步分为C、D、E和F。
3）将C、D、E和F提供给步骤1a： 在1a步骤之后的示例多边形 多边形C将失去一条线（我们称新形状为G），D将在1b步骤后分为两个岛屿（H和I），而多边形E和F没有线条可收集。
4）将G、H和I提供给步骤2a： 在2b步骤之后的示例多边形 多边形G将在2c步骤后分为两个岛屿（J和K），H将失去2条线（称新形状为L），而I将没有线条可收集。
5）将J、K和L提供给步骤1a： 在1a步骤之后的示例多边形 完成后，只需重复这些步骤3次即可收集到所有线条。
最终的多边形公式如下所示： 已标注相位的一行最终公式 更直观的表示方法如下： 带有可视化表示的最终公式 以下是标记了线条的原始多边形： 标记了线条的多边形 使用此方法，凹多边形测试碰撞的速度与将其分解为凸多边形时相同甚至更快（最坏情况是如果两者具有相同数量的顶点，则需要相同的时间，最佳情况可以将测试缩短到步骤1中的所有线和步骤2中的一条线，如果发生碰撞，则可以切掉形状的任何更复杂的蜿蜒线路）。
此算法的限制至少包括以下内容：
1）如果多边形的顶点正在进行动画处理，则上述公式不再适用，并且必须重新制作。然而，对于数量不太复杂的小型多边形来说，上述步骤并不是很复杂（需要（n-2）^2个“这个点在这条线的哪一侧”测试-其结果可以在整个步骤中被缓存和重用）。
2）不会自动处理多边形中的孔。然而，可以像上面那样处理孔并将以下规则应用于它：与原始多边形发生碰撞的形状必须与孔的线相交或者不与孔多边形发生碰撞才能发生碰撞。
3）我提出的拆分多边形的规则未针对任意复杂的多边形进行测试，并且可能需要进一步的规则来处理它们。
4）你必须自己编写算法的代码，因为我没有打算发布一个工作通用版本，这可能需要一段时间。
我正在编写这个算法，所以我将向您提供其理论而非现成的算法：
传说：&&表示AND，||表示OR。
第一步a：
遍历多边形的线，并将每条线与其所有其他点进行测试，我们将分离出所有其他点位于该线上或“内部”一侧的线。
这些收集到的线形成了碰撞检测公式中的一个新节点，它们在彼此之间被视为逻辑AND检查。
第一步b：
将每个孤立的顶点组分别分离出来，并将它们单独馈送到下一步骤中：这些孤立的顶点组在彼此之间被视为逻辑AND。
第一步c：
如果在第3a/3b步到达时收集了任何线条，并且由于需要进入1a步骤而同时收集了多条线条，请重置在步骤3a / 3b中设置的任何变量并直接返回1a步骤。
第二步a：
遍历多边形的线，并将每条线与其所有其他点进行测试，我们将分离出所有其他点位于多边形的“外侧”（或更具体地说，全部位于线的非碰撞侧）的线。
这些收集到的线形成了碰撞检测公式中的一个新节点，它们在彼此之间被视为逻辑OR检查。
第二步b：
将每个孤立的顶点组分别分离出来，并将它们单独馈送到下一步骤中：这些孤立的顶点组在彼此之间被视为逻辑OR。
第二步c：
如果在第2a步骤中收集了任何线条，请重置在步骤3a / 3b中设置的任何变量并直接返回1a步骤。
第三步a：
进入此阶段意味着没有线条剩余，所有顶点都位于其中一条线的一侧。这意味着我们需要更积极地收集线条：
提高在步骤1a和2a中要收集的连续线条数量。这意味着除了所有顶点都位于一条线的一侧之外，它们必须至少位于收集到的线条之一的一侧（在1a中为内侧，在2a中为外侧）。一旦收集到任何线条，此值将重置为1。
第三步b：
如果要收集的连续线的数量超过图形中的线条数量，则将数字重置为2并允许收集非连续的线条（到达此处也是您的网格有点复杂并且您可能需要考虑将其缩小一点，不过达到3a并不是大问题，因为简单的星形必须输入才能解决）。
当使用生成的节点进行碰撞测试时，只需按顺序将要测试对象（点/线/圆）的形状提供给处理后的网格中的节点即可。
对于要进行碰撞测试的两个多边形，只需对其中一个进行此类处理。
创建示例多边形的公式：
1）将示例多边形提供给步骤1a： 在1a步骤之后的示例多边形 图片中的红线是所有其他顶点都在其内部的线，因此必须在其中找到一个形状以使其能够与多边形发生碰撞。
在1b之后，多边形将分为两个岛屿（A和B）。
2）将A和B提供给步骤2a： 在2a步骤之后的示例多边形 图片中的绿线是所有其他顶点都在其外部的线，因此如果形状在其中之一内部，则碰撞将发生。
在2b之后，A和B岛屿将进一步分为C、D、E和F。
3）将C、D、E和F提供给步骤1a： 在1a步骤之后的示例多边形 多边形C将失去一条线（我们称新形状为G），D将在1b步骤后分为两个岛屿（H和I），而多边形E和F没有线条可收集。
4）将G、H和I提供给步骤2a： 在2b步骤之后的示例多边形 多边形G将在2c步骤后分为两个岛屿（J和K），H将失去2条线（称新形状为L），而I将没有线条可收集。
5）将J、K和L提供给步骤1a： 在1a步骤之后的示例多边形 完成后，只需重复这些步骤3次即可收集到所有线条。
最终的多边形公式如下所示： 已标注相位的一行最终公式 更直观的表示方法如下： 带有可视化表示的最终公式 以下是标记了线条的原始多边形： 标记了线条的多边形 使用此方法，凹多边形测试碰撞的速度与将其分解为凸多边形时相同甚至更快（最坏情况是如果两者具有相同数量的顶点，则需要相同的时间，最佳情况可以将测试缩短到步骤1中的所有线和步骤2中的一条线，如果发生碰撞，则可以切掉形状的任何更复杂的蜿蜒线路）。
此算法的限制至少包括以下内容：
1）如果多边形的顶点正在进行动画处理，则上述公式不再适用，并且必须重新制作。然而，对于数量不太复杂的小型多边形来说，上述步骤并不是很复杂（需要（n-2）^2个“这个点在这条线的哪一侧”测试-其结果可以在整个步骤中被缓存和重用）。
2）不会自动处理多边形中的孔。然而，可以像上面那样处理孔并将以下规则应用于它：与原始多边形发生碰撞的形状必须与孔的线相交或者不与孔多边形发生碰撞才能发生碰撞。
3）我提出的拆分多边形的规则未针对任意复杂的多边形进行测试，并且可能需要进一步的规则来处理它们。
4）你必须自己编写算法的代码，因为我没有打算发布一个工作通用版本，这可能需要一段时间。
- pie
1
由于我最近做过这个，因此我想记录一下我在这里使用的方法，因为似乎没有很清晰的答案。
本回答将避免描述通常用于碰撞检测的基础算法 SAT（分离轴定理），因为有关该算法的良好信息已经可以轻松获得。下面提供的信息提供了如何将凹多边形支持添加到现有的凸碰撞检测方案中的说明。
三角剖分
凸分解的最简单形式是三角剖分。
最简单的方法
执行三角剖分的最简单方法是耳切割法，我发现 这篇文章 最清晰地描述了它。
为什么要三角剖分
虽然三角剖分是有效的凸分解，但它将导致比多边形分解更多的 SAT 检查，因此不是最佳选择，但是多边形分解通常将三角剖分作为第一步。
还值得注意的是，三角形分解对于计算重心、转动惯量和其他物理性质以及用于渲染的漂亮选项都很好。
基本的耳剪法在三角剖分过程中会产生非常细的条带，这可能不太适合于碰撞检测和渲染，并且可能会导致不太理想的多边形分解。
修改后的耳剪法可以通过选择纵横比最佳的耳朵来改善，如本文所述。
Delaunay三角剖分算法提供具有最大最小内角的三角剖分。更简单地说，它可以生成更少的细条带的三角剖分，而该技术可以轻松搜索这篇文章很好地描述了这种方法。
多边形分解非常重要，因为它减少了需要进行SAT轴检查的数量，从而提高了运行时性能。
最简单的方法是：
这个问题的最简单方法是使用Hertel-Mehlhorn算法，它承诺产生的多边形数量不会超过最优解的4倍。在实践中，对于简单的凹多边形，该算法通常会产生最优解。
该算法非常简单；迭代由三角剖分创建的内部边缘“对角线”，并删除非必要的对角线。当对角线的两端连接的点为凸时，就会发现非必要的对角线。这是通过测试点的方向来确定的。
我能找到的最好的算法描述是this article。
改进
有许多多边形分解算法，其时间复杂度不同，一些算法可以为复杂的凹多边形产生更优的结果，但在大多数实时使用情况下，多边形复杂度可能较低。
实施细节
使用顶点索引
对于三角剖分和多边形分解，最好使用索引执行分解。这样可以节省内存，并提供一种易于确定哪些边缘是内部边缘的方法，因为外部边缘将始终具有相邻的索引。
SAT和碰撞法线
由于多边形分解会创建内部边缘，因此可能会导致SAT碰撞返回基于内部边缘的碰撞法线。为了解决这个问题，应该能够区分内部和外部边缘/法线，并且丢弃由内部边缘提供的任何碰撞法线。
交集和约束
基于约束的物理引擎（例如box2d，chipmunk，bullet）无法提供凹面体，因为这将允许多个碰撞点，在单个tick中无法解决。这意味着对于基于约束的物理引擎，必须使用关节，而且由于约束不能总是满足，因此多边形不一定严格地固定在一起。
在支持CCD（连续碰撞检测）且不允许多边形相交的物理引擎中，由于定义上始终存在第一个碰撞点，因此可以在求解器本身中支持凸面体碰撞。显然，这会带来性能上的代价。
本回答将避免描述通常用于碰撞检测的基础算法 SAT（分离轴定理），因为有关该算法的良好信息已经可以轻松获得。下面提供的信息提供了如何将凹多边形支持添加到现有的凸碰撞检测方案中的说明。
三角剖分
凸分解的最简单形式是三角剖分。
最简单的方法
执行三角剖分的最简单方法是耳切割法，我发现 这篇文章 最清晰地描述了它。
为什么要三角剖分
虽然三角剖分是有效的凸分解，但它将导致比多边形分解更多的 SAT 检查，因此不是最佳选择，但是多边形分解通常将三角剖分作为第一步。
还值得注意的是，三角形分解对于计算重心、转动惯量和其他物理性质以及用于渲染的漂亮选项都很好。
基本的耳剪法在三角剖分过程中会产生非常细的条带，这可能不太适合于碰撞检测和渲染，并且可能会导致不太理想的多边形分解。
修改后的耳剪法可以通过选择纵横比最佳的耳朵来改善，如本文所述。
Delaunay三角剖分算法提供具有最大最小内角的三角剖分。更简单地说，它可以生成更少的细条带的三角剖分，而该技术可以轻松搜索这篇文章很好地描述了这种方法。
多边形分解非常重要，因为它减少了需要进行SAT轴检查的数量，从而提高了运行时性能。
最简单的方法是：
这个问题的最简单方法是使用Hertel-Mehlhorn算法，它承诺产生的多边形数量不会超过最优解的4倍。在实践中，对于简单的凹多边形，该算法通常会产生最优解。
该算法非常简单；迭代由三角剖分创建的内部边缘“对角线”，并删除非必要的对角线。当对角线的两端连接的点为凸时，就会发现非必要的对角线。这是通过测试点的方向来确定的。
我能找到的最好的算法描述是this article。
改进
有许多多边形分解算法，其时间复杂度不同，一些算法可以为复杂的凹多边形产生更优的结果，但在大多数实时使用情况下，多边形复杂度可能较低。
实施细节
使用顶点索引
对于三角剖分和多边形分解，最好使用索引执行分解。这样可以节省内存，并提供一种易于确定哪些边缘是内部边缘的方法，因为外部边缘将始终具有相邻的索引。
SAT和碰撞法线
由于多边形分解会创建内部边缘，因此可能会导致SAT碰撞返回基于内部边缘的碰撞法线。为了解决这个问题，应该能够区分内部和外部边缘/法线，并且丢弃由内部边缘提供的任何碰撞法线。
交集和约束
基于约束的物理引擎（例如box2d，chipmunk，bullet）无法提供凹面体，因为这将允许多个碰撞点，在单个tick中无法解决。这意味着对于基于约束的物理引擎，必须使用关节，而且由于约束不能总是满足，因此多边形不一定严格地固定在一起。
在支持CCD（连续碰撞检测）且不允许多边形相交的物理引擎中，由于定义上始终存在第一个碰撞点，因此可以在求解器本身中支持凸面体碰撞。显然，这会带来性能上的代价。
- flatmush
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接