shampoodeng / triangulate-rs-egui

Triangulation algorithm for simple polygon with GUI, a project for my computational geometry course.

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.

This project is still working in progress, ^w^.

Feature

• 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

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?

• kd-tree in rust crates
• BTree-set in rust's std collection

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

• polygon triangulation on wikipedia

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.

Todo

• design polygon with mouse click
• implement monotone partition
• implement polygon triangulate algorithm
• implement 3-coloring painting algorithm
• output log while debugging the app
• illustrate the process of triangulate algorithm step by step
• better ui experience
  • show operation hint, like warning, suggestion, etc.
  • show current on-going process
  • add acknowledgement page for the app
  • add a Genshin(OvO) icon on acknowledgement page

Thanks💖

Many thanks to following repository which inspired or helped me.

• eframe_template
• CGAL
• kdtree-rs

triangulate-rs-egui's Issues

Implement triangulate algorithm for simple polygon

More detail can be found in https://en.wikipedia.org/wiki/Polygon_triangulation

• check vertex type
• handle start vertex
• handle end veretx
• handle split vertex
• handle merge vertex
• handle regualr vretex
• monotone polygon output
• monotone polygon triangulation
• validate if a polygon is monotone

Select a polygon's vertex with a mouse click

The goal is to select a vertex of a existing polygon in the painting area. The selected vertex will be the input for the following 3-coloring process.

It will be easy and efficient to search for something in an ordered data structure, the binary search tree for example. A polygon's vertices can be stored in a 2D-Tree. One can find a nearest vertex around the cursor by searching the nearest children with respect to cursor position in the 2D-Tree.

Available implement of KD-tree:

• kd-tree in rust crates
• BTree-set in rust's std collection

Polygon diagnoals cut polygon's outline during monotone partition.

better debug info

• debug info
• number vertices on the painting area
• output log info to local file

Implement 3-coloring for triangulated polygon

• https://www.geeksforgeeks.org/graph-coloring-applications/
• https://en.wikipedia.org/wiki/Graph_coloring

Implement dynamic binary search tree

Implement doubly connected edge list(partially complete)

get_left_neighbor: attempt to subtract with overflow

[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(173,557)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] Pushing point coordinate:(173,15)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(173,556)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(173,556)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(173,555)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(173,551)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(286,480)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] Pushing point coordinate:(286,92)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(286,480)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(286,480)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(287,480)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(287,480)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(288,480)
[2024-06-09T08:02:34Z DEBUG triangulate_rs::app] current cursor position:(290,482)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(409,569)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] Pushing point coordinate:(409,3)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(409,569)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(411,569)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(412,568)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(512,472)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] Pushing point coordinate:(512,100)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(512,472)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(512,472)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(513,472)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(513,472)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(513,472)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(521,474)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(677,568)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] Pushing point coordinate:(677,4)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(678,567)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(679,565)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(680,564)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] current cursor position:(637,349)
[2024-06-09T08:02:35Z DEBUG triangulate_rs::app] Pushing point coordinate:(637,223)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(636,349)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(636,349)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(636,349)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(635,349)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(570,261)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] Pushing point coordinate:(570,311)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(570,261)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(570,261)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(570,261)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(569,260)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(568,260)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(510,330)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] Pushing point coordinate:(510,242)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(510,330)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(510,330)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(509,330)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(509,330)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(505,332)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] current cursor position:(426,331)
[2024-06-09T08:02:36Z DEBUG triangulate_rs::app] Pushing point coordinate:(426,241)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(387,231)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] Pushing point coordinate:(387,341)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(387,229)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(387,229)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(387,229)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(387,229)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(226,210)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] Pushing point coordinate:(226,362)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(225,210)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(224,212)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(224,213)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(207,347)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] Pushing point coordinate:(207,225)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(207,347)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(206,348)
[2024-06-09T08:02:37Z DEBUG triangulate_rs::app] current cursor position:(206,349)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(124,409)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] Pushing point coordinate:(124,163)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(124,409)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(122,410)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(122,411)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(49,440)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] Pushing point coordinate:(49,132)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(48,440)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(47,440)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(46,440)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(45,441)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(44,441)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(81,308)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] Pushing point coordinate:(81,264)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(81,308)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(81,308)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(82,307)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(82,307)
[2024-06-09T08:02:38Z DEBUG triangulate_rs::app] current cursor position:(84,307)
[2024-06-09T08:02:39Z DEBUG triangulate_rs::app] current cursor position:(103,560)
[2024-06-09T08:02:39Z DEBUG triangulate_rs::app] Pushing point coordinate:(103,12)
[2024-06-09T08:02:39Z DEBUG triangulate_rs::app] current cursor position:(103,560)
[2024-06-09T08:02:39Z DEBUG triangulate_rs::app] current cursor position:(103,560)
[2024-06-09T08:02:39Z DEBUG triangulate_rs::app] current cursor position:(103,560)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(131,526)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] Pushing point coordinate:(131,46)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(131,526)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(131,526)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(131,525)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(131,525)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(132,524)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(133,522)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(236,462)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] Pushing point coordinate:(236,110)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(236,462)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(236,462)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(238,462)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(362,527)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] Pushing point coordinate:(362,45)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(363,527)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(364,527)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(523,411)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] Pushing point coordinate:(523,161)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(523,411)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(523,411)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(524,410)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(525,410)
[2024-06-09T08:02:42Z DEBUG triangulate_rs::app] current cursor position:(528,411)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(636,536)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] Pushing point coordinate:(636,36)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(636,536)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(636,536)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(636,536)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(640,534)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(713,385)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] Pushing point coordinate:(713,187)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(653,198)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] Pushing point coordinate:(653,374)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(653,198)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(653,197)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(653,197)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(653,197)
[2024-06-09T08:02:43Z DEBUG triangulate_rs::app] current cursor position:(653,197)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(561,167)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] Pushing point coordinate:(561,405)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(560,167)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(559,168)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(558,169)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(492,272)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] Pushing point coordinate:(492,300)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(492,272)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(492,272)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(491,272)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(322,245)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] Pushing point coordinate:(322,327)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(322,245)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(322,244)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(321,242)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(291,192)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] Pushing point coordinate:(291,380)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(291,192)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(291,192)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(290,192)
[2024-06-09T08:02:44Z DEBUG triangulate_rs::app] current cursor position:(289,192)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(180,230)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] Pushing point coordinate:(180,342)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(179,230)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(178,231)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(177,232)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(176,234)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(120,316)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] Pushing point coordinate:(120,256)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(120,318)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(118,321)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] current cursor position:(65,401)
[2024-06-09T08:02:45Z DEBUG triangulate_rs::app] Pushing point coordinate:(65,171)
[2024-06-09T08:02:46Z DEBUG triangulate_rs::app] current cursor position:(293,392)
[2024-06-09T08:02:46Z DEBUG triangulate_rs::app] Pushing point coordinate:(293,180)
[2024-06-09T08:02:46Z DEBUG triangulate_rs::app] current cursor position:(293,392)
[2024-06-09T08:02:46Z DEBUG triangulate_rs::app] current cursor position:(293,392)
[2024-06-09T08:02:46Z DEBUG triangulate_rs::app] current cursor position:(295,392)
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex7 is start vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex10 is start vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex6 is regular vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] interior is left to vertex6
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex11 is regular vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] interior is right to vertex11
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex9 is regular vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] interior is left to vertex9
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex8 is merge vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex12 is regular vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] interior is right to vertex12
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex5 is regular vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] interior is left to vertex5
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex14 is split vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex13 is end vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex3 is split vertex
[2024-06-09T08:02:48Z DEBUG triangulate_rs::triangulate_2] vertex1 is split vertex
thread 'main' panicked at src\triangulate_2.rs:273:19:
attempt to subtract with overflow
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace
error: process didn't exit successfully: target\debug\triangulate_rs.exe (exit code: 101)

• The terminal process "C:\Users\Liu.cargo\bin\cargo.exe 'run'" terminated with exit code: 101.
• Terminal will be reused by tasks, press any key to close it.

Output logging infomation to terminal

panicked at src\monotone_y_partition.rs:370:27: no entry found for key

Pos2::new(624.,285.),
Pos2::new(732.,285.),
Pos2::new(873.,280.),
Pos2::new(874.,509.),
[2024-06-16T09:56:16Z INFO triangulate_rs::monotone_y_partition] ---start monotone partition---
[2024-06-16T09:56:16Z DEBUG triangulate_rs::monotone_y_partition] monotone partition event queue:[2, 1, 0, 3]
[2024-06-16T09:56:16Z WARN triangulate_rs::monotone_y_partition] prev:2, idx:3, next:0
[2024-06-16T09:56:16Z INFO triangulate_rs::monotone_y_partition] vertex3 is start vertex
[2024-06-16T09:56:16Z WARN triangulate_rs::monotone_y_partition] prev:3, idx:0, next:1
[2024-06-16T09:56:16Z INFO triangulate_rs::monotone_y_partition] vertex0 is end vertex
[2024-06-16T09:56:16Z WARN triangulate_rs::monotone_y_partition] prev:2, idx:3, next:0
[2024-06-16T09:56:16Z WARN triangulate_rs::monotone_y_partition] prev:0, idx:1, next:2
[2024-06-16T09:56:16Z INFO triangulate_rs::monotone_y_partition] vertex1 is split vertex
thread 'main' panicked at src\monotone_y_partition.rs:370:27:
no entry found for key