
Computational geometry
Computational Geometry Code 

This page lists "small" pieces of geometric software available on the Internet. Most of the software is available free of charge. Unless otherwise specified, C or C++ source code is available for all programs. Software libraries and collections and programs that can be run interactively over the web are listed on separate web pages. Submitted: Aug 20, 2004

Polygon Triangulation 

Computing the triangulation of a polygon is a fundamental algorithm in computational geometry. In computer graphics, polygon triangulation algorithms are widely used for tessellating curved geometries, as are described by splines. Methods of triangulation include greedy algorithms, convex hull differences and horizontal decompositions. Submitted: Nov 26, 1999

Downloadable Software from the Geometry Center 

Part of the mission of the Geometry Center is to develop software tools to support the computation and visualization of mathematics. A considerable portion of the Center's efforts have gone to designing such tools, and to making them available to the mathematical and scientific communities, and to the world at large. Submitted: Jun 25, 1999

CGAL 

The CGAL project is a collaborative effort to develop a robust, easy to use, and efficient C++ software library of geometric data structures and algorithms. The CGAL library contains: basic geometric primitives such as points, vectors, lines, predicates such as for relative positions of points, and operations such as intersections and distance calculation; a collection of standard data structures and geometric algorithms, such as convex hull, (Delaunay) triangulation, planar map, polyhedron, smallest enclosing circle, and multidimensional query structures; interfaces to other packages, e.g. for visualization, and I/O, and other support facilities. Submitted: Dec 04, 1999

Comparison of Different C++ Algorithms for Polygon Boolean Operations 

When writing my BS degree work I tested several software libraries for speed and robustness of performing polygon Boolean operations. They include Boolean (v. 1.34), CGAL (r. 1.1), Constructive Planar Geometry (CPG), and GPC (v. 2.22). Submitted: Aug 20, 2004

Qhull 

Qhull computes convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthestsite Delaunay triangulations, and furthestsite Voronoi diagrams. It runs in 2d, 3d, 4d, and higher dimensions. It implements the Quickhull algorithm for computing the convex hull. Qhull handles roundoff errors from floating point arithmetic. It computes volumes, surface areas, and approximations to the convex hull. Qhull does not support constrained Delaunay triangulations, triangulation of nonconvex surfaces, mesh generation of nonconvex objects, or mediumsized inputs in 9D and higher. Submitted: Oct 23, 1998

Steve Fortune code 

Steve Furtue sweeplione code for 2dimensional Voronoi diagram, Delaunay triangulation. Submitted: Oct 29, 1999

Triangle A TwoDimensional Quality Mesh Generator 

Triangle generates exact Delaunay triangulations, constrained Delaunay triangulations, and quality conforming Delaunay triangulations. The latter can be generated with no small angles, and are thus suitable for finite element analysis. Submitted: Oct 23, 1998

Wykobi Computational Geometry Library 

Wykobi is an efficient, robust and simple to use multiplatform 2D/3D computational geometry library. Wykobi provides a concise, predictable, and deterministic interface for geometric primitives and complex geometric routines using and conforming to the ISO/IEC 14882:2003 C++ language specification. The design and structure of Wykobi lends itself to easy and seamless integration into projects of any scale that require a robust yet efficient 2D/3D computational geometry backend. Submitted: Sep 25, 2006

Visual Computing: Geometry, Graphics, and Vision 

The "Visual Computing" book provides a concise introduction to common notions, methodologies, data structures and algorithmic techniques arising in the fields of computer graphics, computer vision, and computational geometry. Submitted: Aug 31, 2005

VXL 

VXL is a set of libraries that are the result of earlier initiatives (namely IUE, TargetJr.), to create an open source crossplatform development environment for computational geometry. VXL has GUI creation, image processing, numerical, multipleview geometry & segmentation libraries among others. Submitted: Jun 02, 2001

The SvLis Settheoretic Kernel Geometric Modeller 

This page describes the svLis settheoretic (or CSG) geometric modeller, which is coded in C++. SvLis was written at the University of Bath, where research has been done in geometric modelling for many years. The design philosophy of svLis is simple. It is an efficient settheoretic geometric modeller which is straightforward enough for any technical person who knows a little C++ to get to grips with in a day or two, but which is sufficiently rich in operations and entities to be able to represent a very wide range of shapes for all aspects of engineering, for many aspects of science, and possibly some for art as well. It is userextendible in lots of ways, and provides safe function calls to give access to all its internal geometric structures. It is intended to be easy and intuitive to program with, allowing operations to be performed using overloaded operators and functions in the usual objectoriented way, but using sophisticated memorymanagement strategies to allow the shari Submitted: Feb 16, 2000


