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

Question

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

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

Answer 1

Вот статья Amanatides и Woo "Быстрый алгоритм обхода вокселей для трассировки лучей" для 2D и 3D случаев. Практическая реализация.

Answer 2

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

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

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

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); */
    }
    else
    {
      // 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           
    }
}