dmonde/lib/geometrie.py

# -*- 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