Пересечение прямоугольников отрезком

← →
mega (2008-02-08 15:16) [0]

Привет Мастерам! Извниняюсь за оффтопик.. Но не подскажете ли вы решение следующей проблемы? Попытаюсь сформулировать на примере шахматной доски.. Есть отрезок в известных координатах в пределах плоскости доски, как узнать через какие клетки он проходит? Известны начальная, конечная клетки и их размер...

← →
Jeer © (2008-02-08 15:21) [1]

Рассчитываются точек-центров клеток и вычисляется превышение расстояния (полудиагональ) от этих точек до заданной прямой.

← →
Jeer © (2008-02-08 15:23) [2]

P.S.
>Рассчитываются (координаты) точек-центров

← →
mega (2008-02-08 15:44) [3]

Jeer, а можно подетальнее? Т.е. циклом по всем клеткам, вычисляем координаты центра?... А дальше? Координты начал и конца отрезка в произвольном месте клетки

← →
ketmar © (2008-02-08 15:50) [4]

>[3] mega (2008-02-08 15:44:00)
ты от точки до прямой расстояние вычислить асилишь? в чём проблема дальше? перебрать даже 64 клетки в тупом цикле?

зыж или вообще взять DDA-алгоритм.

---
Understanding is not required. Only obedience.

← →
mega (2008-02-08 15:58) [5]

Расстояние то я асилю... А какое условие что проходит через клетку?

← →
Jeer © (2008-02-08 16:02) [6]

> превышение расстояния (полудиагональ) от этих точек до заданной
> прямой.

Условие - что не проходит.
Обратное - просто not

← →
ketmar © (2008-02-08 16:04) [7]

>[5] mega (2008-02-08 15:58:00)
таки расстояние. впрочем, лично я бы делал DDA.

---
Understanding is not required. Only obedience.

← →
Jeer © (2008-02-08 16:12) [8]

Не озвучена целевая задача, поэтому можно телепатировать до ус...

← →
mega (2008-02-08 16:15) [9]

Извиняюсь на неграммотность.. Просто не совем понятен термин "полудиагональ"... Это 0,5 диагонали? Если так то как быть, например, со случаем когда прямая проходит под клеткой горизонтально? Расстояние от нее до центра высшей клекти меньше чем 0,5 диагонали

← →
Anatoly Podgoretsky © (2008-02-08 16:21) [10]

> ketmar (08.02.2008 15:50:04) [4]

Это самое простое, работает для любых пикселей.

← →
mega (2008-02-08 16:26) [11]

спасибо за советы, пробую DDA...

Ну тады, если я опять не туплю, не полудиагональ, а сумма полустороны d и вот етого: d*(sqrt(2)-1)*sin(2*(oX^AB)), где d - полусторона, oX^AB - угол между осью абсцисс и отрезком.

Если в пикселах, то сканировать вдоль прямой попадание на заданную решетку.

← →
NiGGa (2008-02-08 17:00) [14]

Учебник аналитической геометрии (класс 9-10, точно не помню) + читать.

Пересечение прямоугольников отрезком Найти похожие ветки