Split intersection between polygons in the middle

Question

I am working with some biological imaging samples and trying to create a digital model of the cell shapes. For the sake of simplicity I would like to generalize their shape by modelling them as polygons.

I am struggling to split two overlapping polygons into polygons that do not share the overlapping area at their intersections. Instead this area is divided between two shapes. My intentions are best illustrated below.

I work in Python, and OpenCV package but would be happy to implement any alternative packages that could solve this. (numpythonic way would be best - if possible!)

Answer 1

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
import cv2


threshold = 200
thickness = 16
linewidth = 2
white = 255
black = 0


def fun(image):
    res = np.full(image.shape, white).astype(np.uint8)
    # determine contours
    grayscale = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    thresh = cv2.threshold(grayscale, threshold, white, cv2.THRESH_BINARY)[1]
    contours = cv2.findContours(thresh, mode=cv2.RETR_TREE, method=cv2.CHAIN_APPROX_NONE)[0]
    # create intersection and union
    intersection, union = sorted(contours, key=len)[::len(contours) - 2]
    outline = np.full(res.shape, white).astype(np.uint8)
    cv2.drawContours(outline, [union], -1, black, thickness, cv2.LINE_AA)
    inline = np.full(res.shape, white).astype(np.uint8)
    cv2.drawContours(inline, [intersection], -1, black, thickness, cv2.LINE_AA)
    # determine points for line
    points = np.logical_and(outline == 0, inline == 0).astype(np.uint8)[:,:,0] * white
    a, b = cv2.findContours(points, mode=cv2.RETR_TREE, method=cv2.CHAIN_APPROX_NONE)[0]
    a = np.mean(a.squeeze(), axis=0).astype(int)
    b = np.mean(b.squeeze(), axis=0).astype(int)
    # draw outline of union
    cv2.drawContours(res, [union], -1, black, linewidth, cv2.LINE_AA)
    # draw connecting line
    cv2.line(res, a, b, black, linewidth)
    return res

for img in ['img1.jpg', 'img2.jpg']:
    orig = np.asarray(Image.open(img))
    res = fun(orig)
    fig, ax = plt.subplots(1, 2)
    for i, img in enumerate([orig, res]):
        ax[i].imshow(img, cmap='gray');
        ax[i].axes.get_xaxis().set_visible(False)
        ax[i].axes.get_yaxis().set_visible(False)
    plt.show();

This approach works as follows:

1. First convert the image to grayscale and use thresholding to binarize the image and then determine the contours. Next, sort the contours by increasing size, which ensures that the contour of the intersection (part to remove) comes first, the contour of the union (part to keep) comes second to last (last comes the contour of the image borders).
2. Create two new white images, draw the contour of the union outline in black on one and the contour of the intersection inline in black on the other and then intersect the two images' black parts to get the patches marking the endpoints for the new line. Then compute the endpoints a and b for the new line as the mean of their respective patches.
3. Draw a straight line connecting the two points a and b as well as the outline of the union on a new, initially white, image, in black, resulting in the desired output image.

Remark: This approach does not work for the third scenario (as it assumes the shapes to be convex, or much rather, to have only one intersection), but my guess is that adapting it to also work for such cases should be doable.