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

[7z99 (cody)]

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!

[dthecoolest]

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

PolyBool Lua Library

Hi all! I recently wrote a port of a js library that provides functionality for 2D boolean opperations on polygons. I’ve found it’s super useful for just about anything you can squash down into 2D so I figured I’d share it with all of you as well. Here’s a Roblox model if you prefer: And here are some screenshots of what it can do! I’d have prefered a better demo, but filling concave polygons is a pain. Check out the demo on the js library to get a better feel. [None] [Union] [Inter…

[RecanValor (recanman)]

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

[7z99 (cody)]

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

@dthecoolest

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

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.

[FuzzyEq]

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.

[7z99 (cody)]

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.

[7z99 (cody)]

Bumping because of a lack of an answer

[dthecoolest]

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

Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping

[7z99 (cody)]

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:

Reducing polygon(s) to rectangle(s)

Recently I was searching for ways to ‘rectangulate’ rectilinear polygons too. I already came up with a way of doing it but I’m browsing the forum to see whether there are any alternative solutions. I’m sharing what I have here to see if it fits your needs since you said that rectangular decomposition was not the exact solution you were looking for. So let’s get into it. Assuming that the placed nodes are either in clockwise or counter-clockwise order and that the polygon is rectilinear with mo…

I’m going to sleep now and probably come up with something tomorrow but I’ll send an update if I have any updates.

[DevSynaptix]

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