CGAL users discussion list

[Olumide <>]

Mariette Yvinec wrote:
> Once the first point has been located, the line_face_circulator of cgal  
> is going to visit only faces traversed by the query
> segment. Thus the complexity is equal to the number of intersection 
> point found and not
> to its worst case which is effectively p*m

I think now I understand what you mean. The tedious part of the 
line_face_circulator's task is to find triangle in which the starting 
point lies. The next triangle can be found by shooting a ray in the 
direction of the end point, and intersecting.locating that edge of the 
starting triangle that is shared with the next triangle path of the ray. 
(Care of course is taken to ensure that the length of the ray does not 
exceed the distance between the start and end points.)

But as you know, I am interested in those edges intersected by the line 
whose start and end is given, and not the triangles it traverses. If 
only there was a line_edge_circulator (oh well, that can be fixed). By 
the way, do adjacent each member triangles in a triangulation share 
edges? I hope so. (If not, I'll have to do something about coincident 
points on half edge pairs.)

One last issue. I would like to know how does the line_face_circulator 
finds the starting triangle (i.e. the one in which the starting point 
lies). Also, I'd like to know if a line_face_circulator can be informed 
of its starting triangle. I'm interested in doing this because as you 
can see from my diagram, the polygon P, is consists of a number of line 
segments, each one of which will perform a line_face_circulation on the 
triangular mesh M. And because the end point of one line segment s, is 
the start of the next line segment t, both segments s and t must lie in 
the same triangle. Thus there is no need for successive 
line_face_circulators to locate a starting triangle.

Thanks again listening to me ramble.

Regards,

- Olumide