My attempt at an algorithm for Delaunay Triangulation :D Turbo mode NOT recommended (although Turbowarp is). Turbo mode just totally ruins everything and I have literally no idea why. Scratch is great. Turbowarp link if desired: https://turbowarp.org/1026857680?fps=60&hqpen (250fps doesn't seem to work. It basically does what Turbo mode does...turns it into spaghetti. Although 60fps seems to run it fine.) This algorithm isn't well documented (in my opinion), so I ended up attempting to write this multiple times without sufficient information (and also ended up figuring out some of it on my own). I plan on using this for a low poly image filter, so yea :P This blog post was really good and helped a lot (if you're interested): https://ianthehenry.com/posts/delaunay/ I don't believe this is a fully correct implementation of the algorithm, but it works for my needs (although I'm not entirely sure what I need to change). Occasionally it won't calculate all the triangles correctly, and the overall shape is as a result concave, rather than convex, so I added 14 points on the outside (beyond where the random inner points can be placed), and that seemed to help. Those extra points are also included in the progress bar (if you move your mouse to the bottom). The random points are also randomly offset slightly (-3 to +3 pixels - including decimal points) so that no points are co-linear. I believe it's still technically possible for points to be co-linear, although the odds of that are astronomically low, and I have no motivation to work on this algorithm anymore. I've already spent like 18 hours on this...(but hey I made it there in the end). This runs surprisingly well on Scratch. I expected to have to optimize it a lot more lol Yep. Also, I'm not sure about time complexity, as in, how long it takes depending on the amount of points. It doesn't seem to be O(n) - aka linear. It increases as the points increase (in an exponential way), but not by a lot at all. I think a lot of it is random, but if I had to guess, it's somewhere around O(n log n) - just off of looking at a big-o notation graph and watching the speed of the algorithm. Honestly it's probably not that hard to find it out for yourself though... Yep v2.
