|
Есть прямоугольник, координаты известны, и есть отрезок, координаты тоже известны. Гарантируется, что одна точка отрезка находится внутри прямоугольника, а другая - снаружи. Как найти точку пересечения этого отрезка с прямоугольником? Смотрел реализацию алгоритма Коуэна-Сазерленда, но он не помог, зацикливается. Можно влоб проверять по уравнению прямой для каждой стороны прямоугольника, но есть ли что-то более правильное? З.Ы. подобная математика была очень давно, ничего не помню, да и не знал наверное =) задан 29 Ноя '11 12:26 
AlexDenisov |
|
А, пардон, как Коэн-Сазерленд позволяет найти именно точку пересечения? Или я чего-то путаю? Так-то, решение в лоб - самое простое и не сказать даже, что особо неэффективное. отвечен 29 Ноя '11 15:51 
Occama 1
В приведенном на википедии коде, на последней итерации временная точка должна содержать как раз координаты пересечения, и она содержит, но на некоторых вызовах тупо уходит в вечный цикл. В общем еще поковыряю его, и если не получится, то буду делать влоб.
(29 Ноя '11 15:57)
AlexDenisov
Все, все, разобрался. Ну да, просто раньше с этим алгоритмом не сталкивался. Странно, на самом деле. При учете того, что граница прямоугольника включена в прямоугольник, цикл должен пройти не более двух раз и на границе остановиться в любом случае. Можете кинуть условия, на которых уходит в цикл? А то "на весу" проблему решить не получается. А в целом да, алгоритм милый.
(29 Ноя '11 17:53)
Occama
|
|
Наивная реализация Сазерленда-Коэна генерирует на каждой итерации алгоритма новую точку, что приводит во floating-point к неустойчивому поведению -- например, посчитанная точка может вылетать из ожидаемой части плоскости. Кстати, это касается и точки, посчитанной 'наивным' способом -- она может не лежать на границе прямоугольника и на исходном отрезке :) В вашем случае, я думаю, можно несколько модифицировать СК, чтобы эффективно найти сторону, пересекающую отрезок, упорядочив координаты. Чуть позже попробую сюда кинуть скетч алгоритма. отвечен 1 Дек '11 18:19 
Антон Ковалев |