Алгоритм растеризации повернутого прямоугольника

Это старый вопрос, но я решил эту проблему (C ++)

https://github.com/feelinfine/tracer

Может кому будет полезно

(извините за мой плохой английский)

Однострочная трассировка

template <typename PointType>
std::set<V2i> trace_line(const PointType& _start_point, const PointType& _end_point, size_t _cell_size)
{   
    auto point_to_grid_fnc = [_cell_size](const auto& _point)
    {
        return V2i(std::floor((double)_point.x / _cell_size), std::floor((double)_point.y / _cell_size));
    };

    V2i start_cell = point_to_grid_fnc(_start_point);
    V2i last_cell = point_to_grid_fnc(_end_point);

    PointType direction = _end_point - _start_point;

    //Moving direction (cells)
    int step_x = (direction.x >= 0) ? 1 : -1;
    int step_y = (direction.y >= 0) ? 1 : -1;

    //Normalize vector
    double hypot = std::hypot(direction.x, direction.y);
    V2d norm_direction(direction.x / hypot, direction.y / hypot);

    //Distance to the nearest square side
    double near_x = (step_x >= 0) ? (start_cell.x + 1)*_cell_size - _start_point.x : _start_point.x - (start_cell.x*_cell_size);    
    double near_y = (step_y >= 0) ? (start_cell.y + 1)*_cell_size - _start_point.y : _start_point.y - (start_cell.y*_cell_size);

    //How far along the ray we must move to cross the first vertical (ray_step_to_vside) / or horizontal (ray_step_to_hside) grid line
    double ray_step_to_vside = (norm_direction.x != 0) ? near_x / norm_direction.x : std::numeric_limits<double>::max();
    double ray_step_to_hside = (norm_direction.y != 0) ? near_y / norm_direction.y : std::numeric_limits<double>::max();

    //How far along the ray we must move for horizontal (dx)/ or vertical (dy) component of such movement to equal the cell size
    double dx = (norm_direction.x != 0) ? _cell_size / norm_direction.x : std::numeric_limits<double>::max();
    double dy = (norm_direction.y != 0) ? _cell_size / norm_direction.y : std::numeric_limits<double>::max();

    //Tracing loop
    std::set<V2i> cells;
    cells.insert(start_cell);

    V2i current_cell = start_cell;

    size_t grid_bound_x = std::abs(last_cell.x - start_cell.x);
    size_t grid_bound_y = std::abs(last_cell.y - start_cell.y);

    size_t counter = 0;

    while (counter != (grid_bound_x + grid_bound_y))
    {
        if (std::abs(ray_step_to_vside) < std::abs(ray_step_to_hside))
        {
            ray_step_to_vside = ray_step_to_vside + dx; //to the next vertical grid line
            current_cell.x = current_cell.x + step_x;
        }
        else
        {
            ray_step_to_hside = ray_step_to_hside + dy;//to the next horizontal grid line
            current_cell.y = current_cell.y + step_y;
        }

        ++counter;

        cells.insert(current_cell);
    };

    return cells;
}

Получить все ячейки

template <typename Container>
std::set<V2i> pick_cells(Container&& _points, size_t _cell_size)
{
    if (_points.size() < 2 || _cell_size <= 0)
        return std::set<V2i>();

    Container points = std::forward<Container>(_points);

    auto add_to_set = [](auto& _set, const auto& _to_append)
    {
        _set.insert(std::cbegin(_to_append), std::cend(_to_append));
    };

    //Outline
    std::set<V2i> cells;

    /*
    for (auto it = std::begin(_points); it != std::prev(std::end(_points)); ++it)
        add_to_set(cells, trace_line(*it, *std::next(it), _cell_size));
    add_to_set(cells, trace_line(_points.back(), _points.front(), _cell_size));
    */

    //Maybe this code works faster
    std::vector<std::future<std::set<V2i> > > results;

    using PointType = decltype(points.cbegin())::value_type;

    for (auto it = points.cbegin(); it != std::prev(points.cend()); ++it)           
        results.push_back(std::async(trace_line<PointType>, *it, *std::next(it), _cell_size));

    results.push_back(std::async(trace_line<PointType>, points.back(), points.front(), _cell_size));    

    for (auto& it : results)
        add_to_set(cells, it.get());

    //Inner
    std::set<V2i> to_add;

    int last_x = cells.begin()->x;
    int counter = cells.begin()->y;

    for (auto& it : cells)
    {
        if (last_x != it.x)
        {
            counter = it.y;
            last_x = it.x;
        }

        if (it.y > counter) 
        {
            for (int i = counter; i < it.y; ++i)
                to_add.insert(V2i(it.x, i));
        }

        ++counter;
    }

    add_to_set(cells, to_add);

    return cells;
}

Типы

template <typename _T>
struct V2
{
    _T x, y;

    V2(_T _x = 0, _T _y = 0) : x(_x), y(_y)
    {
    };

    V2 operator-(const V2& _rhs) const
    {
        return V2(x - _rhs.x, y - _rhs.y);
    }

    bool operator==(const V2& _rhs) const
    {
        return (x == _rhs.x) && (y == _rhs.y);
    }

    //for std::set sorting
    bool operator<(const V2& _rhs) const
    {
        return (x == _rhs.x) ? (y < _rhs.y) : (x < _rhs.x);
    }
};

using V2d = V2<double>;
using V2i = V2<int>;

Использование

std::vector<V2d> points = { {200, 200}, {400, 400}, {500,100} };
size_t cell_size = 30;
auto cells = pick_cells(points, cell_size);
for (auto& it : cells)
    ...                 //do something with cells

Вы можете использовать растровый подход. Прямоугольник представляет собой замкнутый выпуклый многоугольник, поэтому достаточно сохранить крайний левый и крайний правый пиксели для каждой горизонтальной строки развертки. (И верхняя, и нижняя строки развертки тоже.)

Алгоритм Брезенхема пытается нарисовать тонкую, визуально приятную линию без соседних ячеек в меньшем измерении. Нам нужен алгоритм, который посещает каждую ячейку, через которую проходят края многоугольника. Основная идея состоит в том, чтобы найти начальную ячейку (x, y) для каждого края, а затем настроить x всякий раз, когда край пересекает вертикальную границу, и корректировать y, когда он пересекает горизонтальную границу.

Мы можем представить пересечения с помощью нормализованной координаты s, которая движется вдоль края и равна 0,0 в первом узле n1 и 1,0 во втором узле n2.

    var x = Math.floor(n1.x / cellsize);
    var y = Math.floor(n1.y / cellsize);
    var s = 0;

Вертикальные вставки могут быть представлены как эквидистантные шаги с dsx от начального sx.

    var dx = n2.x - n1.x;

    var sx = 10;            // default value > 1.0

    // first intersection
    if (dx < 0) sx = (cellsize * x - n1.x) / dx;
    if (dx > 0) sx = (cellsize * (x + 1) - n1.x) / dx;

    var dsx = (dx != 0) ? grid / Math.abs(dx) : 0;

То же самое и с горизонтальными перекрестками. Значение по умолчанию больше 1.0 учитывает случаи горизонтальных и вертикальных линий. Добавьте первую точку к данным развертки:

    add(scan, x, y);

Затем мы можем посетить следующую соседнюю ячейку, посмотрев на следующее пересечение с наименьшим s.

    while (sx <= 1 || sy <= 1) {
        if (sx < sy) {
            sx += dsx;
            if (dx > 0) x++; else x--;
        } else {
            sy += dsy;
            if (dy > 0) y++; else y--;
        }
        add(scan, x, y);
    }

Сделайте это для всех четырех краев и с одними и теми же данными развертки. Затем заполните все ячейки:

    for (var y in scan) {
        var x = scan[y].min;
        var xend = scan[y].max + 1;
        while (x < xend) {
            // do something with cell (x, y)
            x++;
        }
    }

(Я только просмотрел ссылки, предоставленные MBo. Кажется, что подход, представленный в этой статье, по сути такой же, как и мой. Если так, извините, пожалуйста, за повторяющийся ответ, но после работы над этим я подумал, что могу также опубликовать его.)

Это неоптимально, но может дать общее представление.

Прежде всего, рассмотрим особый случай, когда прямоугольник выравнивается по горизонтали или вертикали отдельно. Это довольно легко проверить, а остальное упростить.

Вы можете представить прямоугольник как набор из 4 неравенств a1 x + b1 y >= c1 a1 x + b1 y <= c2 a3 x + b3 y >= c3 a3 x + b3 y <= c4, поскольку края прямоугольников параллельны, некоторые из констант совпадают. У вас также есть (до нескольких) a3=b1 и b3=-a1. Вы можете умножить каждое неравенство на общий множитель, чтобы работать с целыми числами.

Теперь рассмотрим каждую строку развертки с фиксированным значением y. Для каждого значения y найдите четыре точки, в которых линии пересекают линию сканирования. То есть найдите решение в каждой строке выше. Немного логики найдет минимальное и максимальное значения x. Постройте все пиксели между этими значениями.

Вы усложняете задачу, что вам нужны все частично закрытые квадраты. Вы можете решить эту проблему, рассматривая две соседние строки развертки. Вы хотите построить точки между минимумом x для обеих линий и максимумом для обеих линий. Если, скажем, a1 x+b1 y>=c - это неравенство для левой нижней строки на рисунке. Вам нужно найти наибольший x, чтобы a1 x + b1 y < c это было floor((c-b1 y)/a1) вызовите это minx(y) также найдите minx(y+1), и левая точка будет минимальным из этих двух значений.

Существует много простых способов оптимизации: вы можете найти значения y для верхнего и нижнего углов, уменьшив диапазон значений y для тестирования. Вам нужно проверить только две стороны. Для каждой конечной точки каждой строки есть одно умножение, одно вычитание и одно деление. Дивизия - самая медленная часть, я думаю, примерно в 4 раза медленнее, чем другие операции. Возможно, вы сможете удалить это с помощью алгоритмов Брезенхэма или DDA, упомянутых другими.

Существует метод Аманатидеса и Ву для перечисления всех пересекающихся ячеек. Алгоритм быстрого обхода вокселей для Трассировка лучей.
Вот практическая реализация.
В качестве побочного эффекта для вас - вы получите точки пересечения с линиями сетки - это может быть полезно, если вам нужны области частично закрытых ячеек (для сглаживания и т. Д.).