Open CV Contours - Splitting concave polygon into multiple convex ones

Question

I have the below image in a numpy array

I want to

1. separate the blocks into individual contours or any coordinate representation.

2. I then want to transform any concave polygons into multiple convex polygons.

Like this

So far I've managed to isolate each block into contours with opencv... but is there an easy way to split the L shape objects into two or more square blocks. The new contours of each shape can overlap if needed.

It may also be the case that I have an Image like this which does not have such straight lines.

I have used cv2.approxPolyDP to draw the shape, but again they are concave and I need them splitting.

Any help appreciated.

Answer 1

Ok so thanks Rahul for your answer.

I ended up finding a package that helped me trangulate the polygons which solved my issue.

download with :

pip install sect 

Then :

from sect.triangulation import constrained_delaunay_triangles

Take the contours generated by openCV - this generates them as below.

Then "smooth" the colours so there are less of them. I've used this

epsilon = 0.005 * cv2.arcLength(contour, True)
approx = cv2.approxPolyDP(contour, epsilon, True)

then run it through sect

constrained_delaunay_triangles([tuple(x) for x in approx.squeeze()])

The output splits the polygons into triangles removing ALL concave polygons totally.

Answer 2

One way I can think of is, for each contour, find it convex hull first.See this link

Now find the defect points between contour and its convex hull. See this link

Now using the data of defects distance, find the point with maximum distance. This point will be the points where the 2 objects are joined in L shape. Now from this point, draw a perpendicular line to the contour tangent at that point, and again find contours. The resultant contours will be the 2 contours for the L shape.

Note: In this approach, it is possible that some part of one object comes in other while dividing them at the boundary.