Repo for playing around with implementing computational geometry algorithms from scratch in Rust.
Currently the algorithms are implemented following Joseph O'Rourke's Computational Geometry in C.
This is very much a work in progress, I'm just stepping through the text and implementing things as I go. I'm also a Rust newb so I'm frequently stumbling through the implementations, finding I made a terrible design decision, and going back to reimplement things. As such the API is in constant flux.
My goal for this repo is to eventually have a complete implementation of the algorithms described in the text, which will serve as the basis of a computational geometry library in Rust. I will then build from there, exploring more modern concepts and algorithms. My priorities are to have relatively easy-to-read code, a great test suite, and nice visualizations. I will have these three objectives in mind as I build out this repo.
- Area of 2D polygons
- Triangulation -
$O(n^2)$
-
#14: Fournier-Montuno Trapezoidization -
$O(n \cdot \log n)$ - [#2, #3]: More diverse polygon definitions
- Convex Hull (2D and 3D)
- Voronoi Diagram
- Benchmarking of different triangulation algorithms
- Animated visualizations of algorithms
A simple visualizer is provided using the egui_plot
crate. This provides a local webapp to visualize polygons. Currently this is very simple, and just visualizes the polygons themselves as well as a triangulation. Once more algorithms are implemented I plan to add animations so that one can view the different algorithms in action.
To run the visualizer, simply do:
cd visualizer
trunk serve
You can then direct your browser to localhost:8080
and you'll hopefully see some polygons! If you're in VSCode, it can be handy to use the SimpleBrowser
offered in the IDE.