Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!brutus.cs.uiuc.edu!apple!agate!shelby!polya!anaconda.stanford.edu!sumane
From: sumane@anaconda.stanford.edu (Thilaka Sumanaweera)
Newsgroups: comp.graphics
Subject: Re: Polygon Triangulation
Message-ID: <11844@polya.Stanford.EDU>
Date: 19 Sep 89 16:44:38 GMT
Sender: USENET News System <news@Polya.Stanford.EDU>
Reply-To: sumane@anaconda.stanford.edu (Thilaka Sumanaweera)
Organization: Stanford University
Lines: 38

This is in response to the following message:

*****************************************************************************
In article <11820@polya.Stanford.EDU>, sumane@anaconda.stanford.edu (Thilaka Sumanaweera) writes:
> [Stuff deleted]

> 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.
> 

    But the edges of the given polygon may not be in the 

set of edges of the Delaunay triangulation.  It is not

clear how you can handle these efficiently.

> [Stuff deleted] 
> Thilaka

Jin Chou

*****************************************************************************

This problem can be get around by introducing new points ( O(N) )
on the original edges as explained in the following: (N = No of points.)

	Shape Reconstruction from Planar Cross Sections
		- Jean-Daniel Boissonnat, Journal of Computer Vision, Graphics
		  and Image Processsing 44, pp 1-29, 1988

This algorithm can introduce new points with the time complexity O(N log N).

Thilaka