CGAL users discussion list

[Andreas Fabri <>]

 wrote:
> Hi,
> i was wondering if there is a way to implement an Interval Skip List for faces
> in a triangulation based on an x-y interval from another point (lets say p1)
> that is not included in the triangulation?
> I'm calculate a delaunay_triangulation_2 of a terrain and have another point
> that is not in the triangulation itself but within the convex hull of the
> terrain. Now i would like to search for the face/triangle in which the p1 
> would
> fall in the plane view of the triangulation. Currently i'm checking each
> triangle (only in x-y) if it contains p1 in it (i do that with a point in
> polygon check). The problem is i have to loop through each triangle to find a
> "match". I would like to reduce the possible triangle candidates by an 
> Interval
> Skip List.
> Hope i explained this in an understable way...


You mean, given a triangulation with 3D points, but the projection traits 
class
you want for a point p=(x,y) locate the face on that p gets vertically
projected.

The method  Triangulation_2::locate(Point)  does exactly that, but maybe you
want to do something more elaborate.

andreas