Subject: Re: [boost] [geometry] [impl] polygon relations [was: area area, length, centroid, behavior]
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-03-10 15:14:21
> 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.
We're using vectors all the time (actually it is flexible, deque's are
also possible). I also implemented the intersection list using a vector.
Our approach probably is not that different.
> 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.
See my answer above, not using LL or DLL, just vector.
> Can you send me a reference for Vatti?
Vatti, B.R. "A Generic Solution to Polygon Clipping"; Communications of
the ACM, 35(7), July 1992, pp.56-63.
As far as I know it is not directly/freely available.
> 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
OK, you might publish it then, might be a valuable addition :-)
I still have the feeling it is specific to integers or floating points
in a small extent, and not to doubles in arbitrary coordinate systems as
I'm always using... However, no problem, the more complimentary it is,
the more possibilities for merging.