Re: [Boost-users] [Boost.Polygon] support for polygons with holes

Subject: Re: [Boost-users] [Boost.Polygon] support for polygons with holes
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2011-09-13 22:33:48

Mika Heiskanen wrote:
>         Björn Piltz wrote:
>         >
>         > 1.
>         > Is there an easy(and computationally cheaper) way to check
>         if two
>         > simple polygons intersect?
>         > other than: !boost::polygon::empty(a & b). If not, is such
>         > functionality planned?
>         
>         
>         You should check if their bounding boxes intersect first and
>         then do the expensive check only if there is intersection
>         between the bounding boxes.

>Personally I would expect a good polygon library to provide a function
>named intersects, which would implement an optimization like the one
>mentioned above, plus specialized code which would interrupt polygon
>intersection calculations as soon as one has been found.

It is the application programmer who is in the best position to know whether the bounding box check is a net win.  Usually it is, but if they are, for example, checking the results of a spatial query that already ensures that the bounding box check would return true then they obviously don't want to pay runtime for the redundant check.  You are, of course, correct that a faster intersects check than !boost::polygon::empty(a & b) could be implemented, however, my focus has been toward general algorithms that solve broad classes of problems.  Even a&b is just an instantiation of a much more general algorithm that solves also connectivity extraction and map overlay.  Given a library that already does !boost::polygon::empty(a & b) would you rather get an alternative method of accomplishing the same thing that is a constant factor faster or something like voronoi diagram of line segments that solves a broad set of problems that the library currently does not address at all?

Regards,
Luke