petak, 11. travnja 2014.

Intersection of two 2D polygons in Javascript

If you are dealing with 2D graphics, you must have dealt with polygons. Polygons such as:



Polygons under a are called convex polygons and those under b are called concave. There is also another kind of classification: simple and complex polygons. All of the above polygons are simple. If you draw a following polygon using 5 straight lines, then it is a complex polygon.



The same shape can also be drawn with more lines. In that case, this shape can represent three triangles, that is, three separate polygons that are merely positioned together.

If you wish to calculate intersection of two polygons, this can be relatively simple for convex polygons but a little bit trickier for concave and especially for complex polygons.

Convex polygon intersections:















Concave polygon intersection:
















I created a javascript library that take 2 polygons and return a third polygon that represents an intersection of the given 2 polygons. It works for both convex and concave polygon, but probably not as expected for complex polygons. Polygons are javascript arrays of Points. 'Point' is any javascript object that has both x and y numeric properties. The order of points in an array that defines a polygon is very important. The same set of n points can produce n! different polygons. Most all of them will be complex.

The .js file can be downloaded here:

Polygon.js

Library depends on jQuery for creating shallow copies of javascript objects - $.extend({}, object). Also for various utility functions like $.grep()