问一个算法的问题

Crazy123

给定一个封闭多边形的各个顶点坐标，然后生成一系列组成此多边形的三角形面片，请问有没有什么算法？

secondage

如果是凸多边形的话，那么只需要用任意一个顶点连接其他顶点就可以了
如果是凹的，就切割成几个凸的来做吧

seer

看看RealtimeRendering,有现成算法，不过不是很详细……

fujingqiu

1、任意选择相邻的三个点。
2、计算这三个点的中点，看他在不在这个多边形内。
3、如果在，记录这个三角形，并把中间的顶点删除。
4、如果还有多于三个的顶点则继续选择。

ixnehc

可以试试这样:
找到这个polygon的一条切割线段:
切割线要满足这样的条件:
1.以polygon上任两点为端点
2.不与polygon上任何线段相交
用切割线段将polygon分成两个子polygon,再对子polygon调用上述过程.直到子polygon只有三个顶点为止.

具体可以再优化.不是非要递归调用.

fujingqiu

你看清楚一点好不好，重点在外部的时候不删除，继续。

bigbook2000

你这个问题是一个标准数学问题，在三维GIS系统中有着广泛的应用，通过离散点生成不规则三角网（Triangulated Irregular Networks，TIN），可以参考相关书籍（Delaunay[1934]三角形， Lawson[1972]最大化最小角原则， 各大书店都有）。

我说其中的一个方法思路，一般生成的三角网都不会是唯一的，我们只要建立一种就可以了。先任意取2个最近点组成一个线段，然后搜索第三个点，使之夹角最小，距离最短，组成一个三角形，然后依次向外扩张。

Crazy123

fujingqiu不好意思看错了，早上起来头晕晕的一下就看错了。bigbook2000，你也对三维GIS系统有研究？