Computational geometry library in Python — multiple algorithm families implemented from scratch with visualization. Built for the Computational Geometry course at the University of Athens (Department of Informatics & Telecommunications). Solo project.
hull_2d/ has four classical convex-hull algorithms, all sharing the same Point and orientation primitives in hull_2d/geometry.py:
| Algorithm | File | Complexity |
|---|---|---|
| Gift wrapping (Jarvis march) | gift_wrapping.py |
O(nh) |
| Quickhull | quickhull.py |
O(n log n) average |
| Divide-and-conquer | divide_conquer.py |
O(n log n) |
| Incremental | incremental.py |
O(n²) worst, O(n log n) with sort |
plot_utils.py visualizes each step. hull_2d_tests.py runs them all on shared inputs and verifies they produce the same hull.
hull_3d/gift_wrapping.py extends the gift-wrapping idea into 3D, building the hull face-by-face. hull_3d_tests.py exercises it.
delaunay/ implements Delaunay triangulation by lifting points onto the paraboloid z = x² + y² and computing the convex hull's lower envelope — the canonical "lifting trick". delaunay/lifting.py does the math; delaunay/plot.py visualizes both the lifted hull and the projected triangulation.
test_delaunay_lifting_pipeline.py end-to-end-tests this against random point sets.
kd_tree/ implements a k-dimensional binary space partitioning tree. The driver scripts kdtree_step2.py and kdtree_step4.py correspond to the two staged exercises in the assignment — step2 builds the tree, step4 does range/nearest-neighbour queries on it.
linear_programming/ plus the top-level solve_lp.py — a small LP solver. The course set this as a "build it from primitives" exercise, so the implementation is from-scratch (not wrapping scipy.optimize.linprog).
plots/— generated visualizations for every algorithm family (hull steps, triangulation outputs, KD-tree partitions, LP feasible regions).presentation.pdf— the slide deck used for the in-class presentation.
pip install -r requirements.txt
python hull_2d_tests.py # verify the four 2D-hull algorithms agree
python hull_3d_tests.py # 3D gift wrapping
python test_delaunay_lifting_pipeline.py # Delaunay via lifting
python kdtree_step2.py # build the tree
python kdtree_step4.py # query the tree
python solve_lp.py # LP exampleMIT — applies to my own code in this repo. Assignment-distributed materials retain their original course copyright.