How to fracture or decompose shapes into pure rectangles instead of trapezoids?

Flyingmyd

Hi Matthias,

I am currently trying to fracture and decompose non-orthogonal shapes (such as circles or polygons with slanted edges) into purely orthogonal rectangles.

I have already tried using the decompose_trapezoids() and decompose_convex() methods via the Python API. However, they do not quite achieve what I am looking for.

What I actually want to achieve is a "staircase" approximation. As shown in the attached image, I am looking for a result where the shape is filled with a maximum inner rectangle (main field), and the curved edges are approximated by smaller, stepped rectangles (sub-fields).

(Please see the attached image for my desired output)

My questions are:
Is there any built-in method or parameter in KLayout that can enforce decomposition into pure rectangles?
If not natively supported, what would be the recommended approach or workaround using Python scripts?

Any guidance or code snippets would be greatly appreciated. Thank you in advance!

Matthias

I guess there is a whole field in computational geometry about that kind of approximation you want to achieve. KLayout is not a computational geometry library, but a practical tool. There is no such algorithm built into it. The trapezoid decomposition is a kind of convex decomposition, but without an optimization goal.

Maybe CGAL has something to offer of that kind, but I can't say. I recommend asking the LLM of your choice for recommendations.

Matthias