Is there way for polygon decomposition by thickness?

Question

Here is an example

dots representing coordinates of pixels

---

added more representative example

---

added real example

added main problem

Answer 1

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[0], 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[0][::-1], key[1][::-1])] = counts[key]
   return new_counts

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

etc.

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:

Answer 2

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.