November 9, 2019 EDIT: I found a horrible edge case regarding nearby integers a while back and haven’t and won’t fix them. Don’t use this module.
I wrote a module that fills any simple polygon with right triangles. Simple means:
- No holes
- No intersecting edges
- No vertices at the same position
It has an upper bound of O(n3). A faster implementation already exists, but the file is no longer available.
Extra Information
I attempted this challenge because I needed to fill a hexagon for a project. Unbeknownst to me, polygon triangulation is a popular problem, and the algorithm I devised is actually a common algorithm called ear clipping. I wrote the first version entirely myself, so after discovering this problem online, I replaced some of my math with others’ faster math. The final version is about half and half. Much quicker algorithms exist than ear clipping, but I’ll save that for someone else. 
Files
If you want to play with the polygon editor seen in the GIF, download the place file. Otherwise, grab the module.
Module: Polygon Triangulator - Roblox
Polygon Editor: file removed because the script is broken
I have yet to find any edge-case polygons that triangulate incorrectly. If you do, please let me know.
