Divide non-convex surfaces into the minimum number of smaller rectangles

Hì everyone,
I would like to subdivide some non-convex surfaces into the minimum number of smaller rectangles that compose them. Kindly see the attached image where I have highlighted how I need to divide these surfaces. Is there any component or method I could do that? I have tried to see some old threads in the forum, but I couldn’t solve my problem.

Thank you so much in advance!

Non-convex surfaces.gh (29.0 KB)

Question; several of these have multiple solutions, how do you want to pick between these?

Also, is there an upper limit to the complexity of these outlines?

1 Like

You can detect the inner edges by doing a simple isLeft (or isRight check). This is done by computing the dot-product of two normalized vectors and then check if it’s larger (or smaller) than 0. The vectors to take are the tangents of line a and line b.
Then you just take one vector and draw a line until it intersects. Make sure to round a bit for not running into floating number issues, or give it a minimum and maximum threshold.
A rule could be, if there is an inner edge followed by another inner edge, then take the same vector. But in the end, the problem remains on which direction to pick from.

Another approach is ray-casting. A given line intersects exactly odd times (usually once; if n modulo 2 is 1) in one direction if it’s inner, or even times (usually zero times; if n modulo 2 is 0) if it’s outer. Then just create a line between starting point and intersection point.


Hì David, thank you for the answer.
For the first question, I don’t have a rule to prefer one configuration rather than another. For example, there are two ways to divide the C shape surfaces into three smaller rectangles, both of them are good for my scope.
For the second question, the complexity will be similar to these outlines in the attachment: C, T, L, S shapes, not more complex because these are the boundary of some buildings. I have already simplified shapes that now are made by only orthogonal angles.

Hì Tom, thank you for the answer.
Yes, I think that both solutions can be suitable for my case, but I’m not sure I to be able to reproduce them in Grasshopper precisely as you described me, I’m a beginner. Do you have an example of this method that I can try to apply in my case? or do you know if it was employed in another thread that I can read?

Given the opportunity: There’s various related publications around (obviously using code) on “similar” matters. The typical general case is: attempt to split BrepFace Lists into N sub BrepFaces (where these have “as equal” as possible areas). That said implementing more specific rules is - in theory - possible. If you are interested for an indicative/raw C# solution - rather well outside your thread goal mind - notify (but it could be just a freaky black box for you if you are not familiar with coding).

1 Like

As noted above, there are numerous ways to interpret this. Here’s a possibility based on the geometry you posted, which I’m sure is not the final story. It involves several steps:

Bring in your geometry from the Oort Cloud to the origin; it’s always better to operate near 0;0;0
Rotate it so the shapes are aligned with the xy axis.
Split the shapes into rectangles by extending the edges.
Find the centroid of each resulting shape.
Sort by y values for each shape within a tolerance. (point groups)
Join those shapes with similar y values.

Going by my usual experience here, I’m completely confident that this has no generality beyond your limited and probably unrepresentative example…

Non-convex surfaces-b.gh (51.8 KB)


Thank you Peter, unfortunately I’m not familiar with coding so I don’t think I will be able to used it.

Thank you very much, Ethan. Your file makes exactly what I had in mind. Maybe in other similar cases it won’t work as well as in this one, but it will certainly be very useful as a base from which to start.

1 Like