Re: [boost] [geometry] [impl] polygon relations [was: area area, length, centroid, behavior]

Subject: Re: [boost] [geometry] [impl] polygon relations [was: area area, length, centroid, behavior]
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-10 14:19:37

Barend Gehrels wrote:
>> Given a black box booleans implementation I can usually tell if it
>> is graph traversal based because it is a) slow 

> A polygon intersection/union/difference algorithm consists of:
> - finding the intersections
> - gathering the results
> 
> The last one can be done by graph traversal, of which the performance
> is 
> not the problem, vertices are visited only once. Finding the
> intersections is the challenge and the sweepline can be a useful
> utility there.

Well, you are looking at the big-O.  Traverse a linked list and traverse a vector and you will find that there is a significant constant factor runtime penalty.  The graph is very much like a linked list, I use vectors to store my data and avoid the linked list runtime penalty for the majority of code.
> 
>>  b) uses too much memory

> The list of intersections is in normal cases very short and will even
> in extreme cases not exceed the number of vertices of the polygons.
> So I 
> don't think of it as "too much"

Well, I have to assume people will run the algorithm on data that barely fits in memory on a 256 GB memory monster of a machine.  Space is time, ask Einstein.  A linked list uses four times more memory than a vector.  I store the vertices of partial polygons in linked list form only while they are currently intersecting my sweepline and then copy them out into vector when they are closed by the algorithm, minimizing the ammount of data stored in that form.  In the graph algorithm the entire data set is stored in that form, and that means several times more memory is needed to do the same work.  You fall out of cache, your performance goes way down.  You fall out of physical memory and you might as well kill the job.  Consuming less memory and having less traffic allocating and deallocating are the first and second most important things to consider when optimizing an algorithm for the constant factor.  Because it impacts which data structures you choose, it also impacts which algorithms you choose.

>> and c) has O(n^2) runtime associating n holes to an outer polygon
> Can you give a reference to this calculation? I'm not convinced. A
> hole either:
> - disappears by intersection (so will be part of the exterior
> boundary) 
> - stays in the polygon because included by both input polygons, or
> falls outside, you indeed have to determine this but this is O(n)
> where n is a hole, and this probably can be done while traversing it
> above. - in case of a union new holes can be formed, lying in the
> union 

Two of the old internal implementation I replaced had this problem.  I've also observed it in commercial tools.  It can be made O(n), but often this is neglected because people assume it won't be a problem.  It also isn't obvious how to make it O(n) with the graph traversal algorithm.  If you subtract all polygons from the bounding box of the entire set you have a heck of a lot of holes and nothing in the graph to help you.

> There are:
> - Sutherland-Hodgeman, only convex
> - Weiler-Atherton, the first graph traversal one
> - Vatti, used in GPC (I now saw that they indeed call it scan beam
> although I think sweep line is the more general term)
> - Leonov-Nikitin, polyboolean *(still graph traversal, only integer?)
> - Greiner-Hormann (still graph traversal) (1998)
> - Kim/Kim (modified version of the above) (2006)

Can you send me a reference for Vatti?  I've seen polyboolean before.  It is limited to 22 integer bits of precision or some such, which is kind of odd.

> * is fast but I quote here:
>> /PolyBoolean/ uses John Hobby's rounding cell technique to avoid
>> extraneous intersections and is therefore completely
>> robust. /Boolean/ also rounds the intersection points to the integer
>> grid, then repeats until no new intersection points are found.
> Are you using one of the above or another one?

I am using my own.  It is probably similar to John Hobby, I always round downward within a single integer grid.  I don't repeatedly scan because the algorithm is carefully crafted to not create new intersections in the first pass as I describe in another mail posted earlier today to this list.  Also, it is a work in progress.

Regards,
Luke