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: Barend Gehrels (barend_at_[hidden])
Date: 2009-03-10 09:00:33

Hi Luke,

We've corresponded about this off-list as well, so here a short answer 
(in the end not that short...).

I propose to note in the subjectline that discussions are about 
implementation details, as these, to make it clear for "users" that they 
might skip these ones.

> 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.

As I didn't finish the full polygon intersection yet, (we have 
polygon-clipping against a rectangle) for me finding intersections was 
no issue until now. Will look at the sweepline but also at monotonic 
sections and indexing. And benchmark.

>  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"

> 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

> Please note, Barend, I'm not criticizing you, I'm criticizing an algorithm invented in the '70s.
Pythagoras' theorem is 2500 years old. You refer to Bentley-Oltmann, it 
is from 1979. Weiler is from 1980. The age of an algorithm is not a 
measure of its usability.

Polygon/polygon relating algorithms (intersection, union, etc) have to:
- handle convex as well as concave polygons
- handle holes
- handle floating point
- handle collinear or equal segments, horizontal/vertical cases
- handle "degenerate cases" (some authors call it like that but a 
segment intersecting / tangenting a vertex, i.m.o it is not degenerate)
- not produce degenerate lines
- be fast and flexible
- you might add that self-intersecting polygons or arbitrary directions 
or winding rules should be handled

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)
- ...
Some are modifications of each other. Most ones are in fact modified 
Weiler-Atherton versions, therefore I still refer to it as such, I've 
made modifications as well.

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

> That's sort of my goal, actually.
>   
Mine too! So we might be happy to cooperate.

Regards, Barend