Skip to content

A curated list of awesome computational geometry visualizations, frameworks, and resources

License

Notifications You must be signed in to change notification settings

atkirtland/awesome-computational-geometry

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Awesome Computational Geometry Awesome

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.

Contents

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.

Books

Notes

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.

Conferences

Strictly Computational Geometry

Broader

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.

University Courses

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.

About

A curated list of awesome computational geometry visualizations, frameworks, and resources

Topics

Resources

License

Code of conduct

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published