dmonde/lib/bresenham.py

"""Algorithme de Bresenham"""
from __future__ import division
from math import *
from dmF import *
 
dbg = True

def casesEntre(coord1, coord2, formeCases = "H"):
    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 coord1 != coord2:
        if formeCases == "H":
            retour = _brH(x1, y1, x2, y2)
        else:
            retour = _brC(x1, y1, x2, y2)
    else:
        retour = [coord1]

    # retourne la liste si les coordonnees ont ete interverties
    if inversee:
        retour.reverse()
    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*(y2-y1) + abs(x2 % 2) - abs(x1 % 1)):
        if dbg: print "*** V"
        retour = _brH_v(x1, y1, x2, y2)
    else:
        if dbg: print "*** H"
        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
    
    # 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
    if dbg: 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:
        if dbg: 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)"""
    #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

    # Calcul des ecarts
    dx = 1.5 * (x2 - x1)      #en x, on a 1.5u de centre a centre
    dy = y2 - y1             #en y, on compte en demi hauteurs
    if (x1 + x2) % 2 == 1: 
        if x1 % 2 == 0:
            dy += 0.5
        else:
            dy -= 0.5

    #k est la tangente de l'angle par rapport a la verticale
    k = dx/(dy*sqrt(3))
    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
            x, y = pos
            pos = x, y+1
            retour.append(pos)
            d += (k*pas)
        else:
            #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 -= 1.5
        if dbg: print "  > d = {} -> {}".format(d, pos)

    return retour           

# print casesEntre((0,0), (4,5)) 
# print casesEntre((1,0), (5,5))