hitTestPoint vs. insidePolygon

update: After trying the below method with highly detailed, dynamically stored polygonal data, I now realize that hitTestPoint is MUCH more efficient. Therefore, the below should only be used with very simple (like less than 20 points) polygons. Hopefully it’s still of interest, though!

When creating dynamic Flash dot density maps (see my wiscMapper), it seems only natural to make use of ActionScript’s built-in hitTestPoint method. Hell, it works. I’ve typically created random points within the bounding box of the polygon in question, called the hitTestPoint method to determine if they would “hit” the polygon, and placed (or killed) the dot accordingly. This works, and it can place 5000 dots on a fairly small polygon in just a second or two.

randPoint = new Point(Math.random()*sprite.width, Math.random()*sprite.height);
randPoint = sprite.localToGlobal(randPoint);</li>
if (sprite.hitTestPoint(randPoint.x, randPoint.y, true)) {

But sometimes a second or two is way too long. And sometimes a polygon is very small, so small that Flash bugs out on hitTestPoint calls (always returning false in this case). Having had just this problem, and dealing with dynamic data as I am (that is, dealing with data for which the coordinates of nodes are still being stored in arrays), I decided to try to recode a better method.

randPoint = new Point(Math.random()*sprite.width, Math.random()*sprite.height);
if (PolyTools.insidePolygon(poly, poly.length, randPoint) == 1) {

PolyTools.insidePolygon is simply a static method I wrote based on the stuff I read here about the point-in-polygon test. How does it compare? Well gents, in my tests it is almost exactly twice as fast as calling hitTestPoint. But I haven’t done extensive testing, and haven’t tested very complex polygons. But still, I plan on switching most of my dot density work over to the point-in-polygon method soon. Remember, though, that this only works for data that is dynamically stored as the movie runs (a dynamically-loaded shapefile, say).

And a slight advantage of the faster method is that dots are only placed within the polygons — NOT on the borders. The hitTestPoint results, by contrast, will of course return True in cases where the point “hits” the polygon’s border.

One Comment

  1. Which algorithm did you find executed fastest?

    lee
    Posted May 27, 2011 at 2:21 pm | Permalink

One Trackback

  1. By indiemaps.com/blog » pixelArea on June 2, 2008 at 11:34 pm

    [...] density map in wiscMapper, but never needed to use it until recently. You see, as I noted recently here, to create a dot density map in Flash, it is typical to create random points within the bounding [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *