如何离散线段

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的算法。