Найти пересечение между линией и сеткой быстрым способом

Question

Есть ли способ, позволяющий мне найти все точки пересечения между линией и сеткой?(Круги пересечений нарисованы не в масштабе друг с другом, я знаю)но этот алгоритм ужасно неэффективен (O(m*n), где m - это число x сетки, а n - это число y сетки).

Я ищу лучшегоалгоритм на этом.

Answer 1

Я не уверен, что действительно понимаю вопрос.Это то, что вы ищете случайно?

Иллюстрация 1 http://i31.tinypic.com/mwwg37.png

Иллюстрация 2 http://i27.tinypic.com/657uc1.png

Answer 2

Звучит так, будто вам нужен Цифровой дифференциальный анализатор или Алгоритм Брезенхема .Bresenham - это тот же алгоритм, который используется для рисования линий на растровом изображении;в этом случае раскраска пикселя эквивалентна проверке столкновений в этом квадрате.

Answer 3

Если сетка выровнена по оси:

1. выяснить уравнение линии
2. вычислить точки пересечения напрямую, используя x или y линии сетки в качестве фиксированной переменной

Если сетка регулярная, расстояние между пересечениями с каждой горизонтальной линией будет одинаковым.То же самое касается и вертикальных линий.В этом случае вы могли бы просто сделать простой итеративный алгоритм с dx и dy.