javascript polygon intersection

Question

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?

Answer 1

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.