# Split a polygon composed of multiples of 90 degree angles into rectangles?

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:

How would I split that into quadrants like this:

TIA for any help!

2 Likes

Since it’s 2d I think you can try checking out polybool:

You said squares but you are showing rectangles. Which one do you want to do?

Rectangles, my bad. I’ll edit the post.

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.

1 Like

I’m pretty sure you’re looking for the Greedy Meshing Algorithm: https://devforum.roblox.com/t/consume-everything-how-greedy-meshing-works/452717

Edit: Actually you’re looking for the complete opposite.

1 Like

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:

I’m probably overcomplicating things but I really have no knowledge with this type of thing.

Bumping because of a lack of an answer

Found a stack over flow algorithm for it but it seems complex " minimum dissection into rectangles of a rectilinear polygon", good luck.

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:

1. Build a node graph of the polygon
2. Use A* to find the largest closed shape

Then you can either:

1. 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

2. 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

4 Likes