# Awesome Computational Geometry A curated list of awesome computational geometry visualizations, libraries, and resources.

Computational geometry is a topic in computer science that focuses on solving problems in geometry. Applications of computational geometry include computer-aided design, robotics, GIS systems, and computer vision.

## Algorithm Visualizations

• Convex Hull - The convex hull of a shape is the smallest convex set that contains it.
• Convex Hull Algorithms - 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.
• Chan's Algorithm - An optimal output-sensitive algorithm to compute the convex hull of a set of points in 2 or 3 dimensions.
• Kirkpatrick's Point location - A data structure and method for point location with O(n) space and O(log n) query time using triangulation.
• Voronoi Diagrams - A partition of a plane into regions close to a given set of points.
• Fortune's Algorithm - A sweep line algorithm for generating the Voronoi diagram in O(n log n) time and O(n) space.
• Point/Line Duality - A type of mathematical duality frequently used in computational geometry algorithms.
• k-d tree - A method of partitioning k-dimensional space in an efficient way for searches like nearest neighbors.
• Configuration Space - The space of possible configurations of an object like a robot.

## Libraries

• CGAL - A software project that provides easy access to efficient and reliable geometric algorithms in the form of a C++ library. This website also has explanations of many of these algorithms.
• Wykobi - An extremely efficient, robust, and simple to use C++ 2D/3D oriented computational geometry library.
• geometry3Sharp - Open-Source, Boost-licensed C# library for geometric computing.
• Computational Geometry Software Libraries - UIUC's large collection and library of geometric software by Jeff Erickson.
• The Stony Brook Algorithm Repository - A repository of algorithms based on The Algorithm Design Manual.
• Geometric Tools - A library of source code for computing in the fields of mathematics, graphics, image analysis, and physics that includes some computational geometry algorithms.
• GeoLib - A fast and efficient computational geometry library available in C++, C# and Java.
• hull.js - JavaScript library that builds the convex hull of a set of points.
• S2 Geometry Library - 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.
• Computational Geometry Unity Library - A library of computational geometry algorithms for Unity.

## Journals

• arXiv - Recent submissions to arXiv about computational geometry.
• Elsevier - A forum for research in theoretical and applied aspects of computational geometry.
• Journal of Computational Geometry - An international open access journal devoted to publishing original research of the highest quality in all aspects of computational geometry.

## Competitive Programming

• HackerEarth - A set of articles on computational geometry.
• TopCoder - A set of articles on computational geometry.
• HackerRank - A set of programming problems using computational geometry.
• GeeksforGeeks - Implementations and explanations for a large number of commonly asked questions and common topics in geometric algorithms.

## Courses

### Open Courses

• MIT OCW - A course taught by Nicholas Patrikalakis and Takashi Maekawa in 2013.
• Udemy - A course about implementing computational geometry algorithms in C++.
• edX - A course in computational geometry.
• Brilliant - Practice problems for basic concepts in computational geometry.

## Miscellaneous

• The Open Problems Project - A project aimed to record important open problems in computational geometry and related fields.
• Wolfram - Documentation for computational geometry algorithms implemented in the Wolfram language.
• Matlab - Documentation for computational geometry algorithms implemented in the Matlab.

## Contributing

Contributions are welcome! See the contribution guidelines.