## Computational Geometry

Computational Geometry covers a collection of operations that solve specific problems in geometry. For example, one of the more common applications of computational geometry is encountered when experimental data are available only for an irregularly sampled grid. If you just want to plot such data (e.g., as a contour plot) you may not even want to know how Igor computes the curve. However, if you need to analyze your data or interpolate them you might require some of the following tools

### Delaunay Triangulation and Voronoi Polygons in the Plane

The Delaunay triangulation is a tesselation of the plane into triangles connecting nearest neighboring vertices. The triangulation is unique unless there exists more than 3 vertices that lie on a circle otherwise empty of vertices (e.g., as in the case of a square grid). The Voronoi polygons are the mathematical complement of the Delaunay triangulation. The edges of the Voronoi polygons are the perpendicular bisectors of the sides of the Delaunay triangles.

### Triangulation and Interpolation on the Surface of a Sphere

A pair of operations for handling data distributed on a surface of a sphere. The triangulation (SphericalTriangulate) produces an output that is then used by the interpolation to interpolate a scalar value given scalar values at the triangulation vertices.

### Triangulate and Interpolate in 3D.

A pair of operations that first computes the triangulation of 3D data and then uses the triangulation to interpolate a scalar at any point interior to the convex hull. The triangulation is based on an algorithm by D.F. Watson. The output of the triangulation is in a format that can be displayed directly in Gizmo, Igor's OpenGL-based 3D graphics tool.

### Bounding Ball

An algorithm that computes the smallest sphere that inscribes all the specified data.

### Convex Hull.

Compute the convex hull for a set of points in two or three dimensions. In two dimensions the convex hull can be imagined as the set of points required to describe a rubber band wrapped around the data. In three dimensions the analogy can be extended to a taut rubber surface wrapped around the data cloud.

### Polygon Area

A simple algorithm to compute the area of a planar polygon.

### Points in Polygon

A simple algorithm to find if the specified points are inside a planar polygon.