最も近い未訪問ポイントを取得しますか？

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()