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) ?