Computational Geometry Algorithms

Author: William Bowley
Description: Implementations of algorithms from Computational Geometry by Mark de Berg et al.

Overview

This repository contains python implementations of several computational geometry algorithms from Mark de Berg et al. They are intended for learning and experimentation only, and may serve as a reference for future work into classical computational or differential geometry. All algorithms are written from scratch with no external imports, includes data structures also.

Implementations

Chapter	Algorithm	Complexity	Status	Link
Ch 1	Slow Convex Hull	$O(n^3)$	Completed	slow_convex_hull.py
Ch 1	Convex Hull	$O(n \log n)$	Completed	convex_hull.py
Ch 2	Bentley-Ottmann Intersection	$O((n+k) \log n)$	WIP	find_intersections.py

Installation

# Install locally via setup-tools:
git clone https://github.com/wgbowley/Computational-Geometry-Problems.git
cd Computational-Geometry-Problems
pip install -e .