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: 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