線光柵化/ 4連接Bresenham

對於碰撞測試，我需要柵格化一條線。布氏算法的工作原理幾乎一樣需要，但就是缺陷產生一行：線光柵化/ 4連接Bresenham

我需要：

我目前的執行（基於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; 
}

是否有其他的行光柵化算法，我可以使用，或者有人知道如何修改bresenham？

來源

2012-11-24 DiddiZ

在我看來，Bresenham的原始輸出是8連接，但你需要4連接。您可以對原始輸出進行後期處理以檢測對角線鏈接，然後確定線條最接近哪個像素。 – koan

請參閱http://stackoverflow.com/questions/5186939/algorithm-for-drawing-a-4-connected-line看起來像是同一個問題。 – koan

出於興趣：爲什麼您需要柵格化一條線以進行碰撞檢測？你不能只計算交叉點嗎？ – Axel

感謝公案，有時你只是缺乏要搜索的關鍵字，Algorithm for drawing a 4-connected line似乎解決它：

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

來源

2012-11-24 17:08:26 DiddiZ

也許這將是有益的，還有就是我的版本非整數終點。這是一種用於幾何形狀空間索引的類GridMap的方法，以加速二維地圖中的碰撞檢測。

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

來源

2014-12-31 10:17:34

線光柵化/ 4連接Bresenham

回答

相關問題