Polygon Hit Test with Ray Casting

Another old project that I’ve been digging back into with JavaScript recently has been the Lassie engine’s geometry system. Now, first and foremost, that’s NOT to say that the Lassie engine is in production for HTML5 (coding in my free time is not among my current priorities!). However, I’ve always found Lassie’s point-and-rectangle grid system to be archaic, and in all honesty, the only reason for that is because I’ve never taken the time to figure out polygon math. So, I’ve been tinkering with this…

The first thing that Lassie’s grid system would need to support polygons is a way to hit-test points against a polygonal area. A quick Google search on this led to an old (and shockingly simple) technique called ray casting.

The premise of ray casting involves extending a ray in one direction from the target point, and then counting how many times that ray intersects sides of the polygon in question. If the intersection count is an even number, then we can assume that the ray has both entered and exited the polygon’s boundaries an equal number of times, therefore placing the point outside of the polygon. However, if the intersection count is an odd number, then the point has entered but never left the bounds of the polygon and is therefore inside. Amazing that such a simple test holds up.

In JavaScript:

// Tests for counter-clockwise winding among three points.
// Specifically written for an intersection test:
// Uses ">=" (rather than ">") to cast equal points as valid CCW components.
function ccw(x, y, z) {
    return (z.y-x.y) * (y.x-x.x) >= (y.y-x.y) * (z.x-x.x);
}

// Tests for intersection between line segments AB and CD.
function intersection(a, b, c, d) {
    return ccw(a, c, d) !== ccw(b, c, d) && ccw(a, b, c) !== ccw(a, b, d);
}

// Performs ray casting, testing if point P falls within a polygonal region.
// @param p: The point to test.
// @param poly: An array of points forming a polygonal shape.
// @return: true if point falls within polygon.
function hitTestPolygon(p, poly) {
    var sides = poly.length,
        origin = {x:0, y:p.y},
        hits = 0,
        s1,
        s2,
        i;

    // Test intersection of an external ray against each polygon side.
    for (i = 0; i < sides; i++) {
        s1 = poly[i];
        s2 = poly[(i+1) % sides];
        origin.x = Math.min(origin.x, Math.min(s1.x, s2.x)-1);
        hits += (intersection(origin, p, s1, s2) ? 1 : 0);
    }

    // Return true if an odd number of hits were found.
    return hits % 2 > 0;
}

You’ll see our test uses three methods. First, ccw() tests for counter-clockwise winding among three points. Using that, we can test intersection() between two line segments by testing if the points of either segment wind into one another. Finally, we can perform ray casting by testing a target point’s line to an exterior point against each line segment in the polygon, and counting the number of intersections that are registered. Keep in mind that point order of your polygon array does matter (although the hit test still seems to work for oddly-wound polygons with intersecting sides). To see the hit test in action, try this:

var poly = [
    {x:10, y:10},
    {x:100, y:25},
    {x:125, y:125},
    {x:25, y:100}
];
hitTestPolygon({x:50, y:50}, poly); // true
hitTestPolygon({x:15, y:50}, poly); // false
Advertisements

2 comments so far

  1. ivan on

    Hi, I have implemented that algorithm into my Polygon library, it works really fast! :)
    http://polyk.ivank.net/?p=demos

  2. permion on

    Wow thanks. I just spent a few hours figuring out why this worked, including some of the math concepts I haven’t seen/remembered. It was an interesting learning experience.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: