Path: utzoo!attcan!uunet!wuarchive!cs.utexas.edu!news-server.csri.toronto.edu!csri.toronto.edu!corkum
From: corkum@csri.toronto.edu (Brent Thomas Corkum)
Newsgroups: comp.graphics
Subject: Re: triangulation and contouring
Keywords: triangulation
Message-ID: <1990Aug15.145122.13588@jarvis.csri.toronto.edu>
Date: 15 Aug 90 18:51:22 GMT
References: <1990Aug15.003127.22609@NCoast.ORG>
Organization: Civil Engineering, University of Toronto
Lines: 23


>> I think there was a discussion some time back about delaunay triangulation of
>> random points.  I wrote a program to do this based on a paper by Cavendish JC
>> Field DA, Frey WH in the International Journal for Numerical Methods in 
>> Engineering, V21, 1985, but it ran too slowly (I have seen programs which run
>> 5-10 times faster).  Is there any fast (fastest ?) algorithm to do this?


This is rather interesting as I am currently in the process of using this
paper to write a mesher for a hybrid finite-boundary element 2D stress
analysis program. I've just completed the node insertion program based
on the 1974 paper by Cavendish and am just moving on to the triangulation
routines based on the 1985 paper by Cavendish. I must say that I was
rather disappointed as well with the grid overlay method for node
insertion, I'll end up having to employ some smoothing no doubt. If
anyone has any information or code for the triangulation I would
be interested as well. For our application we're talking maybe 500 elements
maximum so how long on a 386/20 PC would this take to triangulate? A better
question might be , does anyone have any benchmarks for the dulaunay
triangulation process? 

Brent Corkum
corkum@ecf.toronto.edu