Thanks guys. Boyko and Henry's caveats are definitely worth considering in the general case, but do not occur in my use case.
Let us agree that a point on an edge or vertex is "outside" the polygon, that polygons never share an edge or vertex, and that the polygons are not degenerate (I think the term is "convex"). Can someone give me a short piece of code that will allow me to plot polygons (represented by an Nx2 array of numbers) on a graph? Ideally, I could pass in multiple polygons (a vector of boxes, each box containing a polygon), and have them plotted simultaneously. This will make it easier to test my models. -Dan -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Henry Rich Sent: Friday, April 16, 2010 2:42 PM To: Programming forum Subject: Re: [Jprogramming] Polygon containment 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
