How to cut irregular polygon to rectangles using shapely (python)?

Question

I have a 150*150 figure inside it are multiple irregular shaply polygons. The polygons are defined using points as follows: polyon((140 0, 140 50, 140 95, 140 140, 95 140, 65 140, 65 150, 150 150, 150 0, 140 0))

Is there any way to divide each irregular shape into multiple perfect rectangles.

Like this (the red lines):

All the polygons in the image:

Polygon((140 0, 140 50, 140 95, 140 140, 95 140, 65 140, 65 150, 150 150, 150 0, 140 0))
Polygon((75 0, 75 25, 90 25, 90 0, 75 0))
Polygon((0 140, 0 150, 40 150, 40 145, 15 145, 15 140, 0 140))
Polygon((25 25, 25 30, 30 30, 30 45, 40 45, 40 25, 25 25))
Polygon((15 35, 15 30, 10 30, 10 35, 15 35))
Polygon((5 0, 5 5, 10 5, 10 0, 5 0))

There's no unique decomposition into rectangles – consider the top-left shape in your example with e.g. a horizontal cut instead. If your shapes don't get more complicated than L shapes then you could use some heuristic like "prefer the most-square decomposition", but for arbitrary input shapes it could get [messy](https://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas). Do you have any further constraints on your inputs / desired outputs? — motto, May 11 '23 at 19:27
Like motto said, if you don't care about which way to cut it and you don't have anything more than an L, you could just detect all internal right angles and cut it horizontally. — imad.nyc, May 11 '23 at 19:32
Thank you for the response @motto . input shapes are always in those 3 forms(rectangle, L shape or the irregular one). output should be a set of rectangles **(if possible)**. Can you please elaborate on the method you described? — 0x Empyrean, May 12 '23 at 06:24
@imad.nyc can you please explain how to detect angles because i tried using coordinates (using lowest horizontal and highest vertical coordinates) but without results — 0x Empyrean, May 12 '23 at 06:26

score 1 · Accepted Answer · answered May 12 '23 at 14:20

If your shapes are always axis-aligned and always either a rectangle or an L shape, then life is a lot simpler.

Assuming you're happy with always splitting horizontally, you can process an L-shaped polygon by:

detecting the interior vertex (it will be the only vertex on the perimeter that isn't on the bounding box)
splitting the polygon with a horizontal line that extends to the polygon's bounding box

from shapely import MultiPoint, LineString
import shapely.ops as ops

def find_internal_vertex(poly):
    simple_poly = poly.simplify(0)  # Remove superfluous vertices
    pt = (
        MultiPoint(simple_poly.boundary.coords)
            .difference(simple_poly.envelope.boundary)
    )
    if pt.geom_type != "Point":
        raise Exception("Shape is not rectangular or L-shaped", poly)
    elif pt.is_empty:
        return None
    else:
        return pt

def split_horizontally(poly, split_origin):
    min_x, min_y, max_x, max_y = poly.bounds
    (origin_x, origin_y) = split_origin

    horizontal_line = LineString(((min_x, origin_y), (max_x, origin_y)))

    return ops.split(poly, horizontal_line)

def split_poly(poly):
    internal_vertex = find_internal_vertex(poly)
    
    if internal_vertex is None:
        # No internal vertex, poly is a rectangle
        yield poly
    else:
        # This is an L; split it horizontally
        origin = internal_vertex.coords[0]
        yield from split_horizontally(poly, origin).geoms

Running it on all the inputs I get:

from itertools import chain
outputs = chain.from_iterable(split_poly(p) for p in inputs)

How to cut irregular polygon to rectangles using shapely (python)?

1 Answers1