javascript多边形交集 [英] javascript polygon intersection

问题描述

我使用了以下代码：
，如 polygon.js 的来源中所述：

  / * 
 *要检测与另一个Polygon对象的交集，此
 *函数使用分离轴定理。如果没有交集，则返回false 
 *，如果有，则返回对象。对象
 *包含2个字段，重叠和轴。通过重叠
 *在轴上移动多边形将使多边形不在交叉点。 
 * / 
 Polygon.prototype.intersectsWith = function（other）{
  

此定理仅适用于凸多边形。您的形状不是凸面的，因为它具有凹痕。这就是脚本错误地报告形状相交的原因。如果你需要使它与凹形一起工作，你必须首先将凹形分割成单独的凸形部分然后将该定理应用于所有单独的部分。显然，这会使脚本更复杂，因为您需要迭代两个形状的凹陷部分的叉积。

I have used the code in the following : http://www.amphibian.com/blogstuff/collision.html. in the html test file I have changed the the first triangle to

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

now when I move the other triangle with inside this shape before crossing it gives me wrongly intersection. Any idea where could be the problem?

解决方案

All right, I set up a fiddle for anyone else wanting to play with this. Here are the results:

The script makes use of the Separating Axis Theorem or (as Wikipedia calls it) Hyperplane separation theorem, as explained in the source of 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) {

This theorem only applies to convex polygons. Your shape is not convex as it has a "dent" in it. That's why the script incorrectly reports that the shapes are intersecting. If you need to make it work with concave shapes, you'll have to make it first split the concave shape up in separate convex parts and then apply the theorem to all individual parts. Obviously, this makes the script more complex as you need to iterate over the cross product of the concave parts of two shapes.

这篇关于javascript多边形交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！