3. Bresenham Algorithmus

Bresenham Algorithmus

  • P

    algo n00b schrieb:

    der b-algorithmus arbeitet mit ganzen zahlen. für die ansteuerung einer fräschmaschine wohl etwas ungeeignet, oder?

    Dazu muß ich dann doch etwas sagen. Alle digital kontrollierten Systeme bilden letztendlich diskret ab, egal, ob Servo- Driven oder Stepper- Driven.
    Beim Servo bekommt man i.d.R. ein diskretes Winkelgebersignal zur Positionskontrolle zurück, während man beim Stepper davon ausgeht, daß die Anzahl der eingespeisten Steps auch den ausgeführten entspricht.
    An der Präzision ändert die Ganzzahlsache gar nichts, weil eben 360 Winkelgeberimpulse oder 200 Steps pro mm aus der mechanischen Anordnung hervorgehen. Genauer geht es nicht, weil es keine 200.27 Steps gibt.

    0
  • C

    Dieser Thread wurde von Moderator/in rüdiger aus dem Forum ANSI C in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • G

    Ich habe vor längerer Zeit auch mal einen n-Dimensionalen Bresenham-Algorithmus realisiert. Ist in der Klasse da zu finden. ...etwas weiter unten:

    /*
 * LineCaster.java
 *
 * Created on 8. März 2005, 01:25
 */

package jaradap.model.algorithm;

import jaradap.model.algorithm.multiPointProcessor.RaycastProcessor;
import jaradap.model.data.BasicRaster;
import jaradap.model.data.SingleChannelStandardRaster;
import math.linearAlgebra.Vector;

/**
 * This class represents Objects which can analyze lines in a given raster. The analysis
 * projects a line into a single value which is given by a RaycastProcessor, the raster and the line. 
 *
 * @author Gregor
 */
public class LineCaster
{
   private final RaycastProcessor pointProcessor;
   private final SingleChannelStandardRaster raster;
   private final int dimension;

   /** 
    * Creates a new LineCaster with the given parameters.
    *
    * @param pointProcessor This is the RaycastProcessor that will be used to analyze the lines 
    *                       in the method castLine.
    * @param raster This is the raster in that this LineCaster analyzes lines.
    */
   public LineCaster(final RaycastProcessor pointProcessor, final SingleChannelStandardRaster raster)
   {
      this.pointProcessor = pointProcessor;
      this.raster = raster;
      dimension = raster.getDimensions();
   }

   /**
    * This method analyzes the line specified by the parameters startPoint and endPoint. 
    * The pointProcessor of this LineCaster is used to compute the resulting value, while the 
    * raster of this LineCaster is the environment for the analysis.
    *
    * @param startPoint This is the start point of the line.
    * @param endPoint This is the end point of the line.
    * @return The value of the pointProcessor after processing all points of the line inside the raster
    *         will be returned. If the line has no points inside the raster, 0 will be returned.
    */
   public float castLine(final Vector startPoint, final Vector endPoint)
   {
      // Check parameters.
      if (startPoint.getDimension() != dimension)
         throw new IllegalArgumentException("startPoint has wrong dimension.");
      if (endPoint.getDimension() != dimension)
         throw new IllegalArgumentException("endPoint has wrong dimension.");

      // Clip line: 
      // Resulting line is given by rasterStartPoint and rasterEndPoint.
      final int[] rasterStartPoint = new int[dimension];
      final int[] rasterEndPoint = new int[dimension];
      if(!setFirstPointInRaster(rasterStartPoint,startPoint,endPoint)) return 0.0f;
      if(!setFirstPointInRaster(rasterEndPoint,endPoint,startPoint)) return 0.0f;

      // Init helper variables.
      int maxDiffIndex = 0;
      final int[] intDifferences = new int[dimension];
      final int[] relativePosition = new int[dimension];
      final int[] position = new int[dimension];
      final int[] increments = new int[dimension];
      for(int i = 0 ; i < dimension ; ++i)
      {
         intDifferences[i] = rasterEndPoint[i] - rasterStartPoint[i];
         increments[i] = (intDifferences[i] > 0) ? 1 : -1;
         intDifferences[i] = Math.abs(intDifferences[i]);
         if (intDifferences[i] > intDifferences[maxDiffIndex]) maxDiffIndex = i;
         relativePosition[i] = intDifferences[i] >> 1;
         position[i] = rasterStartPoint[i];
      }
      final int maxDifference = intDifferences[maxDiffIndex];
      final int maxIncrement = increments[maxDiffIndex];

      // Process line: 
      // 1. Reset pointProcessor.
      // 2. Process Bresenham-Line-Algorithm
      // 3. Return value of pointProcessor
      pointProcessor.reset();
      for(;position[maxDiffIndex] != rasterEndPoint[maxDiffIndex] ; position[maxDiffIndex] += maxIncrement)
      {
         if (pointProcessor.addPoint(raster,position)) return pointProcessor.getValue();
         for(int i = 0 ; i < dimension ; ++i)
         {
            if (i == maxDiffIndex) continue;
            relativePosition[i] += intDifferences[i];
            if (relativePosition[i] < maxDifference) continue;
            position[i] += increments[i];
            relativePosition[i] -= maxDifference;
         }
      }
      pointProcessor.addPoint(raster,position);
      return pointProcessor.getValue();
   }

   private final boolean setFirstPointInRaster(final int[] target, final Vector firstLinePoint,
                                               final Vector lastLinePoint)
   {
      // Compute the distance of the line's start- and endpoint in each direction.
      final double[] distances = new double[dimension];
      double fraction = 0.0;
      for (int i = 0 ; i < dimension ; ++i)
      {
         distances[i] = (float)(lastLinePoint.getComponent(i) - firstLinePoint.getComponent(i));
      }

      // Compute the fraction that represents the point where the line enters the raster.
      for (int i = 0 ; i < dimension ; ++i)
      {
         double newFraction = 0.0;
         final double component = firstLinePoint.getComponent(i);
         final double difference = distances[i];
         final double maxValue = raster.getSize(i) - 1;
         if (component < 0.0)
         {
            if (difference <= 0.0) return false;
            newFraction = component / difference;
         }
         else if (component > maxValue)
         {
            if (difference >= 0.0) return false;
            newFraction = (component - maxValue) / difference;
         }
         if (newFraction < fraction) fraction = newFraction;
      }

      // Use the fraction to compute the first point of the line that lies within the raster
      // and check if the point really lies within the raster.
      // The point may not lie within the raster if there is no point of the line in the raster.
      for (int i = 0 ; i < dimension ; ++i)
      {
         target[i] = Math.round((float)(firstLinePoint.getComponent(i) - fraction * distances[i]));
         if (target[i] < 0) return false;
         if (target[i] > raster.getSize(i) - 1) return false;
      }
      return true;
   }
}
    0
  • A

    pointercrash() schrieb:

    ...
	// Führachse ermitteln
	if ((*abs_x >= *abs_y) && (*abs_x >= *abs_z))
		*leader = 'x';
	else
		if (*abs_y >= *abs_z)
			*leader = 'y';
		else
			*leader = 'z';
...

    ...

    Schön ist diese Stelle im Code nicht.
    Und bitte, bitte keine Tabulatoren im Quellcode und bitte kein C-Chinesisch... in Anlehnung an die Diskussion hier http://www.c-plusplus.net/forum/viewtopic-var-t-is-229653-and-start-is-40-and-postdays-is-0-and-postorder-is-asc-and-highlight-is-.html

    0
  • ?

    abc.w schrieb:

    Schön ist diese Stelle im Code nicht.

    stören dich die vielen sternchen?
    🙂

    0
  • A

    ~fricky schrieb:

    stören dich die vielen sternchen?
    🙂

    Nein, warum denn nicht so:

    *leader = ((*abs_x >= *abs_y) && (*abs_x >= *abs_z)) ? 'x' : (*abs_y >= *abs_z) ? 'y' : 'z';

    Aber jetzt im Ernst, ich würde natürlich diese ?: Kombination auch nicht akzeptieren.
    Ich habe nichts gegen if else if else Kombination. Es ist nur, dass man 2-3 mal drüberschauen muss, um zu erkennen, was pointercrash() da mit seiner Einrückung gemeint hat. Das ist nicht "soldatensicher" und auch nicht "idiotensicher". Und ich finde, der Konstrukt wäre auf folgende Weise optimal:

    if ((*abs_x >= *abs_y) && (*abs_x >= *abs_z))
{
    *leader = 'x';
}
else if (*abs_y >= *abs_z)
{
    *leader = 'y';
}
else
{
    *leader = 'z';
}
    0
  • ?

    ^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.
    🙂

    0
  • J

    ~fricky schrieb:

    ^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.
    🙂

    Was heißt hier falsch eingerückt. Das was der Compiler da rausliest entspricht wohl eher der dargestellten Einrückung. Ich finde zwar auch, dass die andere Variante besser lesbar ist, aber "falsch" ist die dargestellte Einrückung sicher nicht.

    0
  • ?

    Jester schrieb:

    ~fricky schrieb:

    ^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.

    Was heißt hier falsch eingerückt.

    der original-code suggeriert aber, dass alles hinter dem ersten else ein zusammengehöriger block ist, also sich dass 'innere' else nur auf das if direkt davor bezieht.
    🙂

    0
  • J

    ~fricky schrieb:

    Jester schrieb:

    ~fricky schrieb:

    ^^du hast recht, es ist falsch eingerückt und ich bin voll drauf reingefallen.

    Was heißt hier falsch eingerückt.

    der original-code suggeriert aber, dass alles hinter dem ersten else ein zusammengehöriger block ist, also sich dass 'innere' else nur auf das if direkt davor bezieht.
    🙂

    Überraschung: genau so ist es auch. Es gibt kein separates else-if-Konstrukt in C++ -- braucht man ja auch nicht. Mal Dir doch einfach mal den entsprechenden Parse-Baum auf.

    0
  • ?

    es gibt aber sowas:

    if (...)
{
 ...
}
else if (...)
{
 ...
}
else if (...)
{
 ...
}
else
{
 ...
}

    und verschachtelte konstrukte, wie z.b. das hier:

    if (...)
{
  if (...)
  {
   ...
  }
  else 
  {
   ...
  }
}
else 
{
  if (...)
  {
   ...
  }
  else 
  {
   ...
  }
}

    nach der irreführenden einrückung von pc() sieht's aus wie ein verschachteltes if...else{if...else}, was es aber in wirklichkeit nicht ist. deswegen ist die einrückung von abc.w besser (auch ohne klammern).
    🙂

    0
  • J

    ~fricky schrieb:

    nach der irreführenden einrückung von pc() sieht's aus wie ein verschachteltes if...else{if...else}, was es aber in wirklichkeit nicht ist.

    Das versuche ich doch die ganze Zeit zu erklären, es *ist* in Wirklichkeit (nämlich so wie es die Grammatik definiert und der Parser parst) ein verschachteltes if ... else {if ... else ...}.

    Die Regel für das if sieht in etwa so aus:
    statement -> if (bedingung) statement [else statement]

    Das nachfolgende zweite if gehört syntaktisch zu dem statement im else-Zweig.

    Hier kann man sich's auch anschauen: http://linuxsoftware.co.nz/cppgrammar.html#selection-statement

    0
  • ?

    *schluck*, du hast recht! da programmiert man schon jahrelang in C und hat ein völlig falsches bild von einfachen if/else konstrukten (das dazu noch funktioniert?!).
    🙂

    0
  • P

    Huiui! Hätte nicht gedacht, einen Glaubenskrieg ums Indenting auszulösen 😉 . Aber mir erschien das damals einfach so logisch, weil's wirklich geschachtelt ist. Es gibt ja auch kein "else do" oder "else for", weshalb sollte ich genau dem "if" die Einrückung verweigern 😕 ?
    Ist übrigens auch der Default meines Lieblingseditors.
    😃

    0
  • J

    pointercrash() schrieb:

    Huiui! Hätte nicht gedacht, einen Glaubenskrieg ums Indenting auszulösen 😉 . Aber mir erschien das damals einfach so logisch, weil's wirklich geschachtelt ist. Es gibt ja auch kein "else do" oder "else for", weshalb sollte ich genau dem "if" die Einrückung verweigern 😕 ?
    Ist übrigens auch der Default meines Lieblingseditors.
    😃

    Das ist doch kein Glaubenskrieg. Wir haben uns eigentlich mit einer rein fachlichen Fragestellung auseinandergesetzt. Ich sagte ja, ich würde es auch nicht einrücken. Ich habe nur der Behauptung die Einrückung sei falsch widersprochen.

    Ein Grund warum man auf die Einrückung verzichten könnte, ist dass es sich semantisch eigentlich um drei gleichberechtigte Fälle handelt: es wird genau einer davon angesprochen. Das kommt ohne Einrückung imo deutlicher raus.

    0
  • P

    Jester schrieb:

    Ein Grund warum man auf die Einrückung verzichten könnte, ist dass es sich semantisch eigentlich um drei gleichberechtigte Fälle handelt: es wird genau einer davon angesprochen. Das kommt ohne Einrückung imo deutlicher raus.

    Jetzt bin ich mir nicht sicher, ob wir wirklich das Gleiche meinen. Logisch betrachtet kommt nur einer der drei Fälle dran, aber ganz gleichberechtigt sind sie ja nicht:

    if ((abs_x >= abs_y) && (abs_x >= abs_z))
		leader = 'x';
	else
		if (abs_y >= abs_z)
			leader = 'y';
		else
			leader = 'z';

    Dadurch wird der Erkennung x->y->z der Vorrang gegeben, auch wenn Gleichheiten bestehen. Erst wenn x nicht größergleich als y bzw. z, wird weitergeprüft. Die Prüfung y gegen z setzt schon voraus, daß x nicht der Größte ist und bevorzugt bei Gleichheit y.
    Hatte den Grund, daß der abspulende Automat, der zunächst schauen mußte, ob x oder y oder z fahren in der gleichen Reihenfolge geparst hat, dadurch meist um eine knappe µs Vergleichszeit sparen konnte. Hat sich aber bei mir auch schon überholt, ich mache das mittlerweile Funktionspointergefädelt.

    Das als "else if"- Kette hinzuschreiben macht meines Erachtens dann Sinn, wenn man rechts knapp mit dem Platz dran ist und zehn Abfragen vorhat - in Abhängigkeit vom Nichtzutreffen der jeweils vorherigen Abfragen.
    Für echt gleichberechtigte Abfragen gibt es ja "switch - case" (vom "break"- Weglassen mal abgesehen).

    if - else- Konstrukte sind durch ihre Schachtelung per se hierarchisch, was hier ein durchaus erwünschter Effekt war. 😉

    0
  • A

    pointercrash() schrieb:

    ...Für echt gleichberechtigte Abfragen gibt es ja "switch - case" (vom "break"- Weglassen mal abgesehen)...

    Was meinst Du mit "break" weglassen? Etwa so:

    switch (a)
{
    if (c == d) case e: ...;
    else case d: ...;
    if (0) default: ...;
}

    Das geht auch und man kann es beliebig kompliziert machen 🕶

    PS: Ist nur ein dummer Vorschlag von mir. Auf keinen Fall nachmachen... 🙂

    0
  • J

    pointercrash() schrieb:

    Für echt gleichberechtigte Abfragen gibt es ja "switch - case" (vom "break"- Weglassen mal abgesehen).

    Das funktioniert aber nicht immer. Schließlich lässt sich nicht jede Bedingung ohne Umwege auf einen einzelnen Vergleich mit == runterbrechen.

    Meiner Meinung nach sind Deine drei Fälle schon gleichberechtigt. Dass Du in Randfällen einen bestimmten vorziehst tut der Sache imo keinen Abbruch.

    0
  • P

    abc.w schrieb:

    Auf keinen Fall nachmachen... 🙂

    Mein' ich auch. Aber z.B. bei solchen Sachen:

    switch (cc)
	{
	case 'i':		// i = inch
		var *= 25.4;
	case 'm':		// m = mm
		u = var * var;
	break;
	case 'T':
		{
			foo();
		}
	}

    Da machen 'i' und 'm' das Identische, nur, daß 'i' vorher "var" von inch auf metrisch mm umrechnet.

    Jester schrieb:

    Das funktioniert aber nicht immer. Schließlich lässt sich nicht jede Bedingung ohne Umwege auf einen einzelnen Vergleich mit == runterbrechen.

    Meiner Meinung nach sind Deine drei Fälle schon gleichberechtigt. Dass Du in Randfällen einen bestimmten vorziehst tut der Sache imo keinen Abbruch.

    Wie man's nimmt, solange dabei nicht vergessen wird, daß doch Abhängigkeiten bestehen. Bei ein, zwei Teilnehmern bleibt das trivial, aber bastel' mal 6 Entscheidungsteilnehmer in eine 4- Stufige if- then - else -if ein.
    Ich denke, wir gehen darin überein, daß es lesbarere Formulierungen geben muß, was? 😉

    EDIT: hustbaer-Entnörgel-Edit.

    0

  • [nörgel-mode]

    case :'i'

    ich glaube nicht dass sich das compilieren lässt
    [/nörgel-mode]

    0
Anmelden zum Antworten