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
Hi Luke,
> 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.
Regards, Barend