Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!snorkelwacker!bloom-beacon!bu.edu!xylogics!world!ra
From: ra@world.std.com (Chetty Ramanathan)
Newsgroups: comp.graphics
Subject: Re: Triangulating arbitrary planar polygons
Message-ID: <1990Feb26.130421.2049@world.std.com>
Date: 26 Feb 90 13:04:21 GMT
References: <1677@speedy.mcnc.org>
Distribution: comp
Organization: Software Tool & Die
Lines: 24
In-Reply-To: spl@duck.ncsc.org's message of 25 Feb 90 20:29:57 GMT



>I need a bullet-proof algorithm to tesselate (triangularize??) an aribitrary
>polygon.  The only constraint is that the polygon's points are known to be
>co-planar.  However, the polygon may be concave or convex.

I don't have a solution to your problem, but here's a pointer to two papers
that discuss triangulation & shape complexity in great detail

1. Triangulation Simple Polygons & Equivalent Problems - Alain Fournier &
   Delfin Montuno (Univ. of Toronto)

2. Triangulation and Shape Complexity - Bernard Chazelle & Janet Incerpi
   (Brown Univ)

Both papers are published in the ACM's Transactions on Graphics Vol.3 
Number 2 (April 1984)

		-ra
-- 
				-ra
-------------------------------------------------------------------------------
C.Ramanathan                                      |
Software Tool & Die, Purveyors to the Trade       |ra@skuld.std.com