CGAL users discussion list

[Ben Supnik <>]

Hi Sterpa,

This might not be the computationally fastest way to do it, but  think 
that the Arrangement_zone_2 class will do this for you, sort of.  I 
think it implements a "topological walking" algorithm for ray probes, 
e.g. given a point, then going in a direction, it will walk from face to 
face by iterating the CCB of the face you're in to see what edge or 
vertex you go through to get to the next face.

So...if your faces have a low number of edges in the CCB this can be af 
fast way to go through an arrangement.

An entirely different approach (if the arrangement doesn't change much) 
if you care about "direct hits" of the line and the vertices might be to 
use a spatially indexed container to pull only the vertices within an 
area, then query them one by one.

How well this second approach works would depend on the type of data you 
have.

cheers
ben



Sterpa wrote:
> Given a 2d arrangement of lines, I have to do the following operations:
>
> 1) give a line, get the leftmost vertex lies on this line in the arrangement;
> 2) iterate from left to right on the vertices lie on this line.
>
> I need these operations to implement a more efficient computation of the 
> levels
> of an arrangement. Thanks in advance, best regards.

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: