<p>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:</p>

<p><a href="https://i.sstatic.net/FYSIUs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FYSIUs.png" alt="base image wall thickness decomposition"></a></p>

<p><strong>Step 1</strong>
Find all the uninterrupted horizontal and vertical lines in the image. </p>

<p><a href="https://i.sstatic.net/ISiSxs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ISiSxs.png" alt="all horizontal uninterrupted lines"></a><a href="https://i.sstatic.net/n3VYMs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/n3VYMs.png" alt="all vertical uninterrupted lines"></a></p>

<p>In python you would do something like this:</p>

<pre><code>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
</code></pre>

<p><strong>Step 2</strong> fill the area around the lines to create rectangles from the lines:</p>

<p><a href="https://i.sstatic.net/O4pk5s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/O4pk5s.png" alt="from line to rectangle for wall thickness decomposition algorithm"></a>
<a href="https://i.sstatic.net/Mp8Zds.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Mp8Zds.png" alt="from line to rectangle for wall thickness decomposition algorithm"></a>
<a href="https://i.sstatic.net/JN7Q9s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/JN7Q9s.png" alt="from line to rectangle for wall thickness decomposition algorithm"></a>
<a href="https://i.sstatic.net/cdchjs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/cdchjs.png" alt="from line to rectangle for wall thickness decomposition algorithm"></a> etc.</p>

<p>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.</p>

<p><strong>Step 3</strong> Since some lines will create the same rectangle, these duplicate rectangles need to be removed.</p>

<p><strong>Step 4</strong> 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:</p>

<p><a href="https://i.sstatic.net/AwUWOs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/AwUWOs.png" alt="overlapping rectangles"></a>
<a href="https://i.sstatic.net/SePJ7s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SePJ7s.png" alt="overlapping rectangles"></a></p>

<p>The result would then be:</p>

<p><a href="https://i.sstatic.net/HE6A1s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/HE6A1s.png" alt="split rectangles algorithm"></a></p>

<p><strong>Step 5</strong> 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:</p>

<p><a href="https://i.sstatic.net/KfojYs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KfojYs.png" alt="edge case wall splitting"></a>
<a href="https://i.sstatic.net/SbGUHs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SbGUHs.png" alt="edge case wall splittinge"></a>
<a href="https://i.sstatic.net/b0y2Ys.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/b0y2Ys.png" alt="edge case wall splitting"></a>
<a href="https://i.sstatic.net/z3ibYs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/z3ibYs.png" alt="edge case wall splitting"></a></p>

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

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

<p>All  the resulting rectangles are now the decomposed walls by thickness:</p>

<p><a href="https://i.sstatic.net/iOYp4s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/iOYp4s.png" alt="result wall thickness decomposition algorithm"></a></p>

CC BY-SA 4.0
2019-10-26T15:35:11.100Z
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.
Yu Da Chi
CC BY-SA 4.0
2019-10-26T13:27:00.077Z
2019-10-26T13:27:00.077Z
Niels
<p>Here is an example</p>

<p>dots representing coordinates of pixels</p>

<p><a href="https://i.sstatic.net/SFr02.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SFr02.png" alt="enter image description here"></a></p>

<hr>

<p><em>added more representative example</em></p>

<p><a href="https://i.sstatic.net/4E1ez.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4E1ez.png" alt="enter image description here"></a></p>

<hr>

<p><em>added real example</em></p>

<p><a href="https://i.sstatic.net/Y6bJS.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Y6bJS.jpg" alt="added real example"></a></p>

<p><em>added main problem</em></p>

<p><a href="https://i.sstatic.net/P8Y5p.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/P8Y5p.jpg" alt="main problem"></a></p>

CC BY-SA 4.0
2019-09-21T18:03:48.523Z
Use a sweep line algorithm.
lightxbulb
CC BY-SA 4.0
2019-09-23T09:44:26.483Z
@lightxbulb as far I understood that algorithm more suited for finding if any two line segments intersect or not, so it not helped me much

even if I use Canny, and get contours, I still need a fully classified rectangles with corner points
Yu Da Chi
CC BY-SA 4.0
2019-09-23T10:28:58.527Z
It has multiple uses, think of it more as an algorithm design strategy, the segment intersection algo is just one application. For instance in your case you can sweep horizontally, and check the first time `y_start` and `y_end` change, where those are the lower and upper y bounds of your points. In your example it will be `(0,1)`, then you walk along `x` and at the 7th column those change, so you combine the last 6 columns in one rectangle, etc. Note that this works only for 1 rect on over 1 `x` coord, an extension to the general case is trivial though.
lightxbulb
CC BY-SA 4.0
2019-09-23T11:44:17.630Z
@lightxbulb meh... it's a little bit hard to understand, could you draw a scheme?


I also thinking about np.meshgrid, because my data not so perfect, so I interpolate it first
Yu Da Chi
CC BY-SA 4.0
2019-09-23T11:59:02.497Z
Sorry, I will not be making a scheme. I'll try to elaborate though. Let's say you are given the grid of pixels, and the lower and upper leftmost pixels that are black, for instance `(0,0)` and `(0,1)` in your image. You can make a single step along `x` and check whether anything changes - that is check that `(1,0)` and `(1,1)` are black - if they are not, your rectangle ends. You additionally check for `(1,-1)` and `(1,2)` - if any of those are black, then a new rect starts. For your example, the first time any of these checks results in a new rect is at step 7, when the bounds are `(6,0)` and
lightxbulb
CC BY-SA 4.0
2019-09-23T12:02:07.630Z
`(6,1)`, notably we find that `(6,2)` is not white, and find the new bounds `(6,0)` and `(6,2)`. This keeps going till 6 more steps in, when the check for `(12,3)` being white fails, and the new bounds are `(12,0)` and `(12,7)`.
lightxbulb
CC BY-SA 4.0
2019-09-23T12:08:29.877Z
data is bidirectional, have a look, I updated OP post
Yu Da Chi
CC BY-SA 4.0
2019-09-23T12:20:44.580Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/98988/discussion-between-oleg-and-lightxbulb).
Yu Da Chi
CC BY-SA 4.0
2019-09-23T12:37:23.173Z
I don't have time to chat, but the idea remains the same  even with your "bidirectional data". You have two points at each end facing each other, and you step through with both at the same time - a dent or protrusion (the distance between the points changing) resulting in a new rect.
lightxbulb
CC BY-SA 4.0
2019-09-23T14:28:44.077Z
@lightxbulb I added another one image, that shows complexity of my problem - with 3x3 kernel - amount of data is enormous, I just can't predefine all variants (plato, corners, inner  - for all edges + diagonals) Meanwhile variant suggested by you do not provide enough data for further classification (height, width, coordinates)
Yu Da Chi
CC BY-SA 4.0
2019-09-23T14:40:33.513Z
No kernels are required. You just need two points on opposite sides of the boundary (inside). Then you just step perpendicular to the line segment formed by the two points and check the cells "in front" of those and diagonally to them. Try thinking it through - the algorithm is not that hard.
lightxbulb
CC BY-SA 4.0
2019-09-23T14:57:07.900Z
meh.. maybe tomorrow, but now my brain is dead already, sorru ~_~
Yu Da Chi
CC BY-SA 4.0
2019-10-25T18:49:59.917Z
Is this still open?
Niels
<image-processing>
Is there way for polygon decomposition by thickness?
Yu Da Chi
# Is there way for polygon decomposition by thickness?

(Asked by: username_0 on 2019-09-19)

Here is an example

dots representing coordinates of pixels

[![enter image description here](https://i.sstatic.net/SFr02.png)](https://i.sstatic.net/SFr02.png)

---

*added more representative example*

[![enter image description here](https://i.sstatic.net/4E1ez.png)](https://i.sstatic.net/4E1ez.png)

---

*added real example*

[![added real example](https://i.sstatic.net/Y6bJS.jpg)](https://i.sstatic.net/Y6bJS.jpg)

*added main problem*

[![main problem](https://i.sstatic.net/P8Y5p.jpg)](https://i.sstatic.net/P8Y5p.jpg)

**Tags:** image-processing

> **Comments:**
> **username_1**: Use a sweep line algorithm.  
> **username_0**: @username_1 as far I understood that algorithm more suited for finding if any two line segments intersect or not, so it not helped me much  even if I use Canny, and get contours, I still need a fully classified rectangles with corner points  
> **username_1**: It has multiple uses, think of it more as an algorithm design strategy, the segment intersection algo is just one application. For instance in your case you can sweep horizontally, and check the first time `y_start` and `y_end` change, where those are the lower and upper y bounds of your points. In your example it will be `(0,1)`, then you walk along `x` and at the 7th column those change, so you combine the last 6 columns in one rectangle, etc. Note that this works only for 1 rect on over 1 `x` coord, an extension to the general case is trivial though.  
> **username_0**: @username_1 meh... it's a little bit hard to understand, could you draw a scheme?   I also thinking about np.meshgrid, because my data not so perfect, so I interpolate it first  
> **username_1**: Sorry, I will not be making a scheme. I'll try to elaborate though. Let's say you are given the grid of pixels, and the lower and upper leftmost pixels that are black, for instance `(0,0)` and `(0,1)` in your image. You can make a single step along `x` and check whether anything changes - that is check that `(1,0)` and `(1,1)` are black - if they are not, your rectangle ends. You additionally check for `(1,-1)` and `(1,2)` - if any of those are black, then a new rect starts. For your example, the first time any of these checks results in a new rect is at step 7, when the bounds are `(6,0)` and  
> **username_1**: `(6,1)`, notably we find that `(6,2)` is not white, and find the new bounds `(6,0)` and `(6,2)`. This keeps going till 6 more steps in, when the check for `(12,3)` being white fails, and the new bounds are `(12,0)` and `(12,7)`.  
> **username_0**: data is bidirectional, have a look, I updated OP post  
> **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/98988/discussion-between-oleg-and-username_1).  
> **username_1**: I don't have time to chat, but the idea remains the same  even with your "bidirectional data". You have two points at each end facing each other, and you step through with both at the same time - a dent or protrusion (the distance between the points changing) resulting in a new rect.  
> **username_0**: @username_1 I added another one image, that shows complexity of my problem - with 3x3 kernel - amount of data is enormous, I just can't predefine all variants (plato, corners, inner  - for all edges + diagonals) Meanwhile variant suggested by you do not provide enough data for further classification (height, width, coordinates)  
> **username_1**: No kernels are required. You just need two points on opposite sides of the boundary (inside). Then you just step perpendicular to the line segment formed by the two points and check the cells "in front" of those and diagonally to them. Try thinking it through - the algorithm is not that hard.  
> **username_0**: meh.. maybe tomorrow, but now my brain is dead already, sorru ~_~  
> **username_2**: Is this still open?  

---

## 1 answers

### Answer by username_2 on 2019-10-26. Score: 1 | Accepted answer

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:

[![base image wall thickness decomposition](https://i.sstatic.net/FYSIUs.png)](https://i.sstatic.net/FYSIUs.png)

**Step 1**
Find all the uninterrupted horizontal and vertical lines in the image.

[![all horizontal uninterrupted lines](https://i.sstatic.net/ISiSxs.png)](https://i.sstatic.net/ISiSxs.png)[![all vertical uninterrupted lines](https://i.sstatic.net/n3VYMs.png)](https://i.sstatic.net/n3VYMs.png)

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:

[![from line to rectangle for wall thickness decomposition algorithm](https://i.sstatic.net/O4pk5s.png)](https://i.sstatic.net/O4pk5s.png)
[![from line to rectangle for wall thickness decomposition algorithm](https://i.sstatic.net/Mp8Zds.png)](https://i.sstatic.net/Mp8Zds.png)
[![from line to rectangle for wall thickness decomposition algorithm](https://i.sstatic.net/JN7Q9s.png)](https://i.sstatic.net/JN7Q9s.png)
[![from line to rectangle for wall thickness decomposition algorithm](https://i.sstatic.net/cdchjs.png)](https://i.sstatic.net/cdchjs.png) 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:

[![overlapping rectangles](https://i.sstatic.net/AwUWOs.png)](https://i.sstatic.net/AwUWOs.png)
[![overlapping rectangles](https://i.sstatic.net/SePJ7s.png)](https://i.sstatic.net/SePJ7s.png)

The result would then be:

[![split rectangles algorithm](https://i.sstatic.net/HE6A1s.png)](https://i.sstatic.net/HE6A1s.png)

**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:

[![edge case wall splitting](https://i.sstatic.net/KfojYs.png)](https://i.sstatic.net/KfojYs.png)
[![edge case wall splittinge](https://i.sstatic.net/SbGUHs.png)](https://i.sstatic.net/SbGUHs.png)
[![edge case wall splitting](https://i.sstatic.net/b0y2Ys.png)](https://i.sstatic.net/b0y2Ys.png)
[![edge case wall splitting](https://i.sstatic.net/z3ibYs.png)](https://i.sstatic.net/z3ibYs.png)

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:

[![result wall thickness decomposition algorithm](https://i.sstatic.net/iOYp4s.png)](https://i.sstatic.net/iOYp4s.png)

> **Comments:**
> **username_0**: 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.  

---

