Diskretisieren eines Liniensegments

Question

Wie kann ich herausfinden, welche Rasterzellen ein Liniensegment durchläuft? Zum Beispiel kann das Liniensegment als (8.3555 9.1654) -> (1.4123 5.6312) (mit beliebiger Genauigkeit) angegeben werden.

Ich mag diese in eine gitterbasierte Darstellung zu transformieren, wie in dem zweiten Bild auf der Oberseite gesehen:

ich zur Zeit in CGAL suchen bin. Es hat das Paket Snap Rounding welches Art von was ich suche aber nur für die Start- und Endpunkte der Segmente.

Answer 1

ich den Algorithmus selbst Umsetzung endete. Grundsätzlich, weil keiner der Computergrafikalgorithmen meine Anforderung erfüllt, tatsächlich alle Rasterzellen einzuschließen, berührt die Linie.

beachte, dass ich CGAL und zwei verschiedene Kernel bin mit schwebenden prcision Punkte als Point und diskrete Gitterzellen als Pixel darstellen:

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

Dies ist die Funktion:

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

Das erste Bild zeigt einen Linienrasterisierungsalgorithmus wie Bresenham oder DDA.

Das zweite Bild zeigt Voxelisation - alle Gitterzellen werden durch die Linie berührt. Berücksichtigen Sie den Algorithmus von Amanatides and Woo.