[Jprogramming] Polygon containment

[Dan Bron]

Thanks for everyone's contributions to this thread.  Right now, I am working through the integration of J with the other tool, so I haven't studied the suggestions carefully yet.

Even so, I'm fairly convinced the various algos in this thread satisfy my requirements.  But I understand that there is some debate regarding the best approach, and the conclusion depends on some details of the problem.  So though I have what I need, for the sake of the debate (presuming the participants are still interested), here are the details as far I know them:

	1.  Lots of points, few polygons.
	2.  The polygons are convex.
	3.  There can be more than one polygon at a time, but 
	    they won't overlap or touch.
	4.  Some pre-processing has been done, so you know the
	    points are inside the minimal circumscribed 
	    rectangle, but outside the maximal inscribed 
	    rectangle (if that helps).
	5.  I don't know what I want if the point is on an 
	    edge or vertex, but I think it will suffice to 
	    count these cases as "outside" the polygon, or 
	    flag them as "different".  Counting them as 
	    "inside" is ok too, if that makes it easier.  
	    But the answer must be consistent in all cases.

And some implementation details (I arbitrarily selected these, and am open to changing them):
	
	6.  The solution is a dyadic verb.
	7.  Polygons are represent by Nx2 arrays of 
	    floats.  This is the LHA of the verb.
	8.  Points are represented similarly as a vector
	    of 2 floats.  The RHA of the verb is an 
	    (arbitrary) array of points.
	9.  As a consequence, the effective rank of the 
	    verb is "2 1, though it would be nice to not
	    actually have to apply the verb at this rank
	    (for performance reasons).
	
There may be other complications or edge cases I haven't covered, but in those cases feel free to make simplifying assumptions.  The use case is "real-world", so the most of the abstract theoretical complications probably won't be applicable.  

OTOH, if you're hungry for complications, the polygons actually map to physical locations, so the curvature of the Earth is a consideration (though I intend to ignore it, at least initially).

-Dan

PS:  The goal is fast containment-detection, but this must be balanced against code complexity.  Remember that the vast majority of points will be filtered out by the pre-processing, J's workload won't be immense.  

PPS:   I scanned the link Boyko hinted at, and it highlighted a case I hadn't considered.  Specifically, it said that in some applications, the central pentagon of a 5-pointed star polygon is considered "outside" that polygon.  

This is not the case in my application.  More specifically, if the input is a 5-pointed star, then its central pentagon is not a hole, and any points that are contained in that pentagon are also contained in the star.

Contrariwise, if the input was 5 individual isosceles triangles that happened to have shared vertices (though this cannot happen in my use case), and a point fell within the pentagon their bases happen to describe, that point would be considered outside each triangle.