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

*The Geometry Center Home Page*
Comments to: nina@geom.umn.edu