Bresenham-Algorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Bresenham-Algorithmus

Beitragvon sea-live » Samstag 17. Januar 2009, 16:34

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

Beitragvon BlackJack » Samstag 17. Januar 2009, 17:46

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
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Beitragvon sea-live » Samstag 17. Januar 2009, 17:51

Danke werde ich mal versuchen das so hinzubekommen

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

soll ja auch die fräse das teil bearbeiten
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Beitragvon HerrHagen » Samstag 17. Januar 2009, 18:31

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
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Sonntag 18. Januar 2009, 14:36

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?
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Beitragvon HerrHagen » Sonntag 18. Januar 2009, 14:57

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. :wink:
Benutzeravatar
wuf
User
Beiträge: 1374
Registriert: Sonntag 8. Juni 2003, 09:50

Beitragvon wuf » Samstag 14. Februar 2009, 11:24

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 :wink:
Take it easy Mates!
Benutzeravatar
wuf
User
Beiträge: 1374
Registriert: Sonntag 8. Juni 2003, 09:50

Beitragvon wuf » Sonntag 15. Februar 2009, 16:35

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 :wink:
Take it easy Mates!

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]