二维最近点对
看了https://blog.csdn.net/lishuhuakai/article/details/9133961的博客 受益匪浅
用python实现了算法
import math import cv2 import numpy as np import random import os md = float('inf') pts = [] def take_first( elem): return elem[0] def get_d(a,b): global md,pts d = math.sqrt((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1])) if d<md: pts = [[a,b]] md = d if d==md: pts.append([a,b]) md = d return d def min_between(point, left, mid, right, d): temp = float('inf') for i in range(left, mid): if abs(point[i][0] - point[mid][0]) <= d: for j in range(mid, right): if abs(point[i][0] - point[j][0]) <= d and abs(point[i][1] - point[j][1]) <= d : if get_d(point[i], point[j]) < temp: temp = get_d(point[i], point[j]) return temp def divide(point, left, right): # right不包括 if right - left < 2 : return float('inf') elif right - left == 2: return get_d(point[left], point[left + 1]) else: mid = int((left + right) / 2) min_left = divide(point, left, mid) min_right = divide(point, mid, right) d = min(min_left,min_right) min_mid = min_between(point,left,mid,right,d) return min(min_left, min_right,min_mid) def init(num=20): seed = [] for i in range(0, num): x = random.randint(0, 640) y = random.randint(0, 640) seed.append([x, y]) return seed pos = init(50) print(divide(pos,0,len(pos))) print(pts)