javascript多边形交集

我已经使用了以下代码： http://www.amphibian.com/blogstuff/collision.html。在HTML测试文件我已经改变了第一三角形javascript多边形交集

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});

现在

当我穿越之前，这个形状内移动另一三角形它给了我错误地交集。任何想法可能是什么问题？

来源

2012-05-31 user1372020

我不明白你的问题和解决问题 – Ibu

如何三角形有6分？你对坐标的负值如何？ – jbabey

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

好吧，我为其他想玩这个的人设立了一个fiddle。下面是结果：

Demonstration of the problematic intersection

脚本利用分离轴定理或（维基百科称之为）Hyperplane separation theorem，如在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) {

这个定理仅适用于凸多边形。你的形状不是凸的，因为它有一个“凹痕”。这就是为什么脚本错误地报告形状正在相交。如果你需要使它与凹形一起工作，你必须首先将凹形分成单独的凸起部分，然后将定理应用到所有单独的部分。显然，这使得脚本更加复杂，因为您需要遍历两个形状的凹形部分的叉积。

来源

2012-05-31 18:03:19

非常感谢。我想我会用o（N2）算法去，因为我的多边形不是很大，也不是很多。只是奇怪，为什么这不起作用。非常感谢信息。 – user1372020

任何想法都可以移动碰撞的形状？ – yckart

@yckart在小提琴中存在轻微的配置错误，JavaScript代码被包装在MooTools onLoad处理程序中，因此事件未被正确绑定。它应该现在工作，再试一次。 –

这里是我找到两个多边形的交点多边形不太复杂的实现。

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

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

它是一个独立的.js文件。 '多边形'被视为2D点的任何javascript数组。 'Point'是具有x和y数字属性的任何javascript对象。

在现有工具上实现联合功能应该不成问题，我很快就可以做到这一点。

Intersection of 2D polygons

来源

2014-04-14 14:07:37 ancajic

javascript多边形交集

回答

相关问题