How to connect closest points together using opencv

Using the OpenCV module in python is it possible to connect the red dots in the image below such that each red dot is only connected once to its nearest neighbor red dot?

Answer

For the first step, you should convert your image to a binary image using the appropriate tools like cv2.cvtColor(), cv2.threshold(), cv2.bitwise_not(),… (depending on the image) – this means that your image will contain only black or white pixels.

Example:

Then you should find your contours (cv2.findContours) on the image and filter them out with size criterion (cv2.contourArea()) to eliminate other contours like the big pentagon in the middle of the image.

Next step you should find the moments of each contour (cv2.moments()) so you will be able to get x and y coordinates of the center of the contour and put them in a list. (Be careful to append the right x and y coordinate together).

After you have your points you can calculate the distance between all points (with the distance between two points formula – sqrt((x2-x1)^2+(y2-y1)^2))

Then you can use whatever logic you want to get the coordinates of points of shortest distance for every point (in the example below I zipped them in a list and made an array containing distance, x and y coordinates for every point).

Example in code:

    import numpy as np
    import cv2

    img = cv2.imread('points.jpg')
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    ret, threshold = cv2.threshold(gray,150,255,cv2.THRESH_BINARY)
    cv2.bitwise_not(threshold, threshold)
    contours, hierarchy = cv2.findContours(threshold,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
    listx = []
    listy=[]
                         
    for cntr in range(0, len(contours)):
        cntr = contours[i]
        size = cv2.contourArea(cntr)
        if size < 1000:
            M = cv2.moments(cntr)
            cX = int(M["m10"] / (M["m00"] + 1e-5))
            cY = int(M["m01"] / (M["m00"] + 1e-5))
            listx.append(cX)
            listy.append(cY)

    listxy = list(zip(listx,listy))
    listxy = np.array(listxy)

    for x1, y1 in listxy:    
        distance = 0
        secondx = []
        secondy = []
        dist_listappend = []
        sort = []   
        for x2, y2 in listxy:      
            if (x1, y1) == (x2, y2):
                pass     
            else:
                distance = np.sqrt((x1-x2)**2 + (y1-y2)**2)
                secondx.append(x2)
                secondy.append(y2)
                dist_listappend.append(distance)               
        secondxy = list(zip(dist_listappend,secondx,secondy))
        sort = sorted(secondxy, key=lambda second: second[0])
        sort = np.array(sort)
        cv2.line(img, (x1,y1), (int(sort[0,1]), int(sort[0,2])), (0,0,255), 2)

    cv2.imshow('img', img)
    cv2.imwrite('connected.png', img)

Result:

As you can see in the result, every point is now connected with its closest neighbor point. Hope it helps a bit or at least give an idea on how to solve the problem. Cheers!