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?