获取最近的未访问点？

Question

我已经设置了一个有10个点的pygame窗口，现在我正在尝试让每个点连接到以前没有任何点连接到的最近的点。现在，当我运行这个点时，一些点形成了闭环，而不应该有这样的环，除非有一个点应该包含所有的点。

​

​

for p in points:
    bestdist=math.inf
    for q in openset:
        if(points[p]!=openset[q]):
            cdist=dist(points[p],openset[q])
            if cdist<bestdist:
                bestdist=cdist
                b=q
    pygame.draw.line(DISPLAYSURF, RED, points[p] ,points[b], 2)
    openset.pop(b,None)
    pygame.display.update()

Answer 1

看一下这个例子。我只需将最近的点附加到connected_points列表并从openset中删除它。当前点只是最后添加的点：current_point = connected_points[-1]。

import math
import random
import pygame as pg


def dist(p1, p2):
    return math.hypot(p2[0]-p1[0], p2[1]-p1[1])


def main():
    screen = pg.display.set_mode((640, 480))
    clock = pg.time.Clock()
    points = [(random.randrange(640), random.randrange(480))
              for _ in range(10)]
    openset = set(points)
    connected_points = [random.choice(points)]
    openset.remove(connected_points[-1])

    done = False

    while not done:
        for event in pg.event.get():
            if event.type == pg.QUIT:
                done = True

        if openset:
            bestdist = math.inf
            current_point = connected_points[-1]
            for point in openset:
                cdist = dist(current_point, point)
                if cdist < bestdist:
                    bestdist = cdist
                    nearest_point = point

            connected_points.append(nearest_point)
            openset.remove(nearest_point)

        screen.fill((30, 30, 30))
        for p in points:
            pg.draw.circle(screen, (100, 140, 100), p, 5)
        if len(connected_points) >= 2:
            pg.draw.lines(screen, (150, 50, 50), False, connected_points, 2)

        pg.display.flip()
        pg.time.wait(500)
        clock.tick(30)


if __name__ == '__main__':
    pg.init()
    main()
    pg.quit()