[AS2] Point in Polygon (beginfill is not instant)

[Alluvian]

I figured Point in Polygon would be a SNAP in flash. Just draw the polygond with beginfill, moveto, lineto, endfill and then perform a shapeflag = true hittest!

Drawing the shape and checking hittesting with mouse coordinate and onenterframe worked great. So I wasted a bunch of time making a polygon drawing function which I was going to use to draw a polygon, perform hittests against it, and then erase the polygon and associated movieclip.

Unfortunately
I don't know if it waits till the next frame or what, but you can't do a shapeflag = true hittest on movieclip in code that executes in the same frame. For instance:

var square_mc:MovieClip = this.createEmptyMovieClip("square_mc", 1);
square_mc.beginFill(0xFF0000);
square_mc.moveTo(10, 10);
square_mc.lineTo(100, 10);
square_mc.lineTo(100, 100);
square_mc.lineTo(10, 100);
square_mc.lineTo(10, 10);
square_mc.endFill();
trace(square_mc.hitTest(50,50,true));  // returns false
trace(square_mc.hitTest(50,50,false));  // returns true 

I am trying to make a bunch of objects (to be rendered as bitmaps) in a bricklike grid pattern within polygonal shapes. Works fine for rectangles, and I was going to use the same rectangle row/column code but with an added "is point in polygon" check for each object, creating it if it is inside the polygon.

Unfortunately the above issue prevents this from working right. I guess I could keep the movieclips with the polygons till the next frame, then check all the objects to see if they are THEN inside their appropriate polygons and THEN delete those extra movieclips, but that just seems like a very lame hack of a solution.

Anyone now a decen point in poly function for flash as2? Right now I have the vertices as arrays of point objects, but I could be flexible.

[rachil0]

Use a sequence of cross products to sidetest against each edge of the polygon (assuming it's convex). You can also do dot products against the normals of the edges, in 2D these operators are exactly the same.

If your points are sequenced in a counter clockwise fashion in a right handed coordinate system, do something like:

  function testInside (testPoint: Vector2D, p : Polygon) : Boolean
     {
     for each Edge e of Polygon p
        {
        var point1 : Vector2D = start of Edge e
        var point2 : Vector2D = end of the Edge e
        var edge_displacement : Vector2D = point2 - point1
        var test_displacement : Vector2D = testPoint - point1
        var det : Number = cross(edge_displacement, test_displacement);
        if (det < 0) 
          return false;
        }
     return true;
     }

   function cross (v1, v2) : Number
      {
      return v1.x * v2.y - v2.x*v1.y;
      }

If your polygon is not convex, tesselate it into a union of convex polygons, do a insideness test against each one, and "or" the result.

[Alluvian]

Know of a way tesselate a concave poly into a series of convex ones?

Seems like I am increasing my odds of having an edge case with more polygons (object on an edge will cause extra issues with most point in poly schemes).

Anyone know of a ray casting solution for AS2?

[Alluvian]

An ugly solution I am kicking around is making all the objects, waiting 2 frames and using hittest to see which ones I should delete. Not a pleasant solution for me with the number of arrays I have them in for cross referencing purposes though. (region arrays for fast hittesting, all of type array for checking when game is won, and a third for seeing when I can turn of some displacement map effects to shave some cpu time)

[Alluvian]

FOUND IT!

For others who want it, here is my AS2 rewrite of the C++ code found here: http://geometryalgorithms.com/Archiv...rithm_0103.htm

This uses raycasting so it will work on concave or convex polys. It will even work with polys with holes in them. Anyway, I take very little credit since the C++ code practically ported itself.

import flash.geom.Point;
pointinpoly = function(P:Point, V:Array){
    var crossing:Number = 0;
    var n:Number = V.length - 1;
    for(var i = 0; i<n; i++){
        if (((V[i].y <= P.y) and (V[i+1].y > P.y)) or ((V[i].y > P.y) and (V[i+1].y <= P.y))) { 
            var vt:Number = (P.y - V[i].y) / (V[i+1].y - V[i].y);
            if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) {crossing++;}
        }
    } // next i
    if (crossing % 2) {return true;} else {return false;}
} // end of pointinpoly 

Where P is a point object and V is an array of vertices as point objects. The polygon should be closed, meaning the first and last points should be the same. v[0] = v[n]

[rachil0]

If you build in some fudge factor into that determinant test, you shouldn't have significant problems with edge cases. Maybe edges count as inside, maybe they don't, but you as a system designer can make that choice willfully and in a fault-tolerant way with that determinant test.

Decomposition of complex polygons into convex sets has been a part of every constrained movement system I've tried to write, so it's always part of my content creation pipeline. You can always tesselate shapes by hand, that's what I do at least.

If this is not an option, I do have an old solution to the tesselation problem programmed up. I think it works by corner lopping but I don't recall every detail. It's attached and there's a few pngs in there that shows the sample input and output. The catch is that it's written in matlab so you'd have a tedious amount of porting to do. It will not handle holes, intersecting polygons and is not thoroughly tested (bug reports welcome).


EDIT: Whoops, too late. Glad you got it fixed.

[ImprisonedPride]

That's nifty stuff Alluvian. I've already got this idea in my head just from reading your description. Would be fun to play around with if I ever get the time (that whole college things disrupts my schedule yet again... ARGH).

[tonypa]

trace(square_mc.hitTest(50,50,true)); // returns false

Depends on the version of Flash:
*with F8 it returns false
*with F9 (AS2) it returns true

[sirzooass]

I know it's a year and a half later, but I have a question on this topic. Although the code above does indeed work if a point is clearly inside a polygon, it is a bit flaky when it comes to points that are on the line. How could this code be adjusted to determine if a point is on the line or not? I could do the hitTest thing I suppose, but it would be cool to do it with math. The reason I'd like to do this is because I'm working on a Geoboard and I'd love to use Pick's Theorem to find the area of an irregular polygon.

Here is the code modified for my purposes (not optimized yet). I don't think I mucked it up, but it's a possibility!

function pointInPolyCheck(thisBand, pointX, pointY){
	
	var myPoints = thisBand.pointsClip.myPoints;
	var crossings = 0;
	
	// check point against all of the polygon's lines
	for (var i=0; i<myPoints.length; i++){
		var linePoint1 = thisBand.pointsClip["point"+myPoints[i]];
		var linePoint2 = thisBand.pointsClip["point"+myPoints[(i+1)%(myPoints.length)]];
		
		if (((linePoint1._y <= pointY) && (linePoint2._y > pointY)) || ((linePoint1._y > pointY) && (linePoint2._y <= pointY))){ 
			var vt:Number = (pointY - linePoint1._y) / (linePoint2._y - linePoint1._y);
			if (pointX < linePoint1._x + vt * (linePoint2._x - linePoint1._x)) {
				crossings++;
			}
		}
	}
	
	//trace("crossings:"+crossings);
	if (crossings % 2){
		// point is in polygon
		return true;
	} else {
		return false;
	}
}

Any insight would be greatly appreciated.

Update: I just found this, which is definitely an easier approach. It seems to work great even on complex polygons so I should be all good. Here are examples for a triangle and a square if anyone else is ever looking to figure out the area of a polygon.

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 0;
x3 = 10;
y3 = 10;
area = ((x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3))/2;
trace(area);

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 0;
x3 = 10;
y3 = 10;
x4 = 0;
y4 = 10;
area = ((x1*y2 + x2*y3 + x3*y4 + x4*y1) - (x2*y1 + x3*y2 + x4*y3 + x1*y4))/2;
trace(area);

I suppose I should have started a new topic in the Math forum for this but I can't seem to figure out how to delete this. Sorry