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.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
