Есть прямоугольник, координаты известны, и есть отрезок, координаты тоже известны. Гарантируется, что одна точка отрезка находится внутри прямоугольника, а другая - снаружи. Как найти точку пересечения этого отрезка с прямоугольником? Смотрел реализацию алгоритма Коуэна-Сазерленда, но он не помог, зацикливается. Можно влоб проверять по уравнению прямой для каждой стороны прямоугольника, но есть ли что-то более правильное?

З.Ы. подобная математика была очень давно, ничего не помню, да и не знал наверное =)

задан 29 Ноя '11 12:26

изменен 29 Ноя '11 13:36

Expert's gravatar image


10115

10|600 символов нужно символов осталось
3

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

Чтобы пересечь два отрезка достаточно пересечь две прямых и проверить, что точка пересечения принадлежит обоим отрезкам.

ссылка

отвечен 29 Ноя '11 14:30

10|600 символов нужно символов осталось
0

А, пардон, как Коэн-Сазерленд позволяет найти именно точку пересечения? Или я чего-то путаю? Так-то, решение в лоб - самое простое и не сказать даже, что особо неэффективное.

ссылка

отвечен 29 Ноя '11 15:51

1

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

(29 Ноя '11 15:57) AlexDenisov

Все, все, разобрался. Ну да, просто раньше с этим алгоритмом не сталкивался. Странно, на самом деле. При учете того, что граница прямоугольника включена в прямоугольник, цикл должен пройти не более двух раз и на границе остановиться в любом случае. Можете кинуть условия, на которых уходит в цикл? А то "на весу" проблему решить не получается. А в целом да, алгоритм милый.

(29 Ноя '11 17:53) Occama
10|600 символов нужно символов осталось
0

Наивная реализация Сазерленда-Коэна генерирует на каждой итерации алгоритма новую точку, что приводит во floating-point к неустойчивому поведению -- например, посчитанная точка может вылетать из ожидаемой части плоскости. Кстати, это касается и точки, посчитанной 'наивным' способом -- она может не лежать на границе прямоугольника и на исходном отрезке :)

В вашем случае, я думаю, можно несколько модифицировать СК, чтобы эффективно найти сторону, пересекающую отрезок, упорядочив координаты. Чуть позже попробую сюда кинуть скетч алгоритма.

ссылка

отвечен 1 Дек '11 18:19

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,282
×75

задан
29 Ноя '11 12:26

показан
2731 раз

обновлен
1 Дек '11 18:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru