JavaScript多边形相交

Question

我已经使用以下代码：http://www.amphibian.com/blogstuff/collision.html。在HTML测试文件中，我将第一个三角形改为：

triangle1.addPoint({"x":-20, "y":-20});
triangle1.addPoint({"x":-20, "y":20});
triangle1.addPoint({"x":20, "y":20});
triangle1.addPoint({"x":20, "y":10});
triangle1.addPoint({"x":10, "y":10});
triangle1.addPoint({"x":10, "y":-20});

现在当我移动内部三角形时，如果在越过它之前，它会给出错误的交点。有任何想法问题可能出在哪里？

- user1372020

---

我不理解你的问题和困难。 - Ibu

一个三角形如何有六个点？怎么会有坐标的负值？ - jbabey

最后三个三角形不应该是triangle1，而应该是triangle2吗？ - j08691

Answer 1

好的，我为想尝试这个的任何人设置了一个fiddle。以下是结果：

该脚本使用分离轴定理，或者（如维基百科所称）超平面分离定理，如 polygon.js 的源代码中所解释的那样。

/*
 *  To detect intersection with another Polygon object, this
 *  function uses the Separating Axis Theorem. It returns false
 *  if there is no intersection, or an object if there is. The object
 *  contains 2 fields, overlap and axis. Moving the polygon by overlap
 *  on axis will get the polygons out of intersection.
 */
Polygon.prototype.intersectsWith = function(other) {

这个定理只适用于凸多边形。你的形状不是凸的，因为它有一个“凹陷”。这就是脚本错误地报告形状相交的原因。如果你需要让它适用于凹形状，你需要先将凹形状分解成单独的凸部分，然后对所有单独的部分应用该定理。显然，这使脚本更加复杂，因为你需要迭代两个形状的凹部分的叉积。

- Mattias Buelens

---

非常感谢。我想我会选择O(N2)算法，因为我的多边形不是很大，也不是很多。只是好奇为什么这个方法不起作用。非常感谢您提供的信息。 - user1372020

如何移动碰撞的形状，有任何想法吗？ - yckart

@MattiasBuelens 这是我目前的进展：http://jsfiddle.net/ARTsinn/D9Pzb/2/ - yckart

@MattiasBuelens 的 polygon.js 已经不存在了。 - setec

@setec 找到了！ Fiddle已更新。 - Mattias Buelens

Answer 2

这里是我不太复杂的实现，用于查找两个多边形的交集。

它适用于凸多边形和凹多边形，但不适用于复杂（自相交）多边形。算法与Margalit & Knott中介绍的算法非常相似。

其复杂度约为4 * n1 * n2，其中n1和n2是正在计算其交集的多边形中的顶点数。

它是一个单独的 .js 文件。'Polygon'被认为是任何由2D点组成的javascript数组。'Point'是具有x和y数值属性的任何javascript对象。

在现有功能之上实现并集功能应该不是问题，我可能会很快做到。

2D多边形的交集

- AndroC

---

链接已经损坏。请在评论中包含代码本身。 - Luke

links are not working. - Ali Hamedani