CGAL users discussion list

[Mariette Yvinec <>]

Olumide wrote:

> Olumide wrote:
>
> > Shortly after writing that email, I realized that the 2D Arrangements 
> > package is probably what I need.
>
>
> I've been reviewing the 2D Arrangements package and the 2D 
> Intersection of Curves package.
>
> I understand it, the 2D Arrangements package creates an arrangement of 
> lines, to which a number of new lines may be added. The 2D 
> Intersection of curves package on the other hand, requires a list of 
> line segments (which is in effect an arrangement of lines), and finds 
> all points of intersection between them. If this is so, these two 
> packages fall short of what I would like to do. Just as recap, I am 
> trying to find the the points of intersection of a complex, non 
> self-intersecting polygon, P, and an irregular flat (triangular) mesh 
> structure, M. Refer to the diagram 
> http://i17.photobucket.com/albums/b52/videohead/PolyMeshIntersect.jpg 
> . the output should be a new polygon, with intersection points 
> consistently added to it i.e. not haphazardly, such that an imaginary 
> ant (lets call him Billy) can walk round the augmented polygon by 
> going from one vertex to the next, so that he returns to the starting 
> vertex. (Can anyone think of a why did the ant walk round the polygon 
> joke? :-) ...)
>
> Here is my difficulty with the 2D Arrangements and 2D Intersection of 
> Curves packages:
>
> 1. If the line segments of M and P are presented to either package as 
> an arrangement, or a list of line segments, functions exist for 
> computing the intersections of M and P. However the problem is that 
> the computed intersections cannot be easily added to P, which is in 
> fact a list of vertices. (If vertices are added haphazardly, the 
> imaginary ant can make a round trip without going back and forth.)
>
> 2. I've also considered creating an arrangement of lines, or a list of 
> segments from the M (alone), and then insert each line segment of P 
> into the arrangement, or the segment list, then check for 
> intersections. Adding the computed intersection point to P shouldn't 
> be too difficult, however examining all line segments of M, as many 
> times as there are the number of line segments of P seems rather 
> inefficient. Worse still, every line segment of M will be tested with 
> every other even line segment of M, though their intersection points 
> are already known, and not required. Same happens if all line segments 
> of P are tested with all line segments of M, as suggested above. There 
> is no need to test for intersections between line segments of the same 
> entity.
>
> Does this rant betray my lack of understanding of CGAL and 
> computational geometry? Is there another package that can do the job 
> efficiently? Please enlighten the noob.
>
> Thanks,
>
> - Olumide

I persist to say that calling the line_walk member fonction of the 
triangulation for each edge of the polygon
will do the job.  For each edge pq, locate point p,
start the circulator from the face containing p and increment it until  
the face f' containing q. Start from f'for the
next edge. Each  pair of consecutive traversed faces gives you a vertex.