If all angles of the polygon are convex then if the areas of triangles formed by adjacent angles of the polygon and the point in question are all positive (or negative, depending on which way you go around) then the point is enclosed within the polygon.
On Fri, Apr 16, 2010 at 10:58 AM, Dan Bron <[email protected]> wrote: > Boyko Bantchev wrote: > > This is much harder than finding whether a point is within a > > polygon. > > Agreed, but these are my constraints (it's a long story). But on the up > side, there are very few polygons but a gazillion points. So don't have to > calculate bounding rectangles very often. > > > Do you assume that the polygon is non-intersecting? > > Yes. > > > 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. > > I was thinking maximum (shared) area, yes. And uniqueness doesn't matter > -- the only purpose of the rectangle is to minimize the number of times I > need to do the full polygon containment, so even a good approximation is > fine. > > Basically, the approach is this: > (1) A new polygon is defined > (2) I use J to calculate the minimal circumscribed (C) and maximal > inscribed (I) rectangles for this polygon > (3) I set up the following rules in the other tool: > a. For all points outside of C, return 0 > b. For all points inside of I, return 1 > c. For all points inside of C but outside of I, use J to > determine whether the point is truly in the polygon, and return its result. > > This is actually a good opportunity to show off J (the use case is pretty > cool). > > -Dan > > -----Original Message----- > From: [email protected] [mailto: > [email protected]] On Behalf Of Boyko Bantchev > Sent: Friday, April 16, 2010 11:18 AM > To: Programming forum > Subject: Re: [Jprogramming] Polygon containment > > 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
