Элегантный/чистый (специальный случай) Прямолинейный алгоритм обхода сетки?

Ответ 1

То, что вы хотите, - это частный случай суперобложки, в которой все пиксели пересекаются геометрическим объектом. Объект может быть линией или треугольником, и есть обобщения для более высоких измерений.

В любом случае, вот одна реализация для линейных сегментов. На этой странице также сравнивается суперобложка с результатом алгоритма Брезенхема - они разные. альтернативный текст http://eugen.dedu.free.fr/projects/bresenham/diff.png

Я не знаю, считаете ли вы алгоритм там элегантным/чистым, но он кажется достаточно простым, чтобы адаптировать код и перейти к другим частям вашего проекта.

Кстати, ваш вопрос подразумевает, что алгоритм Брезенхэма неэффективен для больших сеток. Это не правда - он генерирует только пиксели на линии. Вам не нужно делать проверку истинности/ложности для каждого пикселя в сетке.

Обновление 1: я заметил, что на картинке есть два "лишних" синих квадрата, которые, по моему мнению, не проходят через линию. Один из них примыкает к "h" в "Этот алгоритм". Я не знаю, отражает ли это ошибку в алгоритме или диаграмме (но см. Комментарий @kikito ниже).

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

Обновление 2: еще одна реализация.

Ответ 2

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

Существует также еще один документ здесь, имея дело с чем - то подобным.

Обе эти статьи связаны в четвертой части превосходных учебных пособий Jakko Bikker по трассировке лучей (которые также включают его исходный код, так что вы можете просмотреть/изучить его реализации).

Ответ 3

Там очень простой алгоритм для вашей проблемы, который работает в линейном времени:

• Учитывая две точки A и B, определите точки пересечения линии (A, B) с каждой вертикальной линией вашей сетки, лежащей внутри этого интервала.
• Вставьте две специальные точки пересечения внутри ячеек, содержащих A и B, в начале/конце списка из точки 1.
• Интерпретируйте каждые две секвенциальные точки пересечения как минимальные и максимальные векторы прямоугольника, выровненного по оси, и отметьте все ячейки сетки, которые лежат внутри этого прямоугольника (это очень просто (пересечение двух выровненных по прямой оси прямоугольников), особенно учитывая, что прямоугольник имеет ширину 1 и, следовательно, занимает только 1 столбец вашей сетки)

+------+------+------+------+
|      |      |      |      |
|      |      | B    *      |
|      |      |/     |      |
+------+------*------+------+
|      |     /|      |      |
|      |    / |      |      |
|      |   /  |      |      |
+------+--/---+------+------+
|      | /    |      |      |
|      |/     |      |      |
|      *      |      |      |
+-----/+------+------+------+
|    / |      |      |      |
*   A  |      |      |      |
|      |      |      |      |
+------+------+------+------+ 

"A" и "B" - это точки, заканчивающиеся линией, представленной "/". "*" обозначает точки пересечения линии с сеткой. Две специальные точки пересечения необходимы для обозначения ячеек, которые содержат A & B, и для обработки особых случаев, таких как A.x == B.x

Требуется оптимизированная реализация и Theta; (| B.x - A.x | + | B.y - A.y |) время для строки (A, B). Кроме того, этот алгоритм можно записать для определения точек пересечения с горизонтальными линиями сетки, если это проще для исполнителя.

Обновление: случаи границы

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

Однако ошибки с плавающей запятой произойдет рано или поздно и дадут неверные результаты. По моему мнению, даже использование double не будет достаточным, и нужно переключиться на тип номера Decimal. Оптимизированная реализация будет выполнять дополнения & Theta; (| max.x - min.x |) в этом типе данных, каждый из которых берет & Theta; (log max.y). Это означает, что в худшем случае (линия ((0, 0), (N, N)) с огромным N ( > 10 ⁶) алгоритм деградирует до наихудшего случая O (N log N) Даже переключение между обнаружением пересечения вертикальной/горизонтальной сетки в зависимости от наклона линии (A, B) не помогает в этом худшем случае, но в среднем случае это действительно верно - я бы рассмотрел только такую ​​реализацию если профилировщик выполняет операции Decimal как шею бутылки.

Наконец, я могу представить, что некоторые умные люди могут придумать решение O (N), которое правильно относится к этим случаям с границами. Все ваши предложения приветствуются!

Коррекция

brainjam указал, что десятичный тип данных не удовлетворяет, даже если он может представлять произвольные числа с плавающей запятой, поскольку, например, ¹/ ₃ t правильно отображаться. Поэтому следует использовать тип данных дробей, который должен иметь возможность корректно обрабатывать пограничные случаи. спасибо brainjam!:)

Ответ 4

Вот простая реализация на Python с использованием numpy. Однако здесь используются только двухмерные векторы и компонентные операции с компонентами, что довольно часто. Результат выглядит довольно элегантно для меня (~ 20 loc без комментариев).

Это не является общим, так как предполагает, что плитки центрированы в целочисленных координатах, а разделительные линии появляются в каждом целом числе плюс одна половина (0,5, 1,5, 2,5 и т.д.). Это позволяет использовать округление для получения целочисленных координат тайла из мировой координаты (что на самом деле не требуется в вашем особом случае) и дает магическое число 0.5 чтобы определить, когда мы достигли последней плитки.

Наконец, обратите внимание, что этот алгоритм не имеет дело с точкой, точно пересекающей сетку на пересечении.

import numpy as np

def raytrace(v0, v1):
    # The equation of the ray is v = v0 + t*d
    d = v1 - v0
    inc = np.sign(d)  # Gives the quadrant in which the ray progress

    # Rounding coordinates give us the current tile
    tile = np.array(np.round(v0), dtype=int)
    tiles = [tile]
    v = v0
    endtile = np.array(np.round(v1), dtype=int)

    # Continue as long as we are not in the last tile
    while np.max(np.abs(endtile - v)) > 0.5:
        # L = (Lx, Ly) where Lx is the x coordinate of the next vertical
        # line and Ly the y coordinate of the next horizontal line
        L = tile + 0.5*inc

        # Solve the equation v + d*t == L for t, simultaneously for the next
        # horizontal line and vertical line
        t = (L - v)/d

        if t[0] < t[1]:  # The vertical line is intersected first
            tile[0] += inc[0]
            v += t[0]*d
        else:  # The horizontal line is intersected first
            tile[1] += inc[1]
            v += t[1]*d

        tiles.append(tile)

    return tiles