一种两维三角剖分的新算法

提出一种两维三角剖分的新算法,算法首先应用求两维点集凸包的Graham扫描法,求出两维点集的凸包,然后将凸包包含的点从原有点集中去掉,求出剩余点集的凸包.如此递归应用Graham扫描法求出一系列凸包,并将原始区域划分为多个独立的子区域,然后利用本文中提出的方法对2个凸包之间的子区域进行三角剖分,从而实现对整个原始区域的三角剖分.

A New Algorithm of Planar Triangulation

This article presents a new algorithm about planar triangulation that firstly uses R.L.Graham scanning method to get the convex hull of all the points,at the same time deletes the points of this new convex hull from the original point muster,and then again seeks the convex hull of residual point muster.This article uses R.L.Graham scanning method to get a series of convex hulls and divides the original area into many ringed mini-extents,then,uses the algorithm presented in this article to triangulate the area between every two neighborly convex hulls so as to realize the triangulation of the whole original area.