Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net