Comment discrétiser un segment de ligne

Question

Comment puis-je savoir à quelle grille un segment de ligne se déplace? Par exemple, le segment de ligne peut être donné comme (8.3555 9.1654) -> (1.4123 5.6312) (avec une précision arbitraire).

Je veux le transformer en une représentation basée sur les grilles comme vu dans la deuxième image sur le dessus:

Je suis actuellement en CGAL. Il a le paquet Snap Rounding qui fait ce que je cherche mais seulement pour les points de début et de fin des segments.

Answer 1

Je fini par mettre en œuvre l'algorithme moi-même. Fondamentalement parce qu'aucun des algorithmes d'infographie n'atteint mon exigence d'inclure réellement toutes les cellules de la grille, la ligne touche.

Notez que j'utilise CGAL et deux noyaux différents pour représenter des points flottants prcision comme Point et cellules discrètes comme 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; 

Ceci est la fonction:

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

La première image montre un algorithme de tramage de lignes tel que Bresenham ou DDA.

La deuxième image montre la voxelization - obtenir toutes les cellules de la grille touchées par la ligne. Envisager l'algorithme de Amanatides and Woo.