CGAL users discussion list

[Simon Giraudot <>]

Le 28/10/2015 12:05, Olivier Devillers a écrit :
> Le 28/10/15 11:54, Simon Giraudot a écrit :
> > Hello,
> >
> > I am trying to access the nearest simplex (vertex, edge or facet) of 
> > a query point lying *outside* of the convex hull of the 3D Delaunay 
> > triangulation (this nearest simplex is thus adjacent to at least one 
> > infinite cell).
> >
> > It seems difficult for several reasons:
> > * The infinite cells of a DT do not have a geometric meaning: 
> > locate() applied to an outside point returns "one" infinite cell, but 
> > it does not means that the point projects on the finite facet of this 
> > cell;
> > * The nearest_vertex() can give a hint but the nearest vertex of an 
> > outside point is not necesseraly on the convex hull.
> >
> > Is there a simple/efficient way to do that?
> My suggestion:
>
> locate(p) return an infinite cell t;
>
> while true
> {
>   let t=abci  (where i is infinite vertex)
>   v = oriented_normal(abc)
>   if orient(a,b,p,b+v)=cw { t=t->neighbor(through abi); continue;}
> if orient(b,c,p,b+v)=cw { t=t->neighbor(through bci); continue;}
> if orient(c,a,p,a+v)=cw { t=t->neighbor(through aci); continue;}
>   // the nearest facet on convex hull is abc
>   break;
> }
> ----------
>
> in other words, walk on the convex hull facets until p project on the 
> facet
> (to be adapted to degenerate cases, of course)
Okay, it took me some time to figure out how to deal with edges/vertices 
but it seems to work fine now.

Thanks very much!

--
Simon Giraudot, PhD
R&D Engineer
GeometryFactory - http://geometryfactory.com/