Re: [Boost-users] [Polygon] Boolean (Clipping) performance

Subject: Re: [Boost-users] [Polygon] Boolean (Clipping) performance
From: Renaud Lepère (renaud.lepere_at_[hidden])
Date: 2013-01-03 04:48:58

On 23/12/2012 07:45, kusogray wrote:
> Hi there,
> I input 200,000 to both polygon set A and B, with each polygon contains 5~8
> points
>
> then do the A^B;
>
> however, this instruction cost about *30 minutes.*
>
> my question is:
>
> I thought the O(n logn) algorithm with n ~ 1,000,000 just cost about at most
> 2 or 3 mins
>
> I checked the XOR AND OR result is correct, but the performance is weird,
>
> did I do anything wrong or misunderstanding?
>

Hello,

  Depending upon the situation all your polygons can generate a lot of 
intersections.  I am not sure but i think that the first step is too 
break all the segments at the intersections (fracture).

  Imagine n triangles rotated by a small angle. The number of 
intersections is in o(n^2). Perhaps you have a similar situation with a 
lot of intersections.

  A possible work-around is to make the union recursively (two by two) ?