Rasterizzazione linea/Bresenham a 4 canali

Question

Per i test di collisione è necessario rasterizzare una linea. L'algoritmo Bresenham funziona quasi, se lo desideri, ma ha il difetto che è produce una linea come:

E ho bisogno:

mio attuale implementazione (basata su 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; 
} 

Esiste un altro algoritmo di rasterizzazione della riga che potrei usare, o qualcuno sa come modificare il bresenham?

Answer 1

Grazie koan, a volte basta mancano le parole chiave da cercare, Algorithm for drawing a 4-connected line sembra risolverlo:

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

forse sarà utile, c'è la mia versione per punti finali non interi. È un metodo della classe GridMap che utilizzo per l'indicizzazione spaziale di forme geometriche al fine di accelerare il rilevamento delle collisioni nella mappa 2D.

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); 
    } 
};