Использование opencv для поиска кратчайшего пути для набора из 6 точек на изображении

Question

Мне удалось найти шесть точек интереса на двумерном изображении. Теперь мне нужно нарисовать путь, который имеет кратчайшее расстояние, чтобы соединить эти точки.

путь начинается в точке 0 и не возвращается к нему.

Я буду рисовать линию от точки 0 до следующей ближайшей точки, затем из этой точки я буду рисовать линию до следующей ближайшей точки и т. Д., Пока не достигну последней точки, которая не была подключена.

шесть точек интереса сохраняются в виде массива типа Point2f. индекс 0 этого массива является отправной точкой. остальные индексы хранят оставшиеся точки в произвольном порядке.

Любая помощь будет оценена

Answer 1

cv :: norm может использоваться, чтобы найти расстояние между двумя точками. Я взял 6 случайных очков на доске 200 х 200.

Теперь я просто перебрал остальные точки, чтобы найти наименьшее расстояние, используя cv :: norm, а затем обменял его индекс со следующей точкой. Мой результат:

Извините, но код написан на python:

import cv2
import numpy as np

def find_nn(point, neighborhood):
"""
Finds the nearest neighborhood of a vector.

Args:
    point (float array): The initial point.
    neighborhood (numpy float matrix): The points that are around the initial point.

Returns:
    float array: The point that is the nearest neighbor of the initial point.
    integer: Index of the nearest neighbor inside the neighborhood list
"""
min_dist = float('inf')
nn = neighborhood[0]
nn_idx = 0
for i in range(len(neighborhood)):
    neighbor = neighborhood[i]
    dist = cv2.norm(point, neighbor, cv2.NORM_L2)
    if dist < min_dist:
        min_dist = dist
        nn = neighbor
        nn_idx = i
nn_idx = nn_idx + j + 1
return nn, nn_idx 

#taking 6 random points on a board of 200 x 200
points = [(10, 10), (115, 42), (36, 98), (78, 154), (167, 141), (189, 4)]
board = np.ones((200, 200, 3), dtype = np.uint8) * 255
for i in range(6):
    cv2.circle(board, points[i], 5, (0, 255, 255), -1)

for j in range(5):
    nn, nn_idx = find_nn(points[j], points[j+1:])
    points[j+1], points[nn_idx] = points[nn_idx], points[j+1]

for i in range(5):
    cv2.arrowedLine(board, points[i], points[i+1], (255, 0, 0), 1, tipLength = 0.07)
cv2.imshow('image', board)
cv2.waitKey(0)
cv2.destroyAllWindows()