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.
Barend Gehrels wrote: 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.
That's what I'm curious about. Can you describe your approach in more detail? I'm left guessing based upon my knowledge of other implementations. What data structure do you use for the graph? Is it vectors? Most people would implement the graph data structure such that each node corresponds to one polygon vertex, is dynamically allocated and contains a vector or linked list of pointers to other nodes. It should be possible to implement a better data structure than that, but I wouldn't expect to see it done. Regards, Luke