CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 02/09/2015 06:48 AM, Илья Палачев wrote:
> Hi,
> There is a vector of 3D points, and the hull of them is constucted:
> std::vector<Point_3> points = ...;
> Polyhedron_3 hull;
> CGAL::convex_hull_3(points.begin(), points.end(), hull);
> After that I need to know which vertex in hull correspond to points[i]
> and vice versa.
> Is there any API to set the initial ID of point/vertex before the
> construction of hull and then to get it after the construction?
> The staightforward method is to look through the vector of vertices and
> find the closest vertex to the given point.
> But this method needs O(N ^ 2) of time, or O(N * log(N)) if we do
> something like preliminary sorting the array of hull vertices in the
> lexicographical order.
> But is there any natural way to do that?
> --

Unfortunately with the current API it is not directly possible.
However, if you use the 3D triangulation package, you can set indices
for each points [1] extract the convex hull by looking at all the cells 
incident to
the infinite vertex.

Note that the function convex_hull_3_to_polyhedron_3 [2] will not port
the indices to the polyhedron vertices but you can modify yourself the
function update an id field of the vertices of the polyhedron (the
function is very simple).


Sebastien.

[1] 
http://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3SettingInformationWhileInserting
[2] 
http://doc.cgal.org/latest/Convex_hull_3/group__PkgConvexHull3Functions.html#gaa87070e950e63e3a7395a2fb14c7ea7c


> Best regards,
> Ilya Palachev