线光栅化/ 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

回答

相关问题