Bresenham-Algorithmus

[sea-live]

gibt es in python hier en beispiel für den rasteralgorythmuss

[BlackJack]

Der ist nicht wirklich abhängig von der Programmiersprache, solange sie imperativ ist. Es sollten im Netz genügend Beispiele zu finden sein.

[sea-live]

Danke werde ich mal versuchen das so hinzubekommen

nachdem ich mit mein toller HPGL viewer in python nun fertig habe


soll ja auch die fräse das teil bearbeiten

[HerrHagen]

Hallo,

hatte irgendwann mal das:

Code: Alles auswählen

def line(mat, y1, x1, y2, x2, color=255):
    """
    Draw not antialiased line in mat.

    >>> x = numpy.zeros((6, 10), dtype='int8')
    >>> line(x, -2, -2, 4, 4, color=1)
    >>> x
    array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
           [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
           [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
           [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int8)    
    """

    y1, x1, y2, x2 = map(int, (y1, x1, y2, x2))
    
    if abs(x2-x1)>=abs(y2-y1):
        length = max((x2, x1)) - min((x2, x1)) + 1
        x = numpy.linspace(x1, x2, num=length)
        y = numpy.linspace(y1, y2, num=length)
    else:
        length = max((y2, y1)) - min((y2, y1)) + 1
        x = numpy.linspace(x1, x2, num=length)
        y = numpy.linspace(y1, y2, num=length)

    #           line in mat (x)      |      line in mat (y)
    mask = (0<=x) & (x<mat.shape[1]) & (0<=y) & (y<mat.shape[0])

    x = x.astype('int')[mask]
    y = y.astype('int')[mask]
    mat[y, x] = color

implementiert. Vielleicht nützt dir das ja was. Ist nicht der Bresham Algorithmus, aber für die meißten Dinge schnell genug.

[EyDu]

Da geht aber noch etwas:

Code: Alles auswählen

def line(mat, y1, x1, y2, x2, color=255):
    y1, x1, y2, x2 = map(int, (y1, x1, y2, x2))

    (a, b) = (y1, y2) if abs(x2-x1)<abs(y2-y1) else (y1, y2)

    length = max(a, b) - min(a, b) + 1
    x = numpy.linspace(x1, x2, num=length)
    y = numpy.linspace(y1, y2, num=length)

    mask = +(0<=x<mat.shape[1] and 0<=y<mat.shape[0])

    x = x.astype('int')[mask]
    y = y.astype('int')[mask]
    mat[y, x] = color

Bis du sicher, dass du oben nur "int" verwenden möchtest, ohne vorher zu runden?

[HerrHagen]

Dein Beispiel funktioniert leider nicht.

Code: Alles auswählen

>>> a = numpy.zeros((7,7))
>>> line(a, 2,2, 4,4)

Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    line(a, 2, 2, 4, 4)
  File "C:/Python25/test/line.py", line 10, in line
    mask = +(0<=x<mat.shape[1] and 0<=y<mat.shape[0])
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

Bis du sicher, dass du oben nur "int" verwenden möchtest, ohne vorher zu runden?

Ja.

[wuf]

Hallo sea-live

Hier noch eine anderer Variante für den Bresenham-Algorithmus ohne numpy-Modul:

Code: Alles auswählen

    def line(self, x0, y0, x1, y1):
        """Brensenham Linien Algorithmus"""

        steep = 0
        coords = []

        dx = abs(x1 - x0)
        dy = abs(y1 - y0)

        if (x1 - x0) > 0:
            sx = 1
        else:
            sx = -1

        if (y1 - y0) > 0:
            sy = 1
        else:
            sy = -1

        if dy > dx:
            steep = 1
            x0,y0 = y0,x0
            dx,dy = dy,dx
            sx,sy = sy,sx

        d = (2 * dy) - dx
        for i in range(0,dx):
            if steep:
                coords.append((y0,x0))
            else:
                coords.append((x0,y0))

            while d >= 0:
                y0 = y0 + sy
                d = d - (2 * dx)

            x0 = x0 + sx
            d = d + (2 * dy)

        coords.append((x1,y1))

        return(coords)

Gruss wuf

[wuf]

Hier noch der Bresenham-Algorithmus für einen Kreis:

Code: Alles auswählen

import Tkinter as tk

app_win = tk.Tk()
draw_plane = tk.Canvas(app_win, width=600, height=400, bg="black")
draw_plane.pack()

def circle(x0, y0, radius):
    """Bresenham Kreis-Algorithmus"""

    x = 0
    y = radius

    f = 1 - radius
    f_x = 0
    f_y = -2 * radius
 
    coords = list()

    coords.append(( x0, y0+radius))
    coords.append(( x0, y0-radius))
    coords.append(( x0+radius, y0))
    coords.append(( x0-radius, y0))

    while x < y:
        if f >= 0:
            y -= 1
            f_y += 2
            f += f_y

        x += 1
        f_x += 2
        f += f_x + 1

        coords.append(( x0+x, y0+y))
        coords.append(( x0-x, y0+y))
        coords.append(( x0+x, y0-y))
        coords.append(( x0-x, y0-y))
        coords.append(( x0+y, y0+x))
        coords.append(( x0-y, y0+x))
        coords.append(( x0+y, y0-x))
        coords.append(( x0-y, y0-x))

    return coords

def create_point(plane, coord, color='yellow'):
    """Zeichnet einen Punkt"""
    x, y = coord
    plane.create_line(x, y, x+1, y+1, fill=color)

for coord in circle(300, 200, 150):
    create_point(draw_plane, coord)

app_win.mainloop()

Gruss wuf