Up: Directory of Computational Geometry Software

Polygons: decomposition, point location, intersection, visibility

This page points to various polygon manipulation programs, including simple programs for triangulation or trapezoidation of polygons or sets of segments. There lots more polygon triangulation programs on these pages!

For point-in-polygon testing, see the code by Weiler or Haines in Graphics Gems, or the code from Joe O'Rourke's Computational Geometry in C, or this very simple function by Stein and Yap.

For point location among many polygons in the plane, see pploc, below.

Code for the area of a polygon can be found in Computational Geometry in C.

arrange

 Randomized incremental trapezoidation of arrangements of polygons in the plane or on the sphere, with point location. C source code, now with your choice of floating point or fixed-precision integer arithmatic.

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 algorithm for triangulation of a simple polygon, 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 near-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?", in O(lg n) time. C source code, floating point.

By Raimund Seidel, Universität des Saarlandes.

Get this little program from our ftp directory.

clippoly

 Finds the intersection of two polygons A and B, as well as A-B or B-A. C++ source code.

By Klamer Schutte, T.U. Delft.

See the Web page for this program.

For the intersection of two convex polygons, see once again Computational Geometry in C.

VisPak

 A collection of programs that computes the visibility graph for polygons in the plane (indicates which vertices can see each other), and also for line segments, axis-aligned polygons, and sets of rectangles. Also, for a polygon vertex, can compute its visibility polygon (the subset of the polygon that it can see).

In C++, using LEDA. Binaries for Solaris. Documentation and the code are available at the Web site.

By S. Wismath, H. Pinto and L. Jackson at the University of Lethbridge, Alberta.

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

Comments to: nina@geom.umn.edu