# -*- coding: utf-8 -*- ''' Fonctions geometriques DMonde ''' from __future__ import division from math import sqrt, atan2, pi, tan import time from PyQt4.QtCore import QPointF, QLineF from PyQt4.QtGui import QPolygonF class Geometrie(object): def __init__(self, fC = "H", dimX = 0, dimY = 0): self._fC = fC self._dimX = dimX self._dimY = dimY def initialiser(self, plateau): self._fC = plateau.formeCases self._dimX = plateau.nbCasesX self._dimY = plateau.nbCasesY def listeCases(self): """retourne la liste des cases composant le plateau en fonction de ses dimensions""" retour = [] for x in range(self._dimX): for y in range(self._dimY): retour.append( (x, y) ) return retour def listeCasesF(self, xmin, ymin, xmax, ymax): """liste de cases filtree (performances)""" retour = [] if xmin < 0: xmin = 0 if ymin < 0: ymin = 0 if xmax > self._dimX: xmax = self._dimX if ymax > self._dimY: ymax = self._dimY for x in range(xmin, xmax + 1): for y in range(ymin, ymax + 1): retour.append( (x, y) ) return retour def polygone(self, x, y): """renvoie l'objet graphique hexagone de la case de coordonnees (x, y)""" polygone = QPolygonF() if self._fC == "H": #si x est impair sur un plateau a cases hexagonales, le y est augmente de 0.5 if 1 == (x % 2): y += 0.5 polygone << QPointF(((x*0.866)+0.2886)*120, y*120) \ << QPointF(((x*0.866)+0.866)*120, y*120) \ << QPointF(((x*0.866)+1.1547)*120, (y+0.5)*120) \ << QPointF(((x*0.866)+0.866)*120, (y+1)*120) \ << QPointF(((x*0.866)+0.2886)*120, (y+1)*120) \ << QPointF( (x*0.866)*120, (y+0.5)*120) else: polygone << QPointF(x*120, y*120) \ << QPointF((x+1)*120, y*120) \ << QPointF((x+1)*120, (y+1)*120) \ << QPointF(x*120, (y+1)*120) return polygone def polygoneAgglo(self, listeCases): """renvoie un polygone contruit par agglomeration des polygones des cases de la liste les cases doivent etre adjacentes (cases hexagonales ou carrees)""" segments = [] #on parcourt les faces des polygones des cases, et on ne garde que ceux qui n'ont pas de case 'en face' for coord in listeCases: polygone = self.polygone(coord[0], coord[1]) voisins = self.lstCoordAdjacentes(coord[0], coord[1]) for i in range(0, len(voisins)): if not voisins[i] in listeCases: j = i+1 if j > len(voisins) - 1: j = 0 segments.append(QLineF(polygone[i], polygone[j])) #on 'accroche' les segments les uns aux autres, dans l'ordre if not len(segments) > 0: return None segments2 = [segments[0]] for segment2 in segments2: for segment in segments: if not QLineF(segment.p1(), segment.p2()) in segments2 and not QLineF(segment.p2(), segment.p1()) in segments2: if sqrt((segment.p1().x()-segment2.p2().x())**2+(segment.p1().y()-segment2.p2().y())**2) < 1: segments2.append(QLineF(segment.p1(), segment.p2())) elif sqrt((segment.p2().x()-segment2.p2().x())**2+(segment.p2().y()-segment2.p2().y())**2) < 1: segments2.append(QLineF(segment.p2(), segment.p1())) pointsPolygone = [] premierPoint = segments2[0].p1() pointsPolygone.append(premierPoint) for segment in segments2: pointSuivant = segment.p2() if pointSuivant != premierPoint: pointsPolygone.append(pointSuivant) #creation du polygone polygone = QPolygonF() for point in pointsPolygone: polygone.append(point) return polygone def coordonneesValides(self, coord): """les coordonnees entrees en parametre sont elles celles d'une case du plateau""" return (coord[0] >= 0 and coord[1] >= 0 and coord[0] < self._dimX and coord[1] < self._dimY) def filtrer(self, lst): """prend en parametre une liste de coordonnees et retourne une liste de coordonnees valides""" retour = [] for coord in lst: x, y = coord[0], coord[1] if self.coordonneesValides((x, y)): retour.append(coord) return retour def coordCentreListeCases(self, listeCases): """renvoie les coordonnees centrales d'une liste de cases""" retour = None if len(listeCases) > 0: listeTriee = sorted(listeCases) posMilieu = int(len(listeCases)/2) retour = listeTriee[posMilieu] return retour def lstCoordAdjacentes(self, x, y): """renvoie la liste des coordonnees adjacentes, !!! -> sans condition d'existence sur le plateau attention: l'ordre est important""" if self._fC == "H": if 1 == (x % 2): return [(x, y-1), (x+1, y), (x+1, y+1), (x, y+1), (x-1, y+1), (x-1, y)] else: return [(x, y-1), (x+1, y-1), (x+1, y), (x, y+1), (x-1, y), (x-1, y-1)] else: return [(x, y-1), (x+1, y), (x, y+1), (x-1, y)] def yR(self, x, y): """retourne le y reel lorsque les cases sont hexagonales""" return y if self._fC != "H" or x % 2 != 1 else y + 0.5 def zone(self, centre, param): """renvoie un dictionnaire representant la liste des coordonnees des cases comprises dans la zone la zone en question est la liste des cases situees a une distance d des coordonnees d'origine""" # if len(param) == 2: # #on vise des coordonnees cible = param if type(param) == tuple else (-1, -1) rayon = param if type(param) == int else 99 if not self.coordonneesValides(centre) or not rayon >= 0: return {} resultat = {} aVerifier = [] ; aVerifier2 = [] ; k = 0 #on part de la premiere case, puis on itere a partir de chaque nouveau depart sur les voisins aVerifier.append(centre) while k <= rayon: for x, y in aVerifier: for coord in self.filtrer(self.lstCoordAdjacentes(x, y)): if not coord in aVerifier and not coord in aVerifier2 and not coord in resultat: aVerifier2.append(coord) for elt in aVerifier: resultat[elt] = k if elt == cible: rayon = k aVerifier = aVerifier2 ; aVerifier2 = [] ; k += 1 return resultat def zone3d(self, centre, rayon): """ centre au format (x, y, z) renvoie les cases de la zone au format (x, y, z)""" retour = [] x0, y0, z0 = centre zone = self.zone((x0, y0), rayon) for coord in zone: x, y = coord dz = rayon - zone[coord] for z in range(-dz, dz + 1): retour.append( (x, y, (z0 + z) ) ) return retour def blocAdjacent(self, listeCases): """renvoie un bloc de cases adjacentes a partir de la liste en parametre""" retour = [] tmp1 = [listeCases[0]]; tmp2 = [listeCases[0]] while len(tmp2) > 0: tmp2 = [] #on liste les cases voisines qui sont dans la liste et pas encore verifiees for x, y in tmp1: for voisine in self.lstCoordAdjacentes(x, y): if voisine in listeCases and not voisine in tmp1 and not voisine in tmp2: tmp2.append(voisine) #chacune de ces cases prend le statut de verifiee for coord in tmp1: listeCases.remove(coord) retour.append(coord) tmp1 = tmp2 return retour def ligne(self, coord1, coord2): """renvoie la ligne demandee en fonction des parametres""" if coord1[0] == coord2[0] and coord1[1] == coord2[1]: return [coord1] if len(coord1) == 2 and len(coord2) == 2: return self._ligne2d(coord1, coord2) elif len(coord1) == 3 and len(coord2) == 3: return self._ligne3d(coord1, coord2) elif len(coord1) == 3 and len(coord2) == 2: return self._ligne3d((coord1[0], coord1[1], 0), coord2) elif len(coord1) == 2 and len(coord2) == 3: return self._ligne3d(coord1, (coord2[0], coord2[1], 0)) else: return [coord1] def _ligne2d(self, coord1, coord2): """renvoie la liste des cases traversees par la ligne entre les cases 1 et 2 prend en parametre des coord de la forme (x,y)""" x1, y1 = coord1 ; x2, y2 = coord2 return self._brH(x1, y1, x2, y2) if self._fC == "H" else self._brC(x1, y1, x2, y2) def _ligne3d(self, coord1, coord2): """renvoie la liste des cases traversees par la ligne entre les cases 1 et 2 prend en parametre des coord de la forme (x,y, z)""" x1, y1, z1 = coord1 ; x2, y2, z2 = coord2 ligne = self._ligne2d((x1, y1), (x2, y2)) ligneZ = self._brC(0, z1, (len(ligne)-1), z2) retour = [] for dist, z in ligneZ: x, y = ligne[dist] retour.append((x, y, z)) return retour def _brC(self, x1, y1, x2, y2): """Algorithme ligne de Bresenham (pour cases carrees)""" retour = [] #SYMETRIE DIAGONALE V = ( abs(y2 - y1) > abs(x2 - x1) ) if V: y1, x1, y2, x2 = x1, y1, x2, y2 #SYMETRIE VERTICALE inversee = (x1 > x2) if inversee: x2, y2, x1, y1 = x1, y1, x2, y2 DX = x2 - x1 ; DY = y2 - y1 decalage = 0.0 saut = 1 if DY > 0 else -1 alpha = ( abs( DY ) / DX ) y = y1 for x in range(x1, x2 + 1): coord = (y, x) if V else (x, y) retour.append(coord) decalage += alpha if decalage > 0.5: y += saut decalage -= 1.0 if inversee: retour.reverse() return retour def _brH(self, x1, y1, x2, y2): """Algorithme ligne de Bresenham (pour cases hexagonales)""" inversee = (x1 > x2) if inversee: x1, x2 = x2, x1 y1, y2 = y2, y1 #calcul selon secteur if abs(x2 - x1) < (2*abs((y2-y1)) + abs(x2 % 2) - abs(x1 % 1)): retour = self._brH_v(x1, y1, x2, y2) else: retour = self._brH_h(x1, y1, x2, y2) # retourne la liste si les coordonnees ont ete interverties if inversee: retour.reverse() return retour def _brH_h(self, x1, y1, x2, y2): """Algorithme ligne de Bresenham (pour cases hexagonales - secteur horizontal)""" # Calcul des ecarts dx = x2 - x1 ; dy = y2 - y1 if (x1 + x2) % 2 == 1: dy += 0.5 if x1 % 2 == 0 else -0.5 # Calcul de l'erreur (l'ecart qui doit s'accumuler au fur et a mesure qu'on avance) k = dy / dx pas = 1 # on itere sur les coordonnees de la boite qui contient les coordonnees 1 et 2 retour = [] d = 0.0 pos = (x1, y1) retour.append(pos) while pos != (x2, y2): d += k*pas if d > 0: #on se deplace vers la case en dessous a droite x, y = pos if x % 2 == 0: pos = x + 1, y else: pos = x + 1, y + 1 retour.append(pos) d -= 0.5 else: #on se deplace vers la case au dessus a droite x, y = pos if x % 2 == 0: pos = x + 1, y - 1 else: pos = x + 1, y retour.append(pos) d += 0.5 if pos[0] > x2: retour = [] break return retour def _brH_v(self, x1, y1, x2, y2): """Algorithme ligne de Bresenham (pour cases hexagonales - secteur vertical)""" #on prend comme unite la demi largeur: u = 0.5773 #la demi hauteur d'un hexa vaut donc 0.8860u, ou sqrt(3)/2 #[a revoir] une fois cela pose, on muliplie tout par 4dy afin d'eviter nombres flottants et divisions sens = 1 if y2 > y1 else -1 # Calcul des ecarts dx = 1.5 * (x2 - x1) #en x, on a 1.5u de centre a centre dy = sens * (y2 - y1) #en y, on compte en demi hauteurs if (x1 + x2) % 2 == 1: if x1 % 2 == 0: dy += sens*0.5 else: dy -= sens*0.5 k = dx/(dy*sqrt(3)) #k est la tangente de l'angle par rapport a la verticale pas = 0.5*sqrt(3) #on avance par demi hauteurs retour = [] d = 0.0 #decalage pos = (x1, y1) retour.append(pos) while pos != (x2, y2): d += (k*pas) if d <= 0.5: #on se deplace vers la case en dessous (ou au dessus) x, y = pos pos = x, y + sens retour.append(pos) d += (k*pas) else: #on se deplace vers la case en dessous (ou au dessus) a droite x, y = pos if (x %2 == 0 and sens == 1) or (x % 2 == 1 and sens == -1): pos = x + 1, y else: pos = x + 1, y + sens retour.append(pos) d -= 1.5 if sens*pos[1] > sens*y2: retour = [] break return retour def disque(self, coord1, coord2): """rendu pas terrible pour l'instant (a cause du decalage des cases?)""" x1, y1 = coord1 ; x2, y2 = coord2 retour = [] # k = 1.1547 if self._fC == "H" else 1 k = 1 rayon2 = (y2 - y1)**2 + (k* x2 - k* x1)**2 for x, y in self.listeCases(): if (k*x - k*x1)**2 + (self.yR(x, y) - self.yR(x1, y1))**2 <= (rayon2 + 0.25): retour.append((x, y)) return retour def cone_(self, coord1, coord2, iAngle = 2): """version disque""" """on trace un disque et on compare les angles""" x1, y1 = coord1 ; x2, y2 = coord2 retour = [] if self._fC == "H" and 1 == (x1 % 2): y1 += 0.5 if self._fC == "H" and 1 == (x2 % 2): y2 += 0.5 if iAngle < 0: iAngle = 0 if iAngle > 4: iAngle = 4 angle = pi/[16, 12, 8, 6, 4][iAngle] # c'est le demi angle! disque = self.disque(coord1, coord2) alpha0 = atan2((x2 - x1), (y2 - y1)) for coord in disque: x, y = coord d = sqrt( (y - y1)**2 + (x - x1)**2 ) if self._fC == "H" and 1 == (x % 2): y += 0.5 tolerance = 0.5 * atan2(1, d) #la tolerance est l'angle d'une case a la distance en cours if self.coordonneesValides( (x, y) ): alpha = atan2( (x - x1) , (y - y1) ) if abs(alpha - alpha0) <= (angle + tolerance) or \ ( 2*pi - abs(alpha - alpha0) ) <= (angle + tolerance): if self._fC == "H" and 1 == (x % 2): y -= 0.5 retour.append( (x, y) ) return retour def cone__(self, coord1, coord2, iAngle = 2): """version zone""" """on trace un disque et on compare les angles""" x1, y1 = coord1 ; x2, y2 = coord2 retour = {} if self._fC == "H" and 1 == (x1 % 2): y1 += 0.5 if self._fC == "H" and 1 == (x2 % 2): y2 += 0.5 if iAngle < 0: iAngle = 0 if iAngle > 4: iAngle = 4 angle = pi/[16, 12, 8, 6, 4][iAngle] # c'est le demi angle! disque = self.zone(coord1, coord2) alpha0 = atan2((x2 - x1), (y2 - y1)) for coord, d in disque.items(): x, y = coord if self._fC == "H" and 1 == (x % 2): y += 0.5 tolerance = 0.5 * atan2(1, d) #la tolerance est l'angle d'une case a la distance en cours if self.coordonneesValides( (x, y) ): alpha = atan2( (x - x1) , (y - y1) ) if abs(alpha - alpha0) <= (angle + tolerance) or \ ( 2*pi - abs(alpha - alpha0) ) <= (angle + tolerance): if self._fC == "H" and 1 == (x % 2): y -= 0.5 retour[(x, y)] = d return retour def cone(self, coord1, coord2, iAngle): """renvoie un dictionnaire representant la liste des coordonnees des cases comprises dans le cone et leur distance a l'origine""" resultat = {} aVerifier = [] ; aVerifier2 = [] ; k = 0 ; rayon = 99 ; x1, y1 = coord1 ; x2, y2 = coord2 if iAngle < 0: iAngle = 0 if iAngle > 4: iAngle = 4 angle = pi/[16, 12, 8][iAngle] # c'est le demi angle! alpha0 = atan2( (x2 - x1), (y2 - y1) ) #on part de la premiere case, puis on itere a partir de chaque nouveau depart sur les voisins aVerifier.append(coord1) while k <= rayon: for x, y in aVerifier: for coordV in self.filtrer(self.lstCoordAdjacentes(x, y)): if not coordV in aVerifier and not coordV in aVerifier2 and not coordV in resultat: xv, yv = coordV tolerance = 0.5 * atan2(1, k) #la tolerance est l'angle d'une case a la distance en cours alpha = atan2( (xv - x1) , (yv - y1) ) if abs(alpha - alpha0) <= (angle + tolerance) or \ ( 2*pi - abs(alpha - alpha0) ) <= (angle + tolerance): aVerifier2.append(coordV) for elt in aVerifier: resultat[elt] = k if elt == coord2: rayon = k aVerifier = aVerifier2 ; aVerifier2 = [] ; k += 1 return resultat def cone3d(self, coord1, coord2, iAngle = 1): x1, y1, z1 = coord1 ; x2, y2, z2 = coord2 #on recupere le cone horizonthal coneH = self.cone( (x1, y1), (x2, y2), iAngle ) #la ligne de mire d = max([d for d in coneH.values()]) ligneZ = self._brC(0, z1, d, z2) if iAngle < 0: iAngle = 0 if iAngle > 4: iAngle = 4 angle = pi/[16, 12, 8][iAngle] # c'est le demi angle! retour = [] for coord, dist in coneH.items(): #calcul de l'ecart de hauteur z0 = ligneZ[dist][1] dz = int(round(dist * tan(angle))) for z in range(-dz, dz + 1): x, y = coord retour.append( (x, y, (z0 + z)) ) return retour if __name__ == "__main__": geo = Geometrie("C", 200, 200) c = geo.cone( (0,0), (5,5), 2) print c