Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!csd4.csd.uwm.edu!bionet!agate!shelby!polya!anaconda.stanford.edu!sumane
From: sumane@anaconda.stanford.edu (Thilaka Sumanaweera)
Newsgroups: comp.graphics
Subject: Re: Polygon Triangulation
Message-ID: <11820@polya.Stanford.EDU>
Date: 16 Sep 89 17:05:12 GMT
Sender: USENET News System <news@Polya.Stanford.EDU>
Reply-To: sumane@anaconda.stanford.edu (Thilaka Sumanaweera)
Organization: Stanford University
Lines: 17

Assuming the polygon vertices are ordered so that
they can be treated as contours, one can use
Delaunay Triangulation to divide both convex and concave
polygons into triangles. (This can be extended with minor
modifications for non-simple (self-intersecting) polygons.)

Delaunay triangulation gives a set of triangles having
the polygon-vertices as corners and whose union is the
convex hull of the polygon-vertices. Triangles outside
the polygon can be eliminated using the fact that the
polygon-vertices are oriented. This will yield a set
of triangles, whose union is the given polygon.

If you want a simple algorithm to implement 2D Delaunay
triangulation, I can give some pointers.

Thilaka