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: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-10 16:17:23

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