Я пытаюсь объединить две вещи. Я пишу игру, и мне нужно определить квадраты сетки, лежащие на линии с конечными точками с плавающей точкой.
Более того, мне нужно включить все квадраты сетки, к которым он прикасается (т.е. не только линию Брезенхэма, но и синюю):
Может кто-нибудь подсказать мне, как это сделать? Очевидным решением является использование алгоритма наивной линии, но есть ли что-то более оптимизированное (быстрее)?
c#
algorithm
grid
interpolation
floating-point
SmartK8
источник
источник
Ответы:
Вы ищете алгоритм обхода сетки. Эта статья дает хорошую реализацию;
Вот базовая реализация в 2D, найденная на бумаге:
На бумаге также есть версия для 3D-лучей.
В случае, если ссылка гниет , вы можете найти много зеркал с ее именем: более быстрый алгоритм обхода вокселей для трассировки лучей .
источник
Идея Blue хороша, но реализация немного неуклюжа. На самом деле, вы можете легко сделать это без sqrt. Давайте пока предположим, что вы исключили вырожденные падежи (
BeginX==EndX || BeginY==EndY
) и сосредоточились только на направлениях линий в первом квадранте, поэтомуBeginX < EndX && BeginY < EndY
. Вам придется реализовать версию как минимум для одного другого квадранта, но это очень похоже на версию для первого квадранта - вы проверяете только другие ребра. В псевдокоде C'ish:Теперь для других квадрантов, вы просто изменить
++cx
или++cy
и условие цикла. Если вы используете это для столкновения, вам, вероятно, придется реализовать все 4 версии, в противном случае вы можете обойтись двумя, соответствующим образом поменяв местами начальную и конечную точки.источник
Ваше предположение не обязательно, чтобы найти ячейки, но линии, которые это пересекает на этой сетке.
Например, взяв ваше изображение, мы можем выделить не ячейки, а линии сетки, которые оно пересекает:
Затем это показывает, что если он пересекает линию сетки, то ячейки по обе стороны от этой линии являются заполненными.
Вы можете использовать алгоритм пересечения, чтобы определить, будет ли ваша линия с плавающей точкой пересекать их, масштабируя ваши точки в пикселях. Если у вас есть соотношение плавающих координат: пикселей 1,0: 1, то вы отсортированы, и вы можете просто перевести его напрямую. Используя алгоритм пересечения отрезков, вы можете проверить, пересекается ли ваша нижняя левая линия (1,7) (2,7) с вашей линией (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/
Потребуется некоторый перевод с c на C #, но вы можете понять идею из этой статьи. Я приведу код ниже в случае разрыва связи.
Если вам нужно выяснить только, когда (и где) пересекаются отрезки, вы можете изменить функцию следующим образом:
источник
JS Demo:
Показать фрагмент кода
источник
Я столкнулся с той же проблемой сегодня и сделал довольно большую гору спагетти из холма моль, но в итоге получил кое-что, что работает: https://github.com/SnpM/Pan-Line-Algorithm .
Из ReadMe:
ReadMe объясняет решение намного лучше, чем код. Я планирую пересмотреть это, чтобы быть менее вызывающим головную боль.
Я знаю, что опоздал на этот вопрос примерно на год, но я надеюсь, что это дойдет до тех, кто ищет решение этой проблемы.
источник