Computational Geometry
Computational approaches for problems in geometry.
Contents
Algorithm Visualizations
A website with visualizations of many convex hull algorithms, including gift wrapping, Graham's scan, quickhull, divide and conquer, monotone chain, and Chan's algorithm.
An optimal output-sensitive algorithm to compute the convex hull of a set of points in 2 or 3 dimensions.
A data structure and method for point location with O(n) space and O(log n) query time using triangulation.
CGViz is a FOSS web app for step-by-step visualizations of many algorithms, designed for exploration, teaching, and creating exportable visuals.
Libraries
Open-Source, Boost-licensed C# library for geometric computing.
JavaScript library that builds the convex hull of a set of points.
A package for manipulating geometric shapes. Unlike many geometry libraries, S2 is primarily designed to work with spherical geometry, i.e., shapes drawn on a sphere rather than on a planar 2D map. This makes it especially suitable for working with geographic data.
A library of computational geometry algorithms for Unity.