Как получить длину отрезка, пересекающего квадрат?

Question

У меня есть линия, определяемая параметрами m, h, где

y = m*x + h

Эта линия проходит по сетке (то есть в пикселях).Для каждого квадрата (a, b) сетки (т.е. квадрата [a, a+1] x [b, b+1]) я хочу определить, пересекает ли данная линия этот квадрат или нет, и если да, то какова длина сегмента в квадрате.

В конце концов, я бы хотел сделать это с несколькими строками одновременно (т. Е. m и h - векторы, в стиле matlab), но сейчас мы можем сосредоточиться на «простом» случае.

Я понял, как определить, пересекает ли линия квадрат:

1. Вычислить пересечение линии с вертикальными линиями x = a и x = a + 1 и горизонтальными линиями y = b и y = b + 1
2. Проверьте, находятся ли 2 из этих 4 точек на квадратных границах (т. е. a <= x < a + 1 и b <= y < b + 1)

Если два из этих точек находятся наквадрат, линия пересекает его.Затем, чтобы вычислить длину, вы просто вычитаете две точки и используете теорему Пифагора.

Моя проблема больше на стороне реализации: как я могу реализовать это красиво (особенно при выборе, какие 2 точки вычесть)

Answer 1

Пусть квадрат определяется угловыми точками (a, b), (a + 1, b), (a, b + 1), (a + 1, b + 1) .

Шаг 1: Проверьте, пересекает ли линия квадрат ...

(a) Замените каждую из координат 4 угловых точек, по очереди на y - mx - h .Если признак этой оценки включает как положительные, так и отрицательные условия, перейдите к шагу b.В противном случае линия не пересекает квадрат.

(b) Теперь есть два подслоя:

(b1) Случай 1: На шаге (a) у вас было три точки, для которых y - mx - h оценивается по одному знаку, а четвертая точка оценивается по другому знаку.Пусть эта 4-я точка будет некоторой (x *, y *) .Тогда точки пересечения составляют (x *, mx * + h) и ((y * -h) / m, y *) .

(b2) Случай 2: На шаге (а) у вас было две точки, для которых y - mx - h оценивается по одному знаку, а две другие точки оцениваются по другому знаку.Выберите любые две точки с одинаковым знаком, скажем, (x *, y *) и (x * + 1, y *) .Тогда точки пересечения составляют (x *, mx * + h) и (x * + 1, m (x * + 1) + h) .

Вам следует рассмотреть некоторые вырожденные случаи, когда линия касается ровно одной из четырех угловых точек, и случай, когда линия лежит ровно на одной стороне квадрата.

Answer 2

Вы можете сделать так: сначала найдите центр квадрата, а затем найдите длину диагонали.Если расстояние от центра квадрата до линии меньше длины диагонали, линия будет пересекать квадрат.и как только вы узнаете, что линия будет пересекаться, вы сможете легко найти отрезанный отрезок.Я думаю, что вы пытаетесь сделать весовую матрицу для техники алгебраической реконструкции.Я надеюсь, что это правильный ответ.Это был мой первый ответ в стеке потока.:)

Answer 3

Ваш предложенный метод может столкнуться с проблемами на шаге (1), когда m равен 0 (при попытке вычислить пересечение с y = k).

если m равно 0, то это легко (длина отрезка линии равна 1 или 0, в зависимости от того, b <= h <= b+1).

В противном случае вы можете найти пересечения с x = a и a+1, скажем, y_a, y_{a+1} через подстановку. Затем обрезайте y_a и y_{a+1} между b и b+1 (скажем, y1 и y2, т.е. y1 = min(b+1, max(b, y_a)) и аналогично для y2) и используйте пропорцию abs((y1-y2)/m) * sqrt(m^2+1).

Здесь используется тот факт, что отрезок между x=k и x=k+1 равен sqrt(m^2+1), а разница в y равна m, и сходство.