Bresenham

18/04/2010 - 08:55 von Karsten Sosna | Report spam
Hallo NG,
folgende Routine zeigt die Berechnung des 1. Oktanten eines Kreises nach
Bresenham:
\\\
Dim retValue As New List(Of Point)

Dim x = r
Dim y = 0
Dim fehler = r

retValue.Add(New Point(x, y))

Do While y < x
Dim dy = y * 2 + 1
y = y + 1
fehler = fehler - dy
If fehler <= 0 Then
Dim dx = 1 - x * 2
x = x - 1
fehler = fehler - dx
End If
retValue.Add(New Point(x, y))
Loop
///
Das funktioniert auch, doch brauche ich jetzt den 2. Oktanten. Ich weiß, das
kann man durch Spiegelung der Koordinaten erreichen, aber das ist nicht
erwünscht. Also habe ich versucht obige Routine "umzubauen", nur berechnet
diese die Koordinaten falsch. Irgendwo habe ich dort einen Fehler in der
Berechnung der Variable "fehler" und/ oder dessen Vergleich.
\\\
fehler = r
Do While x > 0 'Richtig
Dim dx = 1 - x * 2
fehler = fehler - dx
x = x - 1 'Richtig
If fehler > r Then
Dim dy = y * 2 + 1
fehler = fehler - dy
y = y + 1 'Richtig
End If
retValue.Add(New Point(x, y))
Loop
///
Da man so schlecht sehen kann was ich meine habe ich unten nochmals ein
komplettes Beispiel angehàngt.

Danke für jede Hilfe.
Gruß Scotty

Hier das Beispiel
\\\
Public Class Form1
Private bm As New Bitmap(2 * 601, 2 * 601)

Private Sub Form1_Load(ByVal sender As Object, ByVal e As
System.EventArgs) Handles Me.Load
Dim pts1 = GetFullCircle(200)
Dim pts2 = BresenhamCircle(200)

'Mittelpunkt
bm.SetPixel(250, 250, Color.Blue)
For Each pt In pts1
bm.SetPixel(pt.X + 250, -pt.Y + 250, Color.Blue)
Next
For Each pt In pts2
bm.SetPixel(pt.X + 250, -pt.Y + 250, Color.Red)
Next
End Sub

Protected Overrides Sub OnPaint(ByVal e As
System.Windows.Forms.PaintEventArgs)
'MyBase.OnPaint(e)

e.Graphics.DrawImageUnscaled(bm, 0, 0)

End Sub

Private Function GetFullCircle(ByVal r As Int32) As List(Of Point)
Dim li() As List(Of Point) = {New List(Of Point), New List(Of
Point), New List(Of Point), New List(Of Point), New List(Of Point), New
List(Of Point), New List(Of Point), New List(Of Point)}

' Bresenham-Algorithmus für einen Achtelkreis im ersten Oktanten(0
bis 45°)

' Initialisierungen für den ersten Oktanten
Dim x = r
Dim y = 0
Dim fehler = r
' "schnelle" Richtung ist hier y!
'1.Oktant (0 bis 45°)
li(0).Add(New Point(x, y))
'2.Oktant (90 bis 45°)
li(1).Add(New Point(y, x))
'3.Oktant (90 bis 135°)
li(2).Add(New Point(-y, x))
'4.Oktant (180 bis 135°)
li(3).Add(New Point(-x, y))
'5.Oktant (180 bis 225°)
li(4).Add(New Point(-x, -y))
'6.Oktant (270 bis 225°)
li(5).Add(New Point(-y, -x))
'7.Oktant (270 bis 315°)
li(6).Add(New Point(y, -x))
'8.Oktant (360 bis 315°)
li(7).Add(New Point(x, -y))
Do While y < x
Dim dy = y * 2 + 1
y = y + 1
fehler = fehler - dy
If fehler <= 0 Then
Dim dx = 1 - x * 2
x = x - 1
fehler = fehler - dx
End If
'1.Oktant (0 bis 45°)
li(0).Add(New Point(x, y))
'2.Oktant (90 bis 45°)
li(1).Insert(0, New Point(y, x))
'3.Oktant (90 bis 135°)
li(2).Add(New Point(-y, x))
'4.Oktant (180 bis 135°)
li(3).Insert(0, New Point(-x, y))
'5.Oktant (180 bis 225°)
li(4).Add(New Point(-x, -y))
'6.Oktant (270 bis 225°)
li(5).Insert(0, New Point(-y, -x))
'7.Oktant (270 bis 315°)
li(6).Add(New Point(y, -x))
'8.Oktant (360 bis 315°)
li(7).Insert(0, New Point(x, -y))

Loop
li(1).RemoveAt(0)
li(2).RemoveAt(0)
li(3).RemoveAt(0)
li(4).RemoveAt(0)
li(5).RemoveAt(0)
li(6).RemoveAt(0)
li(7).RemoveAt(0)
If r Mod 2 = 0 Then
li(1).RemoveAt(0)
li(3).RemoveAt(0)
li(5).RemoveAt(0)
li(7).RemoveAt(0)
End If
Dim retValue As New List(Of Point)
For n = 0 To 7
retValue.AddRange(li(n))
Next
retValue.RemoveAt(retValue.Count - 1)
Return retValue
End Function

Public Function BresenhamCircle(ByVal r As Int32) As List(Of Point)
Dim retValue As New List(Of Point)

Dim x = r
Dim y = 0
Dim fehler = r

retValue.Add(New Point(x, y))

Do While y < x
Dim dy = y * 2 + 1
y = y + 1
fehler = fehler - dy
If fehler <= 0 Then
Dim dx = 1 - x * 2
x = x - 1
fehler = fehler - dx
End If
retValue.Add(New Point(x, y))
Loop

fehler = r
Do While x > 0 'Richtig
Dim dx = 1 - x * 2
fehler = fehler - dx
x = x - 1 'Richtig
If fehler > r Then
Dim dy = y * 2 + 1
fehler = fehler - dy
y = y + 1 'Richtig
End If
retValue.Add(New Point(x, y))
Loop

Return retValue

End Function

End Class
///
 

Lesen sie die antworten

#1 Thomas Scheidegger
18/04/2010 - 12:59 | Warnen spam
Hallo Karsten

Bild und Code unter (engl.):
http://en.wikipedia.org/wiki/Midpoi..._algorithm

zeigen eigentlich glasklar, wie die Pixels 'gespiegelt' werden.
Alles nur eine Frage der Vorzeichen _und_ Ausgangsposition.


Thomas Scheidegger - 'NETMaster'
http://dnetmaster.net/

Ähnliche fragen