24/3/30 2:17 AM While developing a Roblox game I had the specific problem of how to create a convex polygon from what I like to call a "cloud" of arbitrary points, in a way that wouldn't mess up due to floating point precision loss (it still does, but at least it still makes something good enough for my purposes). I'm pretty sure I first thought about it 9 months ago. I've been thinking about it on and off with a lot of failed ideas but I finally have a solution, or an algorithm, if I wanna be all fancy.
I'd like to share with my solution with others. I'm not the first person to do this, as it turns out the actual name for this is a convex hull.
24/4/4 6:06 PM Now that I know the actual name for this, I did some digging. I basically made a less efficient quick hull.
I'm still proud that I figured it out though. Maybe search engines will pick this up and help somebody.
This will be in super broad terms. It's beginning to dawn on me the number of micro-steps involved in this. Teaching is hard man!
This is drawn in 2d, but with some changes this works with 3d too!
Gather the points needed to create a triangle in 2d, or a tetrahedron in 3d.
Pick a face, then find the furthest point in front it, if such a point exists.
If it does delete that face, and create new faces going towards the point.
In 2D this will always just be one face, but in 3D you need to do this for all other faces with the point in front of them.
Continue "stretching" faces until you find that all of them have the vertices of the shape behind them. Remove the vertices that aren't in any faces and you're done!
This should work for any set of points, so long as none overlap, and so long as it's possible to make a polygon with non-zero area in 2d or non-zero volume in 3d.
Here's what I got it to do in Roblox!
A bunch of random points. Their X Y Z coordinates are turned into red green blue values!
Points in a square grid arranged to roughly match a circle, like this:
Math is super pretty when you stumble upon patterns like this, look at how the remaining vertices are sort of arranged in hexagons!
