ShampooDeng / triangulate-rs-egui

Triangulation algorithm for simple polygon with GUI, a project for my computational geometry course.
Apache License 2.0
1 stars 1 forks source link

triangulate-rs-egui

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

Feature

Installation

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 --release

Technical details

How 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:

  1. monotone partition simple polygon drawn in counter-clock wise order
  2. 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.

Thanks💖

Many thanks to following repository which inspired or helped me.