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-13 12:59:27

>> It looks like my algorithm is most closely related to Vatti, but I
>> have improved on it in several ways.  So far I can only find
>> references to people who are improving on the graph based algorithm
>> and performing all-pairs brute force line intersection.  Do you know
>> of any work that improves directly on Vatti rather than merely
>> comparing yet-another-graph-travering algorithm to Vatti?     
>> 
> Thought I already mentioned that, GPC:
> http://www.cs.man.ac.uk/~toby/alan/software/
> <http://www.cs.man.ac.uk/%7Etoby/alan/software/>
> 
Oh, I didn't recognize the acronym.  I've looked at GPC before when I was trying to find a free alternative to writing my own booleans 2+ years ago.  Their license is not free.  Revisiting their web site their feature set looks oftly familiar.  Trapezoidization and holes, Vatti based for sure.  I'll need to look into their publications (do they have any) and be sure to give them their deserved citation in my paper.

They cite Leonov's boolean comparison which shows them in a very poor light compared to polyboolean.  Their runtime is not scaling very nicely in his benchmarks.  Also the scale of his benchmarks is very small.  You can just barely start to see the runtimes of those two libraries hit the wall.  I'll have to benchmark GPC and PolyBoolean myself before I can say more.  It looks like in 1998, however, their line intersection at least was suboptimal, suggesting a naïve implementation of Vatti.  They also lack keyholing output, which is a hard requirement of just about 50% of use cases, including mine.

Thanks for the link!
Luke