Как проверить, находится ли какая-либо точка (или часть) линии внутри или касается прямоугольника

Я хочу проверить, находится ли линия (или любая точка линии) внутри прямоугольника или пересекает прямоугольник.

У меня есть (x0, y0) и (x1, y1) начальная и конечная точки линии. Кроме того, (ax,ay) и (bx,by) как верхняя левая и нижняя правая точки прямоугольника

Например,

     ____________
    |            |
 ---|-----       |    Result: true
    |            |
    |____________|

    /
  _/__________
 |/           |
 /            |      Result: true
/|            |
 |____________|


     ____________
    |            |
    |   -------- |   Result: true
    |            |
    |____________|    ----------     Result: false

Кто-нибудь может подсказать, как это сделать? Я не хочу знать, что это за точка, я просто хочу знать, есть она или нет.

Большое спасибо за помощь


math line
person user427969    schedule 28.01.2011    source источник
comment
+1 за чистое искусство ASCII :)   -  person alex    schedule 28.01.2011
comment
Быстрый Google для Коэна Сазерленда должен помочь вам начать в правильном направлении.   -  person Jerry Coffin    schedule 28.01.2011
comment
Рассматривайте каждое ребро как отдельный отрезок. Тогда это просто вопрос определения пересечения линии и сегмента и случая, когда он полностью содержится внутри. Конечно, это просто беглое наблюдение и, вероятно, не идеальный способ решения такого типа пересечения (это также очень распространенное пересечение - я был бы очень удивлен, если бы это был оригинальный вопрос ; -)   -  person    schedule 28.01.2011

Ответы (1)


arrow_upward
5
arrow_downward

Первый и третий случаи тривиальны — просто верните true, если какая-либо конечная точка линии находится внутри прямоугольника (т. е. > ax и ay, ‹ bx и by).

Второй представляет собой проблему — мы больше не можем полагаться на конечные точки нашей линии. В этом случае нам придется тестировать линию с каждым краем прямоугольника.

Уравнение для нашей линии будет (x1 - x0)*x + (y1 - y0)*y + x0*y0 - x1*y1 = 0 , и мы можем построить аналогичное уравнение для каждой стороны прямоугольника, используя углы. После этого, подставив уравнение для сторон прямоугольника в нашу линию, мы получим пересечение.

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

Более подробный отчет об этом есть в этом обсуждении.

person Andy Mikula    schedule 28.01.2011
comment
2) мне кажется не подходит. возьмем, например, случай единичного квадрата (от 0,0 до 1,1) по сравнению с сегментом (-1,0)-(1,3). - person Jimmy; 28.01.2011
comment
Ты прав! Это приведет к ложному срабатыванию. Я обновлю свой ответ. - person Andy Mikula; 28.01.2011