I wrote an O(n^2) algorithm for filling a concave polygon with triangles. In the video and place it can fill this 1472-vertex polygon in around 40 seconds. Try to make it faster if you like. I’m dumping it here and abandoning it because I need to fill the area very fast, so I’ll probably use a quadtree and fill it with squares instead.
Supposedly polygon triangulation can be done in O(n log* n) (basically O(n)) but I couldn’t find any sort of explanation of how, and there would probably be just too many physical parts anyway being re-generated every time the polygon changes.
A game where players walk around drawing an area and they want to have the largest area, but if somebody walks through your path before you’ve connected the other end to the polygon then you die.
Very interesting game concept, I’m intrigued. I’m not sure that you’re going to find a polygon fill method that’s faster than known pixel level fills though. Once you have a polygon you’re still going to have to fill it pixel by pixel (or block by bock as the case may be).
When you timed them were you including the time it takes to interact with roblox objects? You should just time how long it takes to generate the data. It looks like fragmentation creates and destroys a lot more parts so it would be slower if you timed that.
Some optimizations brought it down to about 21 seconds. Waiting to parent the parts until after they’re final doesn’t make any noticeable difference, but I did keep the change.
Make an NxN square where N is the width or height of the polygon (which ever is longer) rounded up to a power of 2
Check to see if any of the vertices of the polygon are inside of this square
If none are found, check if the center of the square is inside of the polygon
If it is, set its parent
If one is found then stop searching and break the square up into 4 more squares and start the process over for each of the squares (don’t break into more squares if it’s 1x1, though)
You are measuring your wait times and your instance creation times? Surely you could make this multiple times faster if you just calculated the entire thing at once and only measured the amount of time it takes to return data.
Instead of computing a NxN square, why not do a virus sort of setup, where you find a point known to be inside the square, and start a chain reaction of each square checking the 8 around it, since your polygons will always be single-object shapes, with no islands
Might speed it up a hair, as it means you will only be finding false positives around the borders, instead of across the entire polygon
Edit: to amend, you wouldn’t necessarily need to check all 8 squares even, you could just check the one in the direct direction of it’s parent, plus it’s two neighbors, if you are worried about cost to an extreme extent.
@Weeve fragmentation lets me keep bigger squares that I know are already entirely inside, so their whole areas don’t need to be looked at. I’m not sure exactly what you mean, but I don’t think I want to do a floodfill with 1x1s because the area is too big.
