Python implementation of algorithms and data structures from plane geometry
Project description
planegeometry package
Python implementation of algorithms and data structures from plane geometry is presented.
Problems, algorithms, and data structures
- Geometric objects: points, segments, polygons, rectangles, triangles, circles
- Data structures: edges, graphs, triangle collections, AVL trees, quadtrees, connected planar maps
- Point in polygon problem: the winding number method, the crossing number method
- Polygon orientation
- Bounding box
- Line segment intersection problem: brute force O(n^2), Shamos-Hoey, Bentley-Ottmann
- Closest pair of points problem: brute force search O(n^2), sweep line technique, divide and conquer approach
- Finding two furthest points: brute force search O(n^2), rotating calipers
- Convex hulls: Graham scan O(n log n), Jarvis march (gift wrapping) O(n h), quickhull (divide and conquer approach)
- Delaunay triangulations: naive approach O(n^4), edge flipping, Bowyer-Watson
- Convex polygons: recognition, fan triangulation O(n)
- Monotone polygons: in progress (recognition, triangulation)
- Connected planar maps based on the doubly connected edge list (DCEL): constructors, map overlay procedure.
- Voronoi diagrams: from Delaunay triangulation
Download
To install an official release do
python3 -m pip install planegeometry
To get the git version do
git clone https://github.com/ufkapano/planegeometry.git
Usage
See doc/quickstart.txt and other doc/*.txt files.
Contributors
Andrzej Kapanowski (project leader)
Marcin Permus (convex hull, rotating calipers)
Wojciech Chrobak (sweep line technique, quadtree, closest pair problem)
Monika Wiech (Delaunay triangulation)
Anna Sarnavska (planar maps overlay)
Gabriela Mazur (monotone polygons)
Mateusz Malczewski (Voronoi diagrams)
Maciej Mularski (range searching)
EOF
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
planegeometry-1.0.2.tar.gz
(58.3 kB
view hashes)
Built Distribution
planegeometry-1.0.2-py3-none-any.whl
(100.4 kB
view hashes)
Close
Hashes for planegeometry-1.0.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8948f09da989e9caa170b9c19f99489eec6d1f2372d7ace3e891589750d22ef |
|
MD5 | 4098ace256aa686c7a033d50eddcc0e2 |
|
BLAKE2b-256 | 4fc2e0a9c1cfe657689ea59411dac7ec35385a0e4508d24cb263484b91346feb |