如何在没有随机内点的情况下对多边形进行三角测量?

gue*_*rda 3 language-agnostic algorithm geometry computational-geometry

我想创建三角形预定义的多边形.我的要求是我不想在这个多边形内部创建随机点,以便使用Delaunay三角剖分算法对其进行处理.
多边形可以是凹的或凸的.

我完全可以使用Delaunay三角测量,但我不想在多边形内部创建随机点.如果我可以在此多边形内创建尽可能少的点,那将会更好.
我想尽量减少使用三角形的数量.

我怎样才能建立这个?

评论:这更像是一种与语言无关的东西,我想知道如何自己实现这一点.

Ree*_*sey 5

您可以使用耳剪或单调多边形.这两种算法都不会引入额外的分数.

(如果选择形成单调多边形,则单调多边形是凸的,可以直接分解为三角形扇形.)