Line Rasterization/4-Connected Bresenham

Question

Für Kollisionstests muss ich eine Linie rasteren. Der Bresenham-Algorithmus arbeitet fast wie gewünscht, hat aber die Fehler, die eine Zeile wie ist produziert:

Und ich brauche:

Meine aktuelle Implementierung (basierend auf http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Simplification):

public boolean isInsideLine(int x1, int y1, int x2, int y2) { 
    final int dx = abs(x2 - x1), dy = abs(y2 - y1); 
    final int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1; 
    int err = dx - dy; 

    while (true) { 
     if (isInside(x1, y1)) //Lookup in pixel array 
      return true; 
     if (x1 == x2 && y1 == y2) 
      break; 
     final int e2 = err << 1; 
     if (e2 > -dy) { 
      err -= dy; 
      x1 += sx; 
     } 
     if (e2 < dx) { 
      err += dx; 
      y1 += sy; 
     } 
    } 
    return false; 
} 

Gibt es einen anderen Linienrasterisierungsalgorithmus, den ich verwenden könnte, oder weiß jemand, wie man den Bresenham ändert?

Answer 1

Dank Koan, manchmal fehlt einfach die Schlüsselwörter für die Suche, Algorithm for drawing a 4-connected line scheint es zu lösen:

public boolean isInsideLine(int x1, int y1, int x2, int y2) { 
    final int dx = abs(x2 - x1), dy = abs(y2 - y1); 
    final int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1; 
    int err = dx - dy; 

    while (true) { 
     if (isInside(x1, y1)) //Lookup in pixel array 
      return true; 
     if (x1 == x2 && y1 == y2) 
      break; 
     final int e2 = err << 1; 
     if (e2 > -dy) { 
      err -= dy; 
      x1 += sx; 
     } else if (e2 < dx) { // else if instead of if 
      err += dx; 
      y1 += sy; 
     } 
    } 
    return false; 
} 

Answer 2

Vielleicht wird es sehr nützlich sein, da meine Version für nicht ganzzahligen Endpunkte ist. Es ist eine Methode der GridMap Klasse, die ich für die räumliche Indizierung von geometrischen Formen verwende, um die Kollisionserkennung in 2D-Karten zu beschleunigen.

int GridMap::insertLine(int lineId, double ax, double ay, double bx, double by){ 
    // get index of endpoints in GridMap 
    int ix = getIx(ax); 
    int iy = getIy(ay); 
    int ixb = getIx(bx); 
    int iyb = getIy(by); 
    // insert endpoints to GridMap 
    insert(lineId, ix, iy ); 
    insert(lineId, ixb, iyb); 
    // raster central part of the line 
    double dx = fabs(bx - ax); 
    double dy = fabs(by - ay); 
    int dix = (ax < bx) ? 1 : -1; 
    int diy = (ay < by) ? 1 : -1; 
    double x=0, y=0; 
    while ((ix != ixb) && (iy != iyb )) { 
     if (x < y) { 
      x += dy; 
      ix += dix; 
     } else { 
      y += dx; 
      iy += diy; 
     } 
     insert(lineId, ix, iy); 
    } 
};