CGAL users discussion list

[Andreas Fabri <>]

In case the point set does not change once you start
making your queries:

Sort the convex hull points by angle (with the origin
inside the convex hull).

Find the wedge where your querypoint lies with
a binary search. You still have to check whether
you are outside the convex hull, and then find
the closest point on the convex hull edge.

That is not in CGAL though.

andreas


On 06/09/2011 12:16, Ungermann, Jörn wrote:
> Hello!
>
> I am using a Delaunay triangulation for some interpolation on an irregular
> 2D grid.
> Some points however do not lie within the convex hull. I'd like to use the
> value of the nearest point within the convex hull for those.
>
> I found nearest_vertex() and currently use that to circulate with
> incident_faces() though all adjacent faces of that nearest vertex to
> assemble all
> neighbouring vertices in a std::set and then do some projections to find
> out, whether the closest point is on the edge between the nearest and a
> neighbouring vertex or if it is the nearest vertex itself.
>
> This takes several dozens line of (currently not terribly efficient) code
> for something, which I think might be contained somewhere in the library.
>
> So, is there a function, which calculates for a given point the nearest
> point from within the convex hull of a triangulation?
>
> Thanks and kind regards,
> Jörn Ungermann
>
> --
> Dr. Joern Ungermann
> Institute of Energy and Climate Research - Stratosphere (IEK-7)
> Research Centre Juelich
> Telefon: +49 2461 61-6438


--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri