Delaunay Triangulation

A while ago I needed an algorithm for Delaunay Triangulation (see, for example, this article).  I expected to be able to find lots of standard, current implementations – I didn’t.  After a lot of searching, I found David Sinclair’s algorithm, S-Hull.  Although it sounded efficient, I couldn’t use his code as it stood so I rewrote it; the results (C++ and C#) are now available on David’s website.  It’s a very difficult algorithm to get right (in fact, to be exactly right in general requires infinite-precision arithmetic); I found this paper and the program it refers to (DTT) invaluable.

This entry was posted in Uncategorized. Bookmark the permalink.