CODEWITHSUNDEEP
cgal
Rapidturtle
Rapidturtle

Reputation: 237

Get all points with integer coordinates inside the convex hull of a CGAL triangulation

Given a CGAL triangulation, I would like to find all points with integer coordinates inside its convex hull.

I know we can iterate through all integer points and find their locations by locate(). But that would not be efficient. Is there a way we can find points inside a triangle of the convex hull? Is that an effective way to get lattice points inside a given triangle (vertices are all on lattice points)?

Upvotes: 0

Views: 800

Answers (2)

BrunoLevy
BrunoLevy

Reputation: 2633

A simple possibility is to compute the 3D Delaunay triangulation of your points, then for each finite tetrahedron in the Delaunay triangulation, you iterate on the integer points in the bounding box of the tetrahedron, and reject the ones that are outside the tetrahedron. Testing whether a point q belongs to a tetrahedron (p1,p2,p3,p4) can be done by testing the orient3d(q,pi,pj,pk) for each facet (i,j,k) of the tetrahedron.

A slightly more efficient possibility uses the Bresenham algorithm to directly generate the points in the tetrahedra with integer coordinates (it is more error prone and difficult to implement for a not-so-spectacular speed gain, I experimented both and I am now using the first solution). The second solution will be better if your grid size is very small as compared to the dimension of the tetrahedra.

Upvotes: 0

lrineau
lrineau

Reputation: 6294

You could iterate over the all the integer points inside the bounding box of the triangulation, and use locate() smartly. For a query to locate(), store the returned cell or face handle (I still do not know if your question is about 2D or 3D triangulations). Then, use that handle as the hint parameter of the locate() function. If your queries are close to each other, consecutive locate() will return very fast.

Upvotes: 0

Related Questions