How to discretize a line segment

Question

How can I find out which grid cells one line segment travels through? For example, the line segment may be given as (8.3555 9.1654) -> (1.4123 5.6312) (with arbitrary precision).

I want to transform this into a grid-based representation like seen in the second image on the top:

I am currently looking into CGAL. It has the package Snap Rounding which kind of does what I am looking for but only for the start and end points of the segments.

There are formula's for detecting 2 lines (vectors) crossing, In your case the implied line and the grid lines, is it that thing you are asking about? — Surt, Oct 11 '17 at 20:24
Possible duplicate of [Precise subpixel line drawing algorithm (rasterization algorithm)](https://stackoverflow.com/questions/24679963/precise-subpixel-line-drawing-algorithm-rasterization-algorithm) — Spektre, Oct 12 '17 at 03:41

score 0 · Answer 1 · answered Oct 12 '17 at 01:39

0

The first image shows line rasterizing algorithm like Bresenham or DDA one.

The second image shows voxelization - get all the grid cells touched by line. Consider algorithm of Amanatides and Woo.

answered Oct 12 '17 at 01:39

MBo

77,366
5
53
86

Thanks for that but especially the cells displayed in blue i need to be included as well. And my start and end points need to be float precision. – Christian Oct 18 '17 at 08:15
Start and end points coordinates are floats. Blue cells are registered by algorithm, of course. I just gave them another color (some applications should ignore such points) – MBo Oct 18 '17 at 08:55
Okay, thanks for pointing out. I am going to look into it again. – Christian Oct 18 '17 at 08:57

score 0 · Accepted Answer · answered Oct 18 '17 at 08:10

I ended up implementing the algorithm myself. Basically because none of the computer graphics algorithms meet my requirement of actually including all grid cells, the line touches.

Note that I am using CGAL and two different kernel to represent floating-prcision Points as Point and discrete grid cells as 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;

This is the function:

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

How to discretize a line segment

2 Answers2