Skip to content

Computational geometry algorithms from scratch in Rust.

License

Notifications You must be signed in to change notification settings

adamconkey/computational_geometry

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Computational Geometry in Rust

BUILD TEST CLIPPY

Repo for playing around with implementing computational geometry algorithms from scratch in Rust.

⚠️ Work In Progress: This repos is under heavy development right now and just in its nascent stages.


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.


Features

Currently Supported

  • Area of 2D polygons
  • Triangulation - $O(n^2)$

In the Works

  • #14: Fournier-Montuno Trapezoidization - $O(n \cdot \log n)$
  • [#2, #3]: More diverse polygon definitions

On the Roadmap

  • Convex Hull (2D and 3D)
  • Voronoi Diagram
  • Benchmarking of different triangulation algorithms
  • Animated visualizations of algorithms

Running the Visualizer

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.

Polygon Visualization

Screen Shot 2024-11-23 at 10 48 05 PM

Triangulation Visualization

Screen Shot 2024-11-23 at 10 47 30 PM


About

Computational geometry algorithms from scratch in Rust.

Resources

License

Stars

Watchers

Forks