This repository is a fork of eframe_template. This app is based on egui's painting demo.
The goal is to accomplish the task of my Computational Geometry course solely with rust.
Screencast.from.2024-08-13.13-08-52.webm
- design polygon with mouse click
- monotone partition (sweep line algorithm) for simple polygon
- polygon triangulate
- 3-coloring triangle's vertices based on triangulation result
- choose any triangle inside polygon as startup triangle for 3-coloring
illustrate the process of triangulating a monotone polygon step by step
Make sure you have the Rust 1.78 installed on your machine. The latest stable version of Rust might also work, but I haven't tested yet🤔.
git clone https://github.com/ShampooDeng/triangulate-rs-egui
cd ./triangulate-rs-egui/
cargo build --releaseHow to select a triangle partition inside polygon with mouse click?
The coordinates of a triangle's centroid can be stored in an ordered data structure, KD-Tree. One can find a nearest vertex around the cursor by searching the nearest children with respect to cursor position in the KD-Tree.
Any available solution?
This is feature is actually implemented with crate kd-tree, see app.rs for more details.
How to partition a simple polygon into monotone ones?
cgal provides an implementation of monotone partition using sweep-line algorithm.
I've rewrite cgal's implementation in rust, see triangulate_2.rs for more details.
Which polygon triangulate algorithm to implement?
There are ear-clip and sweep-line algorithm for polygon triangulation. However, I only focus on sweep-line algorithm (because that's what I'm required to do :D). The whole process will be:
- monotone partition simple polygon drawn in counter-clock wise order
- triangulate monotone partitions
How to implement 3-coloring algorithm?
Once the simple polygon is triangulated, one can use a data structure similar to Doubly-Connected-Edge-List(DCEL) to store a triangle's adjacencies, which will eventually result in a graph-like result(neighboring triangles faces are linked by their shared edges). After that, a vertex 3-coloring result can be derived by determine the vertex color of the startup triangle and then traversing triangle faces in the DCEL in a DFS manner.
How to implement DCEL with rust?
Data inside DCEL might needs to be shared and mutable simultaneously, which will be hard to implement with Rust. The way I do it is simply build a DCEL after the triangulation, basically build a static DCEL for the purpose of coloring vertices. In that way, I don't have to maintain a valid DCEL during the process polygon triangulation. Please go to monotone_y_partition for more details.
Many thanks to following repository which inspired or helped me.