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
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
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
- 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
- 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk