2D triangulation, trapezoidation, point location

See geompack.

arrange

Randomized incremental trapezoidation of arrangements of polygons in the plane or on the sphere, with point location. C source code.

There is a two-page paper about arrange.

By Michael Goldwasser, Stanford University.
Look in Stanford's ftp directory for the code.

Fast triangulation

Implementation of Seidel's randomized triangulation algorithm, in floating point. C source code.

By Atul Narkhede and Dinesh Manocha, University of North Carolina.

The text of a Graphics Gem describing this program, and the code itself, are available from their Web site.

trapdec

Expected linear-time trapezoidation of a simple polygon, in C. An input flag gives an O(n lg n) time trapezoidation which is probably much faster! C source code.

Details are in the README file.

By Dimitris Gunopulos, Princeton University.
Get trapdec from our ftp directory .

pploc

A simple O(n lg n) size data structure for a set of non-intersecting line segments (a polygon with holes, for example), to answer queries of the form, "which segment does this point lie directly above?". C source code, floating point.

By Raimund Seidel, Universität des Saarlandes.

Get this little program from our ftp directory . ftp directory.

Up: Directory of Computational Geometry Software
[HOME] The Geometry Center Home Page

Created: May 31 1995 ---