This seems like it ought to be obvious, but I¹m not seeing it. I¹m interested in the problem of deciding whether a point is inside/outside a polygon. Given the vertexes of a polygon, there are a several of ³classic² ways known to compute this test (eg for graphics applications) . Furthermore, it¹s a commonplace computational optimization, to enable quicker culling of points far from the polygon, to construct a bounding box (eg a rectangle aligned with the axes) so that any point outside the box is certainly outside the polygon (eg box corner coordinates are min/max of the polygon¹s). I¹m wondering: how hard is it to compute a sort of ³conceptual dual², a ³binding box², such that any point inside the box is certainly inside the polygon? We can restrict the problem to non-self intersecting polygons, but they may have zigzagging concavities. Perhaps easier would be to use circles, maybe some kind of projective inversion?
This is related to a geometry problem I've worked on: Define a continuous function F that maps the set S of [simple closed curves in R^2] to R^2, such that F(C) is interior to C for all C in S. One solution has two steps for a given C in S: 1) March into C from the boundary -- stoping when two points touch -- to get a tree T of arcs. (Which will be a tree of line segments when C is a polygon.) 2) Now there exists a unique point p of T whose average distance to all points of T is minimum. Now define F(C) = p. This doesn't sound extremely hard to compute when C is a polygon. ----- As for Marc's question, I don't see an easy way to find a radius eps around p such that N_eps(p) lies interior to C. But maybe it's not that hard. --Dan Marc wrote: << This seems like it ought to be obvious, but I’m not seeing it. I’m interested in the problem of deciding whether a point is inside/outside a polygon. Given the vertexes of a polygon, there are a several of “classic” ways known to compute this test (eg for graphics applications) . Furthermore, it’s a commonplace computational optimization, to enable quicker culling of points far from the polygon, to construct a bounding box (eg a rectangle aligned with the axes) so that any point outside the box is certainly outside the polygon (eg box corner coordinates are min/max of the polygon’s). I’m wondering: how hard is it to compute a sort of “conceptual dual”, a “binding box”, such that any point inside the box is certainly inside the polygon? We can restrict the problem to non-self intersecting polygons, but they may have zigzagging concavities. Perhaps easier would be to use circles, maybe some kind of projective inversion?
If your polygon is re-entrant equilateral, with vertices alternately on circles of large and small radius, then clearly no useful "binding box" can exist. WFL On 10/7/12, Marc LeBrun <mlb@well.com> wrote:
This seems like it ought to be obvious, but I¹m not seeing it. I¹m interested in the problem of deciding whether a point is inside/outside a polygon. Given the vertexes of a polygon, there are a several of ³classic² ways known to compute this test (eg for graphics applications) .
Furthermore, it¹s a commonplace computational optimization, to enable quicker culling of points far from the polygon, to construct a bounding box (eg a rectangle aligned with the axes) so that any point outside the box is certainly outside the polygon (eg box corner coordinates are min/max of the polygon¹s).
I¹m wondering: how hard is it to compute a sort of ³conceptual dual², a ³binding box², such that any point inside the box is certainly inside the polygon?
We can restrict the problem to non-self intersecting polygons, but they may have zigzagging concavities.
Perhaps easier would be to use circles, maybe some kind of projective inversion?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The reason a "bounding box" works so much better than a "binding box" is that the intersection of boxes is a box, but the union of boxes isn't, so the bounding box is just the intersection of all (grid-aligned) boxes that bound, while the union of binding boxes isn't a box, but is the entire interior. Andy On Sun, Oct 7, 2012 at 3:30 PM, Marc LeBrun <mlb@well.com> wrote:
This seems like it ought to be obvious, but I¹m not seeing it. I¹m interested in the problem of deciding whether a point is inside/outside a polygon. Given the vertexes of a polygon, there are a several of ³classic² ways known to compute this test (eg for graphics applications) .
Furthermore, it¹s a commonplace computational optimization, to enable quicker culling of points far from the polygon, to construct a bounding box (eg a rectangle aligned with the axes) so that any point outside the box is certainly outside the polygon (eg box corner coordinates are min/max of the polygon¹s).
I¹m wondering: how hard is it to compute a sort of ³conceptual dual², a ³binding box², such that any point inside the box is certainly inside the polygon?
We can restrict the problem to non-self intersecting polygons, but they may have zigzagging concavities.
Perhaps easier would be to use circles, maybe some kind of projective inversion?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
participants (4)
-
Andy Latto -
Dan Asimov -
Fred lunnon -
Marc LeBrun