Path: utzoo!attcan!uunet!mcvax!hp4nl!ruuinf!markov
From: markov@ruuinf.cs.ruu.nl (dr.m.h. overmars)
Newsgroups: comp.graphics
Subject: Re: Concave polygon problem
Summary: This is all wellknown in computational geometry
	 Some references to literature.
Message-ID: <1388@ruuinf.cs.ruu.nl>
Date: 17 Jun 89 13:07:23 GMT
References: <3378@cps3xx.UUCP> <3964@eos.UUCP> <14611@pasteur.Berkeley.EDU>
Organization: Univ of Utrecht, Dept of CS
Lines: 16

The problem of triangulating a polygon is well-known in computational
geometry. See e.g. Preparata and Shamos: Computational Geometry, an
introduction, published by Springer-Verlag for some algorithms. Given a
n-vertex polygon the theoretically most efficient algorithm runs in time
O(n loglog n) but I would not encourage you to implement it. A simple method
partitions the polygon into monotone polygons (each horizontal line intersects
it only once) and next triangulate these. It does not require you to add
vertices in the interior and runs in time O(n log n). See the above
book for a clear description.


-- 
--------------------------------------------------------------------------------
Mark Overmars                                                  |\/| 
Dept. of Comp. Science, University of Utrecht,                 |  |ark
P.O. Box 80.089, 3508 TB Utrecht, the Netherlands    E-mail: hp4nl!ruuinf!markov