MANIPULATION À LA SOURIS D'UN GRAPHE SANS CIRCUIT (AVEC LA LIBRAIRIE PYGAME)

# -*- coding: cp1252 -*-
#Jean-Christophe Bouvard Juillet 2007
#nekochat@gmail.com

#déplacement graphique d'un graphe sans circuits
#a la manière d'un pantin articulé
#le graphe peut contenir des sous-graphes non connexes

import math
import os
import getopt
import pygame
from pygame.locals import *


class SimpleGraph:
  def __init__(self,points ,arcs):
    #liste de couples (x,y) convertis en float pour conserver la précision
    self.points=points
    for p in range(0,len(self.points)-1):
      self.points[p] =intpoint2floatpoint(self.points[p])
    #liste de tuples représentant l'ensemble des index de points adjacents
    self.arcs=arcs
    self.taglist=[]
     
    
  #déplacer un point en déplacant l'ensemble des sommets de manière récursive
  def move(self,pointindex, newpos):
    mynewpos=intpoint2floatpoint(newpos)
    self.taglist=[]
    self.internalmove(pointindex, mynewpos)
    self.taglist=[]
    
  def internalmove(self,pointindex, mynewpos):
    if not pointindex in self.taglist:
      self.taglist.append(pointindex)
     
      #parcours des successeurs.
      for i in self.arcs[pointindex]:
        #calcul des coordonnées du prédecesseur
        #d'abord rotation du point autour du prédecesseur (en gardant la même distance) pour l'aligner 
        #avec la postion de destination
        if i==pointindex:
          print "redondance !" + str(i)
        ivector=vectorfrom2points(self.points[i],mynewpos)
        #rotatepoint=rotatesegment(self.points[i],mynewpos,ivector[0])
        dist=distance(self.points[i],self.points[pointindex])
        rotatepoint=(self.points[i][0]+ math.cos(ivector[0])*dist,self.points[i][1]+ math.sin(ivector[0])*dist)
        
        
        #ensuite calcul des distances dx et dy à parcourir pour atteindre la position finale
        deltapoint=(mynewpos[0]-rotatepoint[0],mynewpos[1]-rotatepoint[1])
        #ajouter le mouvement de ce nouveau point dans la pile par un appel récursif à la fonction move
        self.internalmove(i,(self.points[i][0]+deltapoint[0],self.points[i][1]+deltapoint[1]))
      #parcour des predecesseurs
      for i in range(0, len(self.points)):
        if pointindex in self.arcs[i]:
        #calcul des coordonnées du prédecesseur
        #d'abord rotation du point autour du prédecesseur (en gardant la même distance) pour l'aligner 
        #avec la postion de destination
          ivector=vectorfrom2points(self.points[i],mynewpos)
          dist=distance(self.points[i],self.points[pointindex])
          rotatepoint=(self.points[i][0]+ math.cos(ivector[0])*dist,self.points[i][1]+ math.sin(ivector[0])*dist)
          
        #ensuite calcul des distances dx et dy à parcourir pour atteindre la position finale
          deltapoint=(mynewpos[0]-rotatepoint[0],mynewpos[1]-rotatepoint[1])
          
        #ajouter le mouvement de ce nouveau point dans la pile par un appel récursif à la fonction internalmove
          self.internalmove(i,(self.points[i][0]+deltapoint[0],self.points[i][1]+deltapoint[1]))
      #... et enfin deplacer le point
      self.points[pointindex]=mynewpos
  
  #recherche du sommet le plus proche d'une position donnée (surtout utilisée pour le pointage à la souris)
  def nearestpoint(self,point):
    best=0
    for i in range(0, len(self.points)):
      if distance(self.points[i],point)<distance(self.points[best],point):
        best=i
    return best
      
#Classe qui dessine une représentation d'une instance de notre SimpleGraph
class SimpleGraphDrawing:
  def __init__(self,screen,simplegraph,arccolor=(0,0,0),pointcolor=(0,0,0)):
    self.screen=screen
    self.arccolor=arccolor
    self.pointcolor=pointcolor
    self.graph=simplegraph
  
  #dessiner le graphe
  def draw(self):
    for point in self.graph.points:
      indice=self.graph.points.index(point)
      
      for arc in self.graph.arcs[indice]:
        pygame.draw.line(self.screen, self.arccolor, floatpoint2intpoint(point),floatpoint2intpoint(self.graph.points[arc]), 1)
      #un petit cercle autour de notre sommet pour faire joli
      pygame.draw.circle(self.screen,  self.pointcolor, floatpoint2intpoint(point), 5, 1)

#-----------------------------------------------------------------------------------------------
#Fonctions utiles dans la manipulation des sommets

#transformer un coupe d'entier en un couple de float
def intpoint2floatpoint(point):
  return (float(point[0]),float(point[1]))


#...et un couple de float en entiers
def floatpoint2intpoint(point):
  return (int(round(point[0])),int(round(point[1])))


#le point1 est le centre du cercle, le point2 est sur le cercle
#renvoie les coordonnées du point2 "déplacé" sur le cercle en accord avec l'angle
def rotatesegment(point1,point2,angle):
  d=distance(point2,point1)
  return (point1[0]+math.cos(angle)*d,point1[1]+math.sin(angle)*d)

#calculer la distance entre 2 points
def distance(floatpoint1,floatpoint2):
  return abs(math.sqrt(math.pow(floatpoint2[0]-floatpoint1[0],2)+ math.pow(floatpoint2[1]-floatpoint1[1],2)))
  

#le point1 est le centre du cercle, le point2 est sur le cercle
#on renvoie les coordonnées polaires (angle, distance entre les 2 points)
def vectorfrom2points(floatpoint1,floatpoint2):
  mydistance=distance(floatpoint1,floatpoint2)
  point=(floatpoint2[0]-floatpoint1[0],floatpoint2[1]-floatpoint1[1])
  if mydistance!=0.0:
    if point[0]==0.0:
      angle=(point[1]/abs(point[1]))*math.pi/2
    else:
      angle=math.atan(point[1]/point[0])
      if point[0]<0.0:
        angle=math.pi+angle
  else:
    print "distance=0 !"
    angle=0
    mydistance=0
  return (angle,mydistance)

#-----------------------MAIN------------------------------------------------------------------------------------------------

def main():
 
  pygame.init()
  screen = pygame.display.set_mode((640, 480))
  pygame.display.set_caption("manipuler un pantin")
    

#Création du fond
  background = pygame.Surface(screen.get_size())
  background = background.convert()
  background.fill((250, 250, 250))

  #données du graphe
  points=[(75,125),(100,125),(150,175),(175,225),(200,175),(150,75),(200,100),(200,50), (320,250),(400,300),(425,450)]
  arcs=[[1],[2,5],[3,4],[],[],[6,7],[],[],[9],[10],[]]

  #création du graphe
  mongraphe=SimpleGraph(points,arcs)
  graphdraw=SimpleGraphDrawing(screen,mongraphe,(0,0,0),(250,45,45))
  graphdraw.draw()
#Afficher le fond
  screen.blit(background, (0, 0))
  pygame.display.flip()
#Préparation...
  clock = pygame.time.Clock()
   #Main Loop--------------------------------------------------------------
  
  #flag pour signifier que le déplacement d'un sommet est en cours
  mousedown=False
  while 1:
    clock.tick(60)

    #gestion des evennements
    for event in pygame.event.get():
      if event.type == QUIT:
        return
      #le bouton de la souris est enfoncée
      #si il était levé on selectionne le sommet le plus proche
      #qui suivra les mouvements de la souris jusqu'à qu'il soit relâché
      elif event.type==MOUSEBUTTONDOWN:
        if mousedown==False:
          selectpoint=graphdraw.graph.nearestpoint(pygame.mouse.get_pos())
          mousedown=True
      elif event.type==MOUSEBUTTONUP:
        mousedown=False
      if mousedown==True:
        graphdraw.graph.move(selectpoint,pygame.mouse.get_pos())
    #Re-dessiner tout
    screen.blit(background, (0, 0))
    graphdraw.draw()
    pygame.display.flip()
#------------------------------------------------------------------------------

#Appel de la fonction main lorsque le module est exécuté
if __name__ == '__main__': main()

12 juillet 2007 10:34:49 :

Quelques fautes d'orthographe corrigées et une petite explication complémentaire de l'algo.