[SciPy-User] Bresenham algorithm?

[Sturla Molden]

David Warde-Farley skrev:Here's an implementation I found here: 
http://mail.python.org/pipermail/python-list/1999-July/007163.html


> def bresenham(x,y,x2,y2):
>      """Brensenham line algorithm"""
>      steep = 0
>      coords = []
>      dx = abs(x2 - x)
>      if (x2 - x) > 0: sx = 1
>      else: sx = -1
>      dy = abs(y2 - y)
>      if (y2 - y) > 0: sy = 1
>      else: sy = -1
>      if dy > dx:
>          steep = 1
>          x,y = y,x
>          dx,dy = dy,dx
>          sx,sy = sy,sx
>      d = (2 * dy) - dx
>      for i in range(0,dx):
>          if steep: coords.append((y,x))
>          else: coords.append((x,y))
>          while d >= 0:
>              y = y + sy
>              d = d - (2 * dx)
>          x = x + sx
>          d = d + (2 * dy)
>  

We're on the NumPy mailing list here. Do this istead ;-)

import numpy as np
cimport numpy as np
cimport cython

cdef extern from "math.h":
     int abs(int i)

@cython.boundscheck(False)
@cython.wraparound(False)
def bresenham(int x, int y, int x2, int y2):

     cdef np.ndarray[np.int32_t, ndim=2, mode="c"] coords 

     cdef int steep = 0
     cdef int dx = abs(x2 - x)
     cdef int dy = abs(y2 - y)
     cdef int sx, sy, d, i

     coords = np.zeros(dx, dtype=np.int32)
     if (x2 - x) > 0: sx = 1
     else: sx = -1
     if (y2 - y) > 0: sy = 1
     else: sy = -1
     if dy > dx:
         steep = 1
         x,y = y,x
         dx,dy = dy,dx
         sx,sy = sy,sx
     d = (2 * dy) - dx
     for i in range(dx):
         if steep:
             coords[i,0] = y
             coords[i,1] = x
         else:
             coords[i,0] = x
             coords[i,1] = y
         while d >= 0:
             y = y + sy
             d = d - (2 * dx)
         x = x + sx
         d = d + (2 * dy)
     return coords


Regards,
Sturla