# Is there way for polygon decomposition by thickness?

Here is an example

dots representing coordinates of pixels    • I see two figures consisting of rectangles, both congruent, one in grayscale and one in colors. What would you like to cluster here? – Stephan Kolassa Sep 19 at 12:13
• gray is an image which is I should to process somehow to get second, colored image – Oleg Sep 19 at 12:16
• Ah. It sounds like you actually don't want to cluster shapes, but to cut them into the smallest possible number of rectangles, correct? – Stephan Kolassa Sep 19 at 12:24
• yeah, split them, and get coordinates of it – Oleg Sep 19 at 12:26
• got it, thank you Stephan! – Oleg Sep 19 at 13:41

I would write an algorithm where you would iteratively fill lines into rectangles and create a rectangle merging and splitting procedure based on area and thickness. I will use the following image as an example image for the algorithm: Step 1 Find all the uninterrupted horizontal and vertical lines in the image.

In python you would do something like this:

def horizontal_longest_lines(im):
counts = {}
on_a_line = False
line = None
for row_index, row in enumerate(im):
for col_index, pixel in enumerate(row):
coord = (row_index, col_index)
if not pixel:
on_a_line = False
line = None
continue
if pixel:
if not on_a_line:
on_a_line = True
line = (coord, coord)
counts[line] = 1
else:
current = counts[line]
del counts[line]
line = (line, coord)
counts[line] = current + 1
return counts

def vertical_longest_lines(im):
counts = horizontal_longest_lines(im.transpose())
new_counts = {}
for key in counts:
new_counts[(key[::-1], key[::-1])] = counts[key]
return new_counts


Step 2 fill the area around the lines to create rectangles from the lines:

For a more efficient algorithm, you could improve this step by trying to merge existing lines into rectangles. But that would probably a bit more complicated to write.

Step 3 Since some lines will create the same rectangle, these duplicate rectangles need to be removed.

Step 4 Find overlapping rectangles, give preferences to rectangles that have a bigger area. Cut off the overlapping part from the smaller rectangle. For these two rectangles:

The result would then be: Step 5 Some edge cases can happen, where the resulting cut-off does not result in a new rectangle. For these cases, split the resulting shape in new rectangles. For instance in this case:

Do note, there are two possibilities here in splitting up the resulting shape. You would need to fine-tune this process.

Step 6 Merge rectangles that have exactly the same width as the other rectangle's height and are touching each other.

All the resulting rectangles are now the decomposed walls by thickness: • Nice solution mate! but as for me — I needed a 100% robust & 0 maintenance way, so I ended up with plain simple template matching, categorized by wall thickness. But thank you anyway! Hope it would be helpful for someone. – Oleg Oct 26 at 15:35

It is a bad idea to try to abuse clustering algorithms for this. In particular k-means will not cut vertically, nor consider rectangles.

What you need to do is a trivial axis-aligned corner detection.it does not get much simpler than that!

You begin on the left, and whenever the location of the topmost pixel changes, a rectangle is complete.

• imagine bw floor plan with different wall thickness, so thickness can vary in different directions – Oleg Sep 20 at 7:25