Boyko has the right questions here, and I would add only that the devil is in the details on this problem, at least in some applications. One application is when the polygons tessellate a surface, and you are trying to figure out which polygon a point is in. Then you need to make sure that your calculation
0) handles a point that is exactly on an edge, and tests 'inside' for one of the polygons sharing the edge, and 'outside' for the other; 1) handles a point that is exactly on a vertex, as the application needs. 2) handles degenerate polygons, especially ones that represent a non-connected region by having two identical edges in opposite directions. In addition, it might be important that the algorithm produce the same results when the points and polygons are all translated; and you need to decide what to do about ill-formed polygons. The precision issues arising in this calculation are not easy, and in some cases the underlying representation of the surface is chosen with a view toward making these calculations robust. Henry Rich Boyko Bantchev wrote: > On 16 April 2010 18:01, Dan Bron <[email protected]> wrote: >> (2) ............. >> the maximum inscribed rectangle in that polygon. > > Dan, > > This is much harder than finding whether a point is within a > polygon. Also, what does it mean a `maximum' rectangle? > With respect to its area? In any case, the solution is not > unique and probably not very useful. > >> (3) ................. The inputs is the >> polygon and the points, and the output is a boolean >> per point, which indicates whether the point is >> "truly" in the polygon ............. > > Do points on the polygon's boundary count as in or out? > > Do you assume that the polygon is non-intersecting? > > Regards, > Boyko > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
