CODEWITHSUNDEEP
image-processinggraphicscomputer-vision
Federico
Federico

Reputation: 576

Non convex uniform grid triangulation

I'm trying to triangulate a non convex uniform point grid in 2D. I would need triangles only in the 8-neighborhood of each point. The problem is that when using vtkDelaunay2D I obtain triangles that violate this condition, resulting (in some configurations) in convex planar figures triangulations even if there exists a non convex triangulation.

The delaunay triangulation usually generates more triangles than necessary in this case, turning a non convex figure into a convex figure in many situations.

I can implement this kind of triangulation, but I do not want to reinvent the wheel. Which algorithm could I use to achieve this?

Thanks in advance!

Upvotes: 1

Views: 359

Answers (1)

Francesco Callari
Francesco Callari

Reputation: 11785

The boundary of the Delaunay triangulation is necessarily the convex hull of the point set. But if your points are on a regular grid, and you only want to admit triangles spanning one grid step only, why bother with Delaunay at all? Just traverse your grid two rows at a time, and triangulate wherever you can.

Upvotes: 3

Related Questions