Draw Line - Riehl'sche Algorhytmus

[Developer_X]

hi, ich wollt mich selbst mal an einem Algorhytmus versuchen, eine Linie zu zeichnen in java, ich bin ja fleißig am lesen, und las auch etwas über den Algorhytmus von Bresenham, durch den man Linien zeichnen konnte.

Nun denn, ich machte mich an die Arbeit:

package main;

import java.awt.*;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;

import javax.swing.*;

@SuppressWarnings("serial")
public class Main extends JFrame
{
	int x = 100;
	int y = 100;
	
	public Main()
	{
		setTitle("Riehl'sche Algorithmus");
		setSize(200,200);
		setLayout(new BorderLayout());
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		JPanel p = new JPanel()
		{
			public void paintComponent(Graphics g)
			{
				g.setColor(Color.white);
				g.fillRect(0,0,getSize().width,getSize().height);
				
				g.setColor(Color.red);
				drawLine(g,new Vector2D(x-1,y-1),new Vector2D(100,100));
			}
		};
		p.addMouseMotionListener(new MouseMotionListener()
		{
			public void mouseDragged(MouseEvent arg0)
			{
				x = arg0.getX();
				y = arg0.getY();
				repaint();
			}
			public void mouseMoved(MouseEvent arg0)
			{
			}
		});
		add(p,"Center");
		setVisible(true);
	}
	public void drawLine(Graphics g, Vector2D a, Vector2D b)
	{
	//	Continue
		float d = (float) a.getDistance(b);
		float dx = (float) (b.x-a.x);
		float dy = (float) (b.y-a.y);
		
		float x = (float) a.x;
		float y = (float) a.y;
		
		if(a.x==b.x&&a.y==b.y)
		{
			drawPixel(g,x,y);
		}
		else if(a.x==b.x)
		{
			x = (float) a.x;
			for(;;)
			{
				if(y>b.y)
				{
					break;
				}
				else
				{
					y+=dy/d;
				}
				drawPixel(g,x,y);
			}
		}
		else if(a.y==b.y)
		{
			y = (float) a.y;
			for(;;)
			{
				if(x>b.x)
				{
					break;
				}
				else
				{
					x+=dx/d;
				}
				drawPixel(g,x,y);
			}
		}
		else
		{
			if(x>b.x&&y>b.y)
			{
				for(;;)
				{
					if(x<b.x&&y<b.y)
					{
						break;
					}
					else
					{
						if(x>b.x)
						{
							x -= dx/d;
						}
						if(y>b.y)
						{
							y -= dy/d;
						}
					}
					drawPixel(g,x,y);
				}
			}
			else if(x<b.x&&y>b.y)
			{
				
			}
			else if(x>b.x&&y<b.y)
			{
				
			}
			else
			{
				for(;;)
				{
					if(x>b.x&&y>b.y)
					{
						break;
					}
					else
					{
						if(x<b.x)
						{
							x += dx/d;
						}
						if(y<b.y)
						{
							y += dy/d;
						}
					}
					drawPixel(g,x,y);
				}
			}
		}
	}
	public void drawPixel(Graphics g, float x, float y)
	{
		g.drawLine((int)x,(int)y,(int)x,(int)y);
	}
	public static void main(String[]args)
	{
		new Main();
	}
}

Das Problem:
Wenn der Punkt A kleiner als Punkt B ist, also in X und Y Coordinate funktioniert alles prima, andernfalls, nichts.
Warum?
Irgendwo funktionieren die schleifen net, ich hab mein bestes versucht kriegs aber leider alleine nicht hin, kann mir bitte einer helfen?

Developer_X

Achtung!
Beim ausprobieren könnt ihr mit meinem Algorhytmus wirklich linien ziehen, aber nur wenn ihr im 2.Quadranten seit, ansonsten spinnt es irgendwo off, und dann geht die schleife ewig.
PS:
Bin jetzt noch beim ersten Buch in Kapitel 4.2

 

[Marco13]

Hab' den Algorithmus jetzt nicht nachvollzogen, aber beim "klassischen" Bresenham ist es (wenn ich mich recth erinnere (und das ist jetzt schon >10 Jahre her (ich werd alt))) "normal", dass man nur in einem Oktanten die Zahlen berechnen kann, und die übrigen durch Spiegelungen (oder rotationen um 90°, also vertauschen von x/y) erreicht werden. GANZ grob also: Am Anfang von "drawLine" abfragen, welcher Fall vorliegt, und entsprechend geänderte Methoden(teile) aufrufen.

 

[Hansdampf]

public class Bresenham {
	int x1, y1, x2, y2;
	int d, x, y, ax, ay, sx, sy, dx, dy;

	public void set(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
		dx = x2 - x1;
		ax = Math.abs(dx) << 1;
		sx = dx < 0 ? -1 : 1;
		dy = y2 - y1;
		ay = Math.abs(dy) << 1;
		sy = dy < 0 ? -1 : 1;
		x = x1;
		y = y1;
		if (ax > ay)
			d = ay - (ax >> 1);
		else
			d = ax - (ay >> 1);
	}

	public boolean next() {
		if (ax > ay) {
			if (x == x2)
				return false;
			if (d >= 0) {
				y += sy;
				d -= ax;
			}
			x += sx;
			d += ay;
		} else {
			if (y == y2)
				return false;
			if (d >= 0) {
				x += sx;
				d -= ay;
			}
			y += sy;
			d += ax;
		}
		return true;
	}
	

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
}

 

[Developer_X]

Hab' den Algorithmus jetzt nicht nachvollzogen, aber beim "klassischen" Bresenham ist es (wenn ich mich recth erinnere (und das ist jetzt schon >10 Jahre her (ich werd alt))) "normal", dass man nur in einem Oktanten die Zahlen berechnen kann, und die übrigen durch Spiegelungen (oder rotationen um 90°, also vertauschen von x/y) erreicht werden. GANZ grob also: Am Anfang von "drawLine" abfragen, welcher Fall vorliegt, und entsprechend geänderte Methoden(teile) aufrufen.

Es gibt ja nur folgende 4 Fälle:

• 1.Fall A ist kleiner als B (Idealvorstellung)
• 2.Fall B ist kleiner als A (leicht machbar)
• 3.Fall A.x ist kleiner als B.x aber A.y ist größer als B.y (das ist schon nicht mehr so einfach)
• 4.Fall A.y ist kleiner als B.y aber A.x ist größer als B.x(das ist schon nicht mehr so einfach)

Wie man sehen kann, ist das gar nicht so einfach, naja ich probiers einfach mal weiter, und les weiter.

Developer_X

 

[Hansdampf]

Es gibt ja nur folgende 4 Fälle:
Wie man sehen kann, ist das gar nicht so einfach, naja ich probiers einfach mal weiter, und les weiter.
Developer_X

evltl. liest Du Dir ja meinen Code durch, geht schneller.

public void drawLine(Graphics g, Vector2D a, Vector2D b)
{
Bresenham bh=new Bresenham();
bh.set((int)a.x,(int)a.y,(int)b.x,(int)b.y);
while(bh.hasNext())drawPixel(g, bh.getX(),bh.getY());
}

habe es nicht kompiliert, müsste aber gehen.

 

[Developer_X]

danke, wollt aber meinen eigenen Algo versuchen, danke

 

[Hansdampf]

Wollte nicht aufdringlich sein. Kannst die gewonnene Zeit ja nutzen, ein neues Projekt zu starten.

 

[hdi]

Du hast in deinem Algo tatsächlich eine Endlosschleife:

for(;;) // ist das selbe wie: while(true)

So ist der Algorithmus sicherlich nicht gedacht, also prüf nochmal was hier die Bedingung für die Schleife ist.

 

[Developer_X]

Du hast in deinem Algo tatsächlich eine Endlosschleife:

for(;;) // ist das selbe wie: while(true)

So ist der Algorithmus sicherlich nicht gedacht, also prüf nochmal was hier die Bedingung für die Schleife ist.

Nee nee.
In der Schleife wird die Methode break; aufgerufen, das kannste mir glauben.
Nur halt mit einer speziellen If-Clause innerhalb der schleife.

 

[hdi]

Ok habe ich nicht gesehen. Trotzdem, ich finde:

while(y <= b.y){
   ...
}

ist wesentlich verständlicher als:

for(;;){
    if(y>b.y)
       {
          break;
        }
    ...
}

 

[andre111]

@hdi dito

 

[Marco13]

Es gibt ja nur folgende 4 Fälle:

Und das ganze nochmal mal 2, weil die Frage, ob der Betrag einer Zahl größer oder kleiner als ein anderer Betrag ist auch relevant sein KANN.