Hi, I have no idea what this theorem is called or even if it is a theorem but I am wondering how I would go about splitting a polygon into rectangles to be displayed, assuming all corners are 90 degrees. I’m aware that there is a triangulation algorithm called ear clipping but I’m not sure that’s what I want since I would be working with quadrilaterals in this scenario.
For example, let’s say a player places points like this, each corner of the shape being one Vector3:
I’m looking for this in 3D, although the Y axes would be the same so it’d be relatively easily translated into 3D. I don’t think this is what I’m looking for though as this seems to just show difference between polygons.
That’s interesting and seems like it could help but I’m not sure how I would go about even starting out, I’m thinking I could try finding corners that are 90 degrees from each other, however I think that would become an issue when working with an L-shape:
Not sure if this is what I’m looking for as it accounts for holes which afaik shouldn’t be possible if a user is manually placing points.
I came across this post which was what I was looking for in essence, and I think this reply might be exactly what I’m looking for since the vertices will be placed in a CW or CCW order:
I’m going to sleep now and probably come up with something tomorrow but I’ll send an update if I have any updates.
My understanding is that this is called rectilinear decomposition. If the vertices of your polygon are on grid, things are a lot easier - you could perform an operation like this (even handles holes!) or this.
If you don’t have a fixed coordinate system, there were two different methods I found to be somewhat acceptable:
Build a node graph of the polygon
Use A* to find the largest closed shape
Then you can either:
Recursively decompose the shape into rectangles starting from the largest inscribed rectangle by calculating the intersection shape via polygon boolean operations and then get the bounding box of the shape(s), unionising to get the minimum dissection - details can be found here
Or you can perform convex decomposition of the polygon, then calculate the bounding box of the convex parts, and finally unionising to get the minimum dissection
I ended up using a mixture of these methods, dependent on certain conditions - you can see the result here