Handling several points (say 0 and _0.8) outside or inside the polygon P: r...@w P -/ 0 _0.8 0 1 -Bo
--- Den tors 22/4/10 skrev Dan Bron <[email protected]>: Fra: Dan Bron <[email protected]> Emne: Re: [Jprogramming] Polygon containment Til: "'Programming forum'" <[email protected]> Dato: torsdag 22. april 2010 18.06 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
