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