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