As the title says, How would I implement a Convex Hull in roblox?
I’ve read a lot of articles on the internet about this algorithm, But I dont know how to use them in Roblox, Can someone tell me how to make it work in roblox/give me some useful article about it?
Thanks in advance bois
what a question!
I’m doing some reading about it online rn.
For now, i think you should first try it in 2D just to make it simpler.
An idea might be to take the average position of each point, and to check the distance of each point to the average position of them all. Then you’ll be able to find the outer most points.
After that, you’ll have a set of verteces to make the hull from.
Graham scan - Wikipedia this algorithm is absolutely amazing.
What it does is that it first finds the point that has the lowest Y and then the lowest X coordinate (A = 4,3 B = 3,4 C = 5,2), A will be chosen.
Then it sorts the algorithm in accordance with the angle the line from the current point (Points[1,2,3 etc]) through the selected point (A in this case) makes with the X axis.
After that, it will loop through each point and checks if the angle between the next point and current point. If it makes a turn to the right, then the current point lays within the hull. If it doesn’t then that point gets chosen.
In this case, it will go from A to 1,2,3,4 then make a right turn towards 5, so it ignores 4 and goes towards 5, then 6,7, right turn towards 8,Finds the right turn from 6 to 8, ignore 7 and 6, then 9,10,11 and finished.
The end result will be {A,1,2,3,5,8,9,10,11}
And that’s your hull!
~edits: engrish
Amazing! Thanks for the information : D