使用最近对算法时如何存储一对点

Question

我实现了最接近对算法，我试图找出随机大小的随机点列表中的哪些点最接近。我没有得到有问题的点，我要么再次达到 return 距离，要么什么都没有。我对任何批评持开放态度，但我对为什么会遇到这些问题感到困惑，因为理论上当距离达到新低并且温度表明这一点时，我可以将这对点附加或设置为变量或在列表中。

import math
from math import*
from random import *
from graphics import*

def ClosestPair(P,N):
    #Closest Pair of Points are compared, and the distance between the two pairs
    #is output as a number.
    #
    ret = []
    d = math.inf
    for i in range(N):
        for j in range(i+1,N):
            temp = -1
            d = min(d,sqrt((((P[i].getX() - P[j].getX())**2) + ((P[i].getY() - P[j].getY())**2))))
            if temp < d:
                temp = d
            else:
                ret.append(P[i])
                ret.append(P[j])
    return ret

def main():
    #X&Y is lists that get filled with N values of N size
    #X&Y are appended as the X's and Y's of a Point to Array.
    #Then If ClosestPair = 0 prints closest pair saying points are 
    #overlapping
    #Else prints the Distance and Pair of Points that are Closest
    x = []
    y = []
    array = []

    print('Enter A Size for N')
    n = int(input('N = '))
    for a in range(n):
        x.append(randrange(n))
        y.append(randrange(n))
        array.append(Point(x[a],y[a]))
    #print(array)

    if ClosestPair(array,n) == 0:
        print("The Closest Pair of Points are On top of One another!")
    else:
        print("The Distance between the Closest Points is: ", ClosestPair(array,n), "Points Away")

main()

Answer 1

内循环错误。它应该是这样的：

   temp = min(d,sqrt((((P[i].getX() - P[j].getX())**2) + ((P[i].getY() - P[j].getY())**2))))
   if temp < d:
       temp = d
       ret = [P[i], P[j]]

还有你的功能returns一对吧。将它与 0 进行比较是没有意义的。 Return 距离和点（如果需要）或重新计算距离。

使用最近对算法时如何存储一对点

How to Store a Pair of Points when using Closest Pair Algorithm

algorithm

python-3.x

zelle-graphics