Low-level queries for 2D and 3D points. In 2D, the queries involve
determining where a point lives relative to a line (on one side, on
the other side, oe exactly on the line); relative to a triangle (inside,
outside, or exactly on an edge); or relative to the circumcircle of
a triangle (inside, outside, or exactly on the circle). In 3D, the
queries involve determining where a point lives relative to a plane
(on one side, on the other side, or exactly on the plane); relative to
a tetrahedron (inside, outside, or exactly on a face); or relative to
the circumsphere of a tetrahedron (inside, outside, or exactly on the
sphere). The data type of the query can be floating-point (float or
double) or exact rational (BSNumber or BSRational).
|
Convex hull in 2D or 3D.
|
Delaunay triangulation in 2D, Delaunay tetrahedralization in 3D, and
constrained Delaunay triangulation in 2D. The incremental Delaunay
file supports insertion and removal of points. The mesh classes provide
some additional support that, currently, is used in the interpolation
classes.
|
An implementation of the rotating calipers algorithm; it returns the
pairs of vertex-edge antipodes.
Minimum-area box and minimum-area-circle containing a set of 2D points.
Minimum-volume box and minimum-volume-sphere containing a set of 3D
points. The width of a set of 2D points but implemented to produce a
box containing the points. The returned box has the smallest width of
all boxes containing the points.
|
Separation of point sets in 2D or 3D. This is equivalent to
computing the convex hulls of the sets and determining whether
the hulls intersect (uses the method of separating axes).
|
Triangulation via ear clipping of polygons, nested polygons and trees of
nested polygons.
|
Triangulation via constrained Delaunay triangulation of polygons, nested polygons and trees of
nested polygons.
|
An algorithm for computing cycle bases in planar graphs. The input must be
a planar graph; the IsPlanarGraph class may be used to validate this
assumption (using exact arithmetic).
|
Create a tree of oriented bounding boxes for a set of points, segments
or triangles (in 3D).
|
Computation of extreme points of convex polyhedron in a specified direction.
The PRJ-suffix file uses a straightforward projection of the points onto the
line of specified direction, an O(N) algorithm. The BSP-suffix file uses a
pre-built BSP tree data structure to allow an O(log(N)) algorithm.
|
Partition a 2-dimensional manifold mesh by a plane to obtain a mesh
that is on the positive side of the plane (if such a mesh exists) and
a mesh that is on the negative side of the plane (if such a mesh
exists).
|
Boolean operations on intervals of the form [x0,x1) and on rectangles
of the form [x0,x1) x [y0,y1).
|
Boolean operations on polygons.
|
Nearest-neighbor queries using KD trees. (This is actually not a true
nearest-neighbor query. It uses an approximate query for speed. The
Geometric Tools Library will have a true nearest-neighbor query.)
|
Conformal mapping between surfaces of genus 0.
|
Automatic texture coordinate generation for manifold triangle meshes with
rectangle or disk topology.
|
Decimation of polylines using vertex collapses (continous level of
detail [CLOD]).
|
Decimation of 2-dimensional manifold meshes using vertex collapses.
|
Rasterizer a collection of tetrahedra into a 3D grid.
|
Generate polyline/polygon offsets for a given polyline
or polygon with specified offset distance.
|