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
