Найти правильные ячейки сетки, пересекающие четырехугольник произвольной формы

Question

Мне нужно найти все индексы [x, y] для ячеек сетки, пересекающих четырехугольник произвольной формы, определяемый его угловыми координатами;

• ячейки сетки - это плитки с 128 x 128 px

• ячейки сетки имеют целочисленный индекс от [-nx, -ny] до [nx, ny]
  (максимальное расширение - это квадрат с (2nx * 128) * (2ny * 128) px)

• четырехугольник определяется угловыми точками с координатами (qx, qy) в пиксельном пространстве, заданными как (tl, tr, br, bl)

• Это встроено в three.js сцену:
  • угловые точки / координаты направляются с камеры на базу THREE.PlaneBufferGeometry

Как получить все пересекающиеся плитки вычислительно эффективным способом в JavaScript?

Сейчас я вычисляю плитки по периметру, пересекая каждое четырехугольное ребро, используя mx + b с размером плитки (128px) в качестве шага; оттуда я просто добавляю ряд индексов внутренней плитки для ряда. Но это несколько неуклюже, что может быть или не быть проблемой навыков кодирования. Я собираюсь попробовать использовать THREE.Raycaster , чтобы получить индексы плитки по периметру, но пока не знаю, как именно.

Я ищу лучшее решение по алгоритму; основные формулы, псевдокод, идеи или определенные решения.

Answer 1

Чтобы эффективно найти ячейки сетки, пересекаемые ребрами квадрата, вы можете использовать алгоритм обхода сетки Woo и Amanatides: статья «Алгоритм быстрого обхода вокселей ...» .
Практическая реализация в grid traversalсечение здесь
Пример:

Для внутренних ячеек выпуклых четырехугольников: во время обхода ребра запомните крайнюю левую ячейку в рядудля «правых» ребер, самая правая ячейка для «левых» ребер, и заполните горизонтальный зазор между ними.