I'm trying to programatically generate a mesh, given the vertices of a polygon, which is contained within that polygon. For example, starting with these points:

points solo

I would want to generate a mesh similar to this:

points preferred

My first port of call would be a Delaunay triangulation, but having implemented this, I came up against the problem that this was not contained within the polygon, i.e. it produced a mesh like this:


My question then is, is there either an algorithm which produces the desired result rather than the Delaunay result (because I can't find one online), or a modification that I can make to the Delaunay triangulation algorithm that will fix this?

I'm using the Bowyer-Watson algorithm, by the way. Thank you!

  • 1
    \$\begingroup\$ Presumably you reviewed common polygon triangulation methods and tried applying either ear clipping or monotone triangulation to your case? Where did you run into trouble? \$\endgroup\$
    – DMGregory
    Jul 5 '20 at 13:01
  • \$\begingroup\$ That... completely escaped me. I'll take a look through it, thank you very much. \$\endgroup\$
    – jumbot
    Jul 5 '20 at 13:34

You must log in to answer this question.

Browse other questions tagged .