dmonde/lib/br.py

"""Algorithme de Bresenham"""
from __future__ import division
from math import sqrt

def ligne(coord1, coord2, formeCases = "H"):
    if coord1[0] != coord2[0] or coord1[1] != coord2[1]:
        if len(coord1) == 2 and len(coord2) == 2:
            retour = _ligne2d(coord1, coord2, formeCases)
        elif len(coord1) == 3 and len(coord2) == 3:
            retour = _ligne3d(coord1, coord2, formeCases)
        elif len(coord1) == 2 and len(coord2) == 3: 
            x1, y1 = coord1
            retour = _ligne3d((x1, y1, 0), coord2, formeCases)
        elif len(coord1) == 2 and len(coord2) == 3: 
            x2, y2 = coord2
            retour = _ligne3d(coord1, (x2, y2, 0), formeCases)
        else:
            retour = [coord1]   
    else:            
        retour = [coord1]
         
    return retour    
                
def _ligne2d(coord1, coord2, formeCases = "H"):
    """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

    # on inverse les coord si necessaire (si on va de gauche a droite)
    inversee = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        inversee = True

    if formeCases == "H":
        retour = _brH(x1, y1, x2, y2)
    else:
        retour = _brC(x1, y1, x2, y2)
        
    # retourne la liste si les coordonnees ont ete interverties
    if inversee:
        retour.reverse()
    return retour


def _ligne3d(coord1, coord2, formeCases = "H"):
    """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 = _ligne2d((x1, y1), (x2, y2), formeCases)
    ligneZ = _brC(0, z1, (len(ligne)-1), z2)
    
    retour = []
    for coordZ in ligneZ:
        dist, z = coordZ
        x, y = ligne[dist]
        retour.append((x, y, z))
        
    return retour

def _brC(x1, y1, x2, y2):
    """Algorithme ligne de Bresenham (pour cases carrees)"""

    # on verifie si la ligne est plus verticale qu'horizontale
    estVerticale = abs(y2 - y1) > abs(x2 - x1)
    if estVerticale:
        x1, y1 = y1, x1
        x2, y2 = y2, x2  

    # Calcul des ecarts
    dx = x2 - x1
    dy = y2 - y1
 
    # Calcul de l'erreur  (l'ecart qui doit s'accumuler au fur et a mesure qu'on avance)
    #2dx est l'unite, de maniere a travailler avec des entiers
    error = 0.0
    pasY = 1 if y1 < y2 else -1
 
    # on itere sur les coordonnees de la boite qui contient les coordonnees 1 et 2
    y = y1
    retour = []
    for x in range(x1, x2 + 1):
        coord = (y, x) if estVerticale else (x, y)
        retour.append(coord)
        error += (abs(dy) / dx)
        if error > 0.5:
            y += pasY
            error -= 1.0

    return retour

def _brH(x1, y1, x2, y2):
    """Algorithme ligne de Bresenham (pour cases hexagonales)"""
    #calcul selon secteur
    if abs(x2 - x1) < (2*abs((y2-y1)) + abs(x2 % 2) - abs(x1 % 1)):
        retour = _brH_v(x1, y1, x2, y2)
    else:
        retour = _brH_h(x1, y1, x2, y2)   
    return retour
        
def _brH_h(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: 
        if x1 % 2 == 0:
            dy += 0.5
        else:
            dy -= 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(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