dmonde/lib/bresenham.py

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

def casesEntre(coord1, coord2, formeCases = "H"):
    if coord1 != coord2:
        if formeCases == "H":
            retour = _brH(coord1, coord2)
        else:
            retour = _brC(coord1, coord2)
    else:
        retour = [coord1]
    return retour

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

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

    # retourne la liste si les coordonnees ont ete interverties
    if inversee:
        retour.reverse()
    return retour

def _brH(coord1, coord2):
    """Algorithme ligne de Bresenham (pour cases hexagonales)"""
    x1, y1 = coord1
    x2, y2 = coord2
    if x1%2 == 1: y1 += 0.5
    if x2%2 == 1: y2 += 0.5

    # on inverse les coord si necessaire (si on va de droite a gauche)
    inversee = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        inversee = True
    
    #calcul selon secteur
    if 2*abs(y2 - y1) >= abs(x2 - x1):
        print "*** V"
        resultat = _brH_v(x1, y1, x2, y2)
    else:
        print "*** H"
        resultat = _brH_h(x1, y1, x2, y2)   

    print "res: ", resultat
#     retour = resultat
    retour = []
    for x, y in resultat:
        if x % 2 == 1: y -= 0.5
        retour.append((x,y))

    # retourne la liste si les coordonnees ont ete inversees
    if inversee:
        retour.reverse()   
    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
    
    # Calcul de l'erreur  (l'ecart qui doit s'accumuler au fur et a mesure qu'on avance)
    error = 0.0
    pasY = 1 if y1 < y2 else -1
    print "# de: {}|{} vers {}|{}".format(x1, y1, x2, y2)
    
    # on itere sur les coordonnees de la boite qui contient les coordonnees 1 et 2
    retour = []
    x, y = x1, y1
    #ky: decalage entre cases paires et impaires
    ky = 0
    
    while not x > x2:
        print "  > {}, {}, {}, {}".format(x, y, pasY * ky, error)
        
        coord = (x, y + (pasY * ky))
        retour.append(coord)
        
        x += 1
        ky = 0.5 if (x - x1) % 2 == 1 else 0
        
        error += (0.9087 * (abs(dy) / dx))
        if error > 0.5 + ky:                   
            y += pasY
            error -= 1
                      
    return retour
    
def _brH_v(x1, y1, x2, y2):
    """Algorithme ligne de Bresenham (pour cases hexagonales - secteur vertical)"""
    # Calcul des ecarts
    dx = x2 - x1
    dy = y2 - y1
    signeDy = 1 if dy > 0 else -1
    
    error = 0.0
    pasY = 0.5 if y1 < y2 else -0.5
    
    print "# de: {}|{} vers {}|{}".format(x1, y1, x2, y2)
    
    # on itere sur les coordonnees de la boite qui contient les coordonnees 1 et 2
    retour = []
    x, y = x1, y1
    while not (signeDy * y) > (signeDy * y2):
        print "  > {}, {}, {}, {}".format(x, y, pasY, error)
        if (x%2 == 0 and y == int(y)) or (x%2 == 1 and y != int(y)):
            coord = (x, y)      #la case existe
            retour.append(coord)
            seuil = 0.2886  #a la prochaine position, on sera entre 2 cases
        else:
            seuil = 0.5773  #la prochaine position sera une vraie case
            
        y += pasY
        error += (0.5 * (dx / abs(dy)))
        if error > seuil:                   
            x += 1
            error -= 1.1547

    return retour