How to find nearest points between two contours in OpenCV-CodePudding

For two contours c1 and c2, How do I find the nearest points between the contours.

A solution could be to iterate over all the points, get euclidian distance and go with the minimum euclidian distance but that would have huge time complexity.

I have used cv2.findContours to find the contours.

contours, _ = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

I'd like to find the two points shown on blue between the two contours.

CodePudding user response：

Can't test due to no test data in the question, but this should get you going. Using KDTrees.

from scipy.spatial import KDTree

max_distance = 10 #tune to your data

kd_trees = [KDTree(c) for c in contours]
out = {}
for i, j in zip(np.triu_indices((len(contours),)*2, 1)):
    coo = kd_trees[i].sparse_distance_matrix(kd_trees[j], 
                                             max_distance = max_distance,
                                             output_type = 'coo_matrix')
    ix = np.argmin(coo.data)
    out[(i, j)] = [contours[i][coo.row[ix]], contours[j][coo.col[ix]]]

CodePudding user response：

Using a double for loop can be time consuming. Based on Giovanni Tardini's comment and

(I used the image shared in the question. If you look closely, you will see a yellow dot in each of the contour.)

This link provides other solutions of which KDtrees (proposed by Daniel F) is an option.