CGAL users discussion list

[Marco Aurelio Sterpa <>]

Where is the error in this code?

Arrangement_2 arr = getArrangement(lines);
Arr_walk walk = Arr_walk(arr);
CGAL::zone(arr, lines[i], iterator, walk);


lines is defined as vector<Line_2> lines.

2009/11/2 Marco Aurelio Sterpa <>

I'll try the zone approach and see if it brings sensible improvements, thanks.

2009/11/2 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:

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss