Re: [Boost-users] [review] intrusive container comments

From: Olaf Krzikalla (krzikalla_at_[hidden])
Date: 2007-03-23 09:36:18

Hi,

Thorsten Ottosen wrote:
>>>What I would like to know is if typically all objects is 
>>>inside intrusive containers; also for the use of 2,3, or 4 simultaneous 
>>>containers.
>>
>>I wouldn't say so. In fact, at least one triangulation algorithm needs 
>>to maintain and iterate over a list of all concave vertices of a polygon 
>>again and again (the list becomes smaller during the triangulation 
>>process). But usually in a typical polygon there are much more convex 
>>vertices. Thus just marking the vertices with a flag was no option, 
>>because you'd have to iterate over the whole set of vertices just to 
>>(re)find the concave ones. A "std::list<Vertex*> concaves;" could help 
>>and in usual cases generate less memory overhead than the intrusive 
>>approach.  However, the triangulation algorithm also needs to detect, 
>>whether a given vertex was concave. By using the linked() property of 
>>the intrusive node used by the "concave ilist" it was possible to have a 
>>very fast test for that. IMHO a typical example of the classic space vs. 
>>time tradeoff.
> 
> 
> Ok. How badly would the algorithm perform if these two types of test 
> where only O(lg N) ?
Hmm, from a quick glance I can definitely say it raises from O(m*n) to 
at least O(m*n*lg(n)), maybe even worse (m being the number of all 
veritces in a polygon, n being the number of concave vertices in it).

Best Olaf