線分を離散化する方法

Question

1つの線分が通過するグリッドセルを見つけるにはどうすればよいですか？たとえば、線分は(8.3555 9.1654) -> (1.4123 5.6312)（任意の精度）で指定できます。

私は上に第二の画像に見られるように、グリッドベースの表現にこれを変換したい：

私は現在、CGALに探しています。それは、パッケージのSnap Rounding私は何を探しているのですが、セグメントの開始点と終了点のみです。

Answer 1

私はアルゴリズムを自分で実装することになりました。基本的には、コンピュータグラフィックスアルゴリズムのどれも実際にすべてのグリッドセルを含むという私の要求を満たさないため、ラインが接触します。私はPixelとしてPointとして浮動prcisionポイントと離散グリッドセルを表すためにCGAL 2つの異なるカーネルを使用しています

注：これは、関数である

#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 oneのようなラインラスタライズアルゴリズムを示しています。

第2の画像は、ボクセル化を示しています。ラインですべてのグリッドセルをタッチします。 Amanatides and Wooのアルゴリズムを検討してください。