graham-scan-based-incremental-delaunay 1.0.0

Graham-scan based incremental Delaunay triangulation algorithm with visualization.

graham-scan-based-incremental-delaunay

A Delaunay triangulation algorithm visualization that incrementally add points during the process and uses Graham Scan to construct the initial triangulation of the iteration.

Documentation

Point.py
Grahamscandelaunay.py
Visual.py

Graham Scan-Based Incremental Delaunay Triangulation Algorithm

Given a list of points:

• Sort the list of points such that:
  • the first point is the leftmost, bottommost point, used as the pivot point
  • the remaining points are sorted by their slope in ascending order relative to the first point
• Construct the base convex hull using first 3 points (pivot point and two points with the lowest slopes)
• Incrementally add the next sorted point:
  • Use Graham Scan to get the convex hull, saving any edges that were made
  • Flip the current triangulation to Delaunay
  • Repeat until done

Hotkeys

• LEFT CLICK with your mouse create point on where you clicked
• Press the G key to generate a random point
• Press the S key to start the algorithm with your set of points
• Press the SPACEBAR to iterate to the next step
• Press the R key to reset the algorithm, where you can press S again to start with the same set of points
• Press the C key to stop the algorithm and clear all the points

Visualization

After starting the algorithm, a triangle will be drawn using three of the points.

• Points
  • Black points indicate points that are in the triangulation
  • Light Grey points indicate points that have yet to be added to the triangulation
  • Red points indicate the most recently added point, and the points that are involved when a circumcircle is displayed
  • Dark Red points indicate the point that is on the opposite triangle of a quadrilateral when an edge is being checked if it is Locally Delaunay
  • Yellow points indicate the circumcenter of the triangle formed by the Red points
• Edges
  • Grey edges indicate the edges in the triangulation
  • Green edges indicate the edges that are in the queue to be checked if they are Locally Delaunay
  • Blue edges indicate the current edge that is being checked if it is Locally Delaunay A Yellow circle is drawn when the current edge is an inside edge is being checked if it is Locally Delaunay. This is the circumcircle defined by the triangle formed by the Red points, centered on the Yellow circumcenter. If the Dark Red point is within the Yellow circle, then the current edge will be flipped.

When the algorithm is complete, the background will turn green to indicate completion.

Static Walkthrough

https://user-images.githubusercontent.com/48186448/116015435-3212b200-a607-11eb-8a45-fde9a8893821.mp4

Environment and package info

Please make sure you have installed the pyglet and numpy before running the code, Those two package can be installed using pip command pip install numpy and pip install pyglet

This project has been uploaded to PyPi as a package. You can download the package by the following command: python3 -m pip install graham-scan-based-incremental-delaunay After install the package, you can start the project by python3 and then >>> from grahamscandelaunay import visual

Interesting Examples

Simple 10-Gon

Pentagon in a Pentagon

Counterclockwise Inward Spiral starting from the left

Hyperbolic Curve (Horizontal Gap) - looks like a suspension bridge

Hyperbolic Curve (Vertical Gap) - looks like an hourglass