如何离散化线段

Question

如何找出一条线段穿过哪些网格单元？例如，线段可以指定为 (8.3555 9.1654) -> (1.4123 5.6312)（具有任意精度）。

我想将其转换为基于网格的表示形式，如顶部第二张图片所示：

我目前正在调查 CGAL。它有包 Snap Rounding 哪种方式可以满足我的需求，但仅限于段的起点和终点。

Answer 1

第一张图片显示了类似 Bresenham 或 DDA 的线光栅化算法。

第二张图片显示体素化 - 获取线接触的所有网格单元。考虑Amanatides and Woo的算法。

Answer 2

我最终自己实现了算法。基本上是因为 none 的计算机图形算法满足了我实际包括所有网格单元的要求，所以该线触及。

请注意，我使用 CGAL 和两个不同的内核将浮动精度点表示为 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;
}

如何离散化线段

How to discretize a line segment

c++

grid

geometry

cgal

computational-geometry