
Boost : 
Subject: Re: [boost] [geometry] [impl] polygon relations [was: area area, length, centroid, behavior]
From: Barend Gehrels (barend_at_[hidden])
Date: 20090310 09:00:33
Hi Luke,
We've corresponded about this offlist 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
polygonclipping 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 BentleyOltmann, 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 selfintersecting polygons or arbitrary directions
or winding rules should be handled
There are:
 SutherlandHodgeman, only convex
 WeilerAtherton, 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)
 LeonovNikitin, polyboolean *(still graph traversal, only integer?)
 GreinerHormann (still graph traversal) (1998)
 Kim/Kim (modified version of the above) (2006)
 ...
Some are modifications of each other. Most ones are in fact modified
WeilerAtherton 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk