Re: [Boost-users] [Polygon] Test among 3 libraries

Subject: Re: [Boost-users] [Polygon] Test among 3 libraries
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-09-07 19:14:12

On Sun, Aug 1, 2010 at 7:25 AM, TONGARI <tongari95 <at> gmail.com> wrote:
> Hi,
> I just modified a test program taken from AGG's examples to test the polygon
> clipping capability of following libraries.
> *Boost.Polygon
> *GPC
> *Clipper
>
> Here are some observations:
> 1) The proccesing speed (fastest to slowest): Clipper > GPC > Boost.Polygon
> 2) With "xor", although the results seems the same, they have different
> countours numbers (Clipper the least).
> 3) Boost.Polygon has a strange behavior that it sometimes produces erroneous
> vertical lines within the polygons.
> In this example, with "or" operation you'll see that.
>
> I put the test files here:
> http://tinyurl.com/2axoqxc
>
> Anyone who wants to compile it will also need AGG and Clipper on your
> computer.

Thanks for taking a look at my library and performing this comparison.

I've never seen a comparison with clipper before, I've never heard of clipper and would like to learn more.  Can you provide a link or reference?  I found a sourceforge site with minimal description of clipper, but it left me with a lot of unanswered questions.  I was able to access your code through the tinyurl, but I haven't followed up on it yet.  Was it possible that the "erroneous" vertical lines within the polygons were the hole fracturing lines that I insert if your result type is polygon_concept rather than polygon_with_holes_concept?

As far as the number of contours produced.  Boost.Polygon always provides the maximum number of outer contours and the minimum number of inner contours.  Polygons touching at only one point are reported as separate contours.  Holes touching at only one point are reported as a single contour.  I would argue this is the most correct policy to have.  I generally see mismatch between contour count and vertex count for different polygon clippers on the same data even before issues related to numerical error are introduced that can muddy the water still further.  Such differences do not necessarily indicate there is a problem.

As for performance, I expect GPC to be faster than Boost.Polygon for small test cases.  It is a little tricky to conduct performance comparisions between different polygon clipping libraries because performance can depend quite a bit on input.  My primary goal in the design and implementation of the Boost.Polygon any angle polygon clipping (and related) capability was optimal or near-optimal algorithmic time and space complexity to allow the algorithm to scale to extremely large inputs gracefully.  If a simpler and clearly sub-optimal algorithm (like GPC) is faster for small inputs it doesn't necessarily mean there is anything wrong with the implementation of Boost.Polygon.  I have improved runtime for the any angle capability significantly since I originally got it correct.  Based on the performance study I did (see documentation) there is a ~10X upper bound on improvement in the constant factor for the any angle implementation if you use the efficiency of the similar manhattan capability as a lower bound.  Any improvement beyond that implies a completely new algorithm.

By the way, I would have responded sooner, but I haven't been monitoring the boost-users list.

Thanks again,
Luke