This module contains implementations for computational geometry algorithms based upon Franco P. Preparata and Michael I. Shamos' book "Computational Geometry: An Introduction". These algorithms are subdivided into three topics: geometric searching, constructing convex hulls, and proximity problems.
- Point location
- Slab method: locate a point in a planar graph between its two edges.
- Chain method: locate a point in a planar graph between its two monotone chains connecting its lower-most and upper-most vertices.
- Triangulation refinement method (TBD): locate a point in a triangulated planar graph in one of the triangles.
- Range-searching
- k-D tree method: find out which or how many points of a given set lie in a specified range, using a multidimensional binary tree (here, 2-D tree).
- Range-tree method: find out which or how many points of a given set lie in a specified range, using a range tree data structure.
- Loci method: find out how many points of a given set lie in a specified range, using a region (locus) partition of the searching space.
- Static problem
- Graham's scan: construct the convex hull of a given set of points, using a stack of points.
- Quickhull: construct the convex hull of a given set of points, using the partitioning of the set and merging the subsets similar to those in Quicksort algorithm.
- Divide-and-conquer: given the convex hulls of the two subsets of a given set of points, merge them into a convex hull of the entire set of points.
- Jarvis' march: construct the convex hull of a given set of points, using the so-called gift wrapping technique.
- Dynamic problem
- Preparata's algorithm: construct the convex hull of a set of points being dynamically added to a current hull.
- Dynamic convex hull maintenance (TBD): construct the convex hull of a set of points and re-construct it on addition or deletion of a point.
- Divide-and-conquer closest pair search: given a set of points, find the two points with the smallest mutual distance, using divide-and-conquer approach.
- Divide-and-conquer Voronoi diagram constructing (TBD): given a set points, construct their Voronoi diagram, using divide-and-conquer approach.