Найти все плитки, пересеченные сегментом линии

Question

Мне нужно найти все плитки, которые пересекаются по отрезку линии, но алгоритм линии Bresenham не соответствует моим требованиям. Мне нужно найти все ячейки. Мне не нужно знать точки пересечения, только факт пересечения. Спасибо за помощь.

Я думал найти вектор направления линии и шаг за шагом найти ячейки путем деления на размер плитки. Но я не знаю, как выбрать правильный размер шага. 1 px шаг плохой, я думаю.

Answer 1

Here is article из Amanatides and Woo «Алгоритм быстрого преобразования вокселей для трассировки лучей» для 2D и 3D-корпусов. Practical implementation.

Answer 2

Вы можете использовать один из многих уравнений линии найдена по адресу: http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml или

Возможно у вас есть линия в вашей системе координат, проходящей через две точки вы выводите y=mx+n уравнения и просто совпадаете с вашими плитками и увидеть если они пересекаются при перемещении x в единице вашей системы координат в любом направлении, которое вы предпочитаете от наименьшего x ваших плиток до самого большого. Если вашей системой координат является экран, должно быть достаточно одного пикселя.

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

Answer 3

Легко модифицировать алгоритм Брешенема таким образом, чтобы он отслеживал то, что вам нужно. Вот соответствующий фрагмент алгоритма:

plot(x,y); 
error = error + deltaerr; 
if (error >= 0.5) 
{ 
    y = y + ystep; 
    error = error - 1.0; 
} 

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

plot(x,y); 
olderror = error. 
error = error + deltaerr; 
if (error >= 0.5) 
{ 
    y = y + ystep; 
    error = error - 1.0; 
    extra = error+olderror; 

    if (extra > 0) 
    { 
     plot (x,y); /* not plot (x-1,y); */ 
    } 
    else if (extra < 0) 
    { 
     plot (x+1,y-1); /* not plot (x+1,y); */ 
    } 
    esle 
    { 
     // the line goes right through the cell corner 
     // either do nothing, or do both plot (x-1,y) and plot (x+1,y) 
     // depending on your definition of intersection   
    } 
}