CGAL users discussion list

[Olivier Devillers <>]

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)