Obtenez le point non visité le plus proche?

Question

J'ai mis en place une fenêtre pygame avec 10 points, et maintenant j'essaie de faire en sorte que chaque point se connecte au point le plus proche auquel aucun point précédent ne s'est connecté. Maintenant, quand j'exécute ce point, certains points forment des boucles fermées, alors qu'il ne devrait pas y en avoir, sauf une qui devrait alors contenir tous les points.

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

Jetez un oeil à cet exemple. Je viens d'ajouter le point le plus proche à la liste connected_points et le retirer du openset. Le point actuel est juste le dernier point ajouté: 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()