如何離散線段

Question

如何找出一條線段經過的網格單元？例如，線段可以作爲(8.3555 9.1654) -> (1.4123 5.6312)（以任意精度）給出。

我要像頂部的第二圖像中看到，改造成一個基於網格的表示這樣的：

我目前正在研究CGAL。它有包裝Snap Rounding哪種做我正在尋找的，但僅用於細分市場的起點和終點。

Answer 1

我最終實現了自己的算法。基本上，因爲沒有任何計算機圖形算法符合我實際包括所有網格單元的要求，所以這條線觸及。

注意，我使用CGAL和兩個不同的內核來表示浮動prcision點作爲Point和離散網格細胞作爲Pixel：

#include <CGAL/Simple_cartesian.h> 
#include <CGAL/Point_2.h> 

typedef CGAL::Simple_cartesian<double> KernelDouble; 
typedef KernelDouble::Point_2 Point; 
typedef KernelDouble::Segment_2 Segment; 

typedef CGAL::Simple_cartesian<uint16_t> KernelInt; 
typedef KernelInt::Point_2 Pixel; 

這是函數：

void get_pixels_for_segment(std::list<Pixel>* res, Segment seg) { 
    assert(res->size() == 0); 
    Point start = seg.source(); 
    Point goal = seg.target(); 
    uint8_t swapped = 0; 
    if(start.x() > goal.x()) { // swap 
     start = seg.target(); 
     goal = seg.source(); 
     swapped = 1; 
    } 
    Pixel startp, goalp; 
    startp = point_to_pixel(&start); 
    goalp = point_to_pixel(&goal); 
    int8_t sx = sgn<int>(goalp.x() - startp.x()); 
    assert(sx >= 0); 
    int8_t sy = sgn<int>(goalp.y() - startp.y()); 
    if(startp == goalp) { 
     res->push_back(startp); 
     return; 
    } 
    double d = (goal.y() - start.y())/(goal.x() - start.x()); 
    double ysec = start.y() - d * start.x(); 
    std::list<int> xs; 
    range(&xs, startp.x(), goalp.x()); 
    std::list<int>::iterator xsit = xs.begin(); 
    for(; xsit != xs.end(); ++xsit) { 
     int xl = *xsit; 
     int xr = *xsit + 1; 
     double yl = d * xl + ysec; 
     double yr = d * xr + ysec; 
     if(startp.y() == goalp.y()) { 
      yl = startp.y(); 
      yr = goalp.y(); 
     } 
     if(
      ((startp.y() - floor(yl)) * sy) > 0 
     ) yl = (double) startp.y(); 
     if(
      ((goalp.y() - floor(yr)) * sy) < 0 
     ) yr = (double) goalp.y(); 
     std::list<int> ys; 
     range(&ys, floor(yl), floor(yr)); 
     std::list<int>::iterator ysit = ys.begin(); 
     for(; ysit != ys.end(); ++ysit) { 
      assert(*xsit >= 0); 
      assert(*ysit >= 0); 
      res->push_back(Pixel(*xsit, *ysit)); 
     } 
    } 
    if(swapped) res->reverse(); 
    return; 
} 

Answer 2

第一張圖像顯示了像Bresenham或DDA一樣的線柵格化算法。

第二個圖像顯示體素化 - 獲取所有網格單元格接觸的行。考慮Amanatides and Woo的算法。