最近点对

二维最近点对

看了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)