0

I'm making a C++ project and need to triangulate shape from a given set of points defining the contour of said shape.

The contour is defined in a form of a vector containing x,y coordinates of the points in 2D space. Points are placed in vector in an order that defines how they are connected to form the shape (points[idx] is linked via contour line with points[idx - 1] and points[idx + 1]).

Now I need to generate triangles for that contour in order to create a flat mesh, what algorithm should I use for that problem?

Here is an example, I've got set of black points, can determine shape from order in vector (represented via green lines) and need to generate triangles (red lines). I want to achieve something like in the picture on the left (with proper reflex angles) and not something like picture on the right.

Example

Shrimp
  • 514
  • 5
  • 9
  • 1
    Not sure I completely understand what you're trying to do but you might want to look at [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation). – G.M. Jan 26 '20 at 11:53
  • But would Delaunay triangulation work on shapes that contain reflex angles? My problem is that I have a shape defined by points on the contour of the shape and want to triangulate it in order to create a flat mesh. As an example, let's say I have a contour of something shaped as a "plus sign" (so a set of points on the contour of said plus sign). Wouldn't running Delaunay algorithm generate more of a rhomb shape out of triangles? – Shrimp Jan 26 '20 at 12:17
  • Let me illustrate it, I want to achieve sth like on the left when it comes to generated triangles (for a set of points). Wouldnt Delaunay generate something more like the example on the right? https://imgur.com/a/cvdYdsM – Shrimp Jan 26 '20 at 12:22
  • yes, Delaunay triangulation will (as far as I recall) generate a triangulated convex hull around the points. Ii's difficult to answer the question as it stands. Please edit to specify more clearly the information you have regarding the point set. – G.M. Jan 26 '20 at 12:27
  • Ok, edited the post to include more information – Shrimp Jan 26 '20 at 12:35
  • @G.M. Kind of, didn't know about the term "Constrained Delaunay Triangulation" so it will help me with research. I know I could write my own version and probably will end up doing so, by asking this question I just wanted to make sure there are no easier/more optimised algorithms that someone may know (perhaps something more recent that I did not stumble upon). Anyway, I'll mark that link as an answer, but if someone knows any more algorithms, feel free to post them as I'll gladly look into those too. – Shrimp Jan 26 '20 at 13:05

0 Answers0