Reducing polygon(s) to rectangle(s)

[Isocortex]

I’m attempting to reduce a polygon to rectangle(s), given n number of vertices. The easiest case is to check for 4 points, check unique distances between points and confirm its rectangular shape. I was hoping to reduce a polygon into multiple rectangles, given that there are n points with 90 deg edges.

What solutions have you tried so far?
Initially tried getting the minimum bounding box, but realised for what I’d like to implement I’d need it to reduce it to multiple polygons (following the rules above). I have the first case sorted as described above, but reducing it algorithmically has left me scratcing my head

Does anyone know of any related algorithms?

Update:

• Triangulation not viable solution as application requires rectangular shapes
• See comments for following:

I slept on it and came up with a reasonable solution.
If you provided a function with the given n nodes and a list of edges (i.e. each node is connect to another node to make an edge), and used A Star to find the shortest path between the Start position of the edge and the End position of an edge (without using the edge as a route), you could reduce the polygon into closed shapes.
After that you could ‘ string pull ’ the path (i.e. remove instances of nodes in the path if they share the same line/direction) to reduce the node count. Then you can perform validity checks on the nodes (i.e. no more than 3 unique distances, and n = 4 nodes) for the closed shape to determine if it’s a rectangle.
However, this is quite computationally expensive, and may require me to calculate the path for each edge, the O( n ) would be too expensive for runtime.
Does anyone have any better solutions, or thought of any improvements to the above method whilst reading it?

[Fezezen]

I don’t think it’s very practical or easy to divide polygons into rectangles, it would be easier and make more geometric sense to divide them into triangles. You could try looking up algorithms for triangulation instead.

[Isocortex]

I agree that would be far easier and do use a recently made Lua port of poly2tri’s library for another application within my project. Unfortunately this particular application would only work if I was able to reduce the polygon into rectangles

[Isocortex]

I slept on it and came up with a reasonable-ish solution, but the expense of the operation is unlikely to be acceptable for runtime:

If you provided a function with the given n nodes and a list of edges (i.e. each node is connect to another node to make an edge), and used A Star to find the shortest path between the Start position of the edge and the End position of an edge (without using the edge as a route), you could reduce the polygon into closed shapes.

After that you could ‘string pull’ the path (i.e. remove instances of nodes in the path if they share the same line/direction) to reduce the node count. Then you can perform validity checks on the nodes (i.e. no more than 3 unique distances, and n = 4 nodes) for the closed shape to determine if it’s a rectangle.

However, this is quite computationally expensive, and may require me to calculate the path for each edge, the O(n) would be too expensive for runtime.

Update:
I gave up on this method and decided to approximate the polygon(s) with rectangles through rectangular decomposition - Computing the largest orthogonal rectangle in a convex polygon

Not an exact resolution to the issue as described above but good enough. Recommend the above if needed in future for anyone.

[PhamSammy]

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 more than 4 nodes, then this solution will work. This is my first time posting on the forum so I’ll provide a simple example to hopefully explain my work.

a. First remove all co-linear vertices in the polygon.

b. Determine which vertices are reflex in the polygon.

c. Iterate over the reflex vertices, for each reflex vertex (A) check the next 2 corresponding vertices (B & C) if they create a 90 degree angle and that the next vertex isn’t reflex itself (otherwise you’ll create a rectangle that is outside of the polygon). If these conditions aren’t met, retry this using the previous 2 vertices but this time check if the previous vertex isn’t reflex before iterating to the next reflex vertex. In my provided example, I’ll be choosing the next 2 vertices connected to the chosen reflex vertex since they meet the required conditions.

d. We need one more point to create a rectangle, that is going to be vertex D, to find this you would have to compare the coordinates of vertex A and vertex B to determine where vertex D may lie. Luckily there are only 2 conditions.

If A and B share the same Y value then D would have the same X value as A and Y value as C.
If A and B share the same X value then D would have the same Y value as A and X value as C.

After finding the coordinates for the new vertex D, we then cast a 2D ray from A to D. If the ray intersects exactly on vertex D with no obstructions, then we can create a rectangle. When creating the rectangle we must also remove points B and C and add point D to our list of vertices if no other points in our list have the same coordinates. (Make sure your points are still in order depending on if you worked with vertices ahead of the chosen reflex vertex or behind the chosen reflex vertex)

e. Repeat steps a-f until you only have 4 vertices remaining after removing co-linear points in step a.

f. If everything goes well you will be left with 4 vertices which creates a rectangle, you can create the rectangle and size it accordingly based off diagonal corners.

There are a few things to note… This is probably more computationally intensive when you factor in the 2D raycasting, solving for reflex vertices, and removing co-linear points. This algorithm does have trouble perfectly finding the minimum amount of rectangles to fill the polygon as shown in this shape.

I haven’t tested this out too much so I don’t know if it has any other major flaws or optimizations to be made, if you do find any feel free to tell me about it, other than that the final result should look something like this.

Hope this helps!