Я пытаюсь найти, пересекает ли прямоугольник вогнутый многоугольник.Этот алгоритм выполняет это? - PullRequest
Новая
       1

Я пытаюсь найти, пересекает ли прямоугольник вогнутый многоугольник.Этот алгоритм выполняет это?

7 голосов
/ 12 августа 2010

Я пытаюсь найти, пересекает ли прямоугольник вогнутый многоугольник.Я нашел этот алгоритм: 

double determinant(Vector2D vec1, Vector2D vec2){
    return vec1.x*vec2.y-vec1.y*vec2.x;
}

//one edge is a-b, the other is c-d
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
    double det=determinant(b-a,c-d);
    double t=determinant(c-a,c-d)/det;
    double u=determinant(b-a,c-a)/det;
    if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION;
    return a*(1-t)+t*b;
}

Если я выполню это 4 раза (сверху вниз, сверху вниз слева, сверху вниз справа, снизу справа) * (все ребра моего многоугольника), это будет эффективнои точно скажите мне, если прямоугольник имеет часть или весь вогнутый многоугольник внутри?Если нет, то чего бы не хватало?

Спасибо

Ответы [ 3 ]

13 голосов
/ 12 августа 2010

Код пытается найти точку пересечения двух сегментов - AB и CD.

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

Допустим, точка A имеет координаты (xa, ya), B - (xb, yb) и так далее.Допустим, 

dxAB = xb - xa
dyAB = yb - ya
dxCD = xd - xc
dyCD = yd - yc

Следующая система двух линейных уравнений 

| dxAB dxCD |   | t |   | xc-xa |
|           | * |   | = |       |
| dyAB dyCD |   | u |   | yc-ya |

, если она решена для t и u, даст вам пропорциональное положение точки пересечения настрока AB (значение t) и строка CD (значение u).Эти значения будут лежать в диапазоне [0, 1], если точка принадлежит соответствующему сегменту, и вне этого диапазона, если точка находится вне сегмента (на линии, содержащей сегмент).

Для решения этой проблемыВ системе линейных уравнений можно использовать хорошо известное правило Крамера .Для этого нам понадобится определитель 

| dxAB dxCD |
|           |
| dyAB dyCD |

, который в точности равен determinant(b - a, c - d) из вашего кода.(На самом деле, здесь у меня есть determinant(b - a, d - c), но это не очень важно для целей этого объяснения. Код, который вы по какой-то причине разместили, меняет местами C и D, см. Примечание PS ниже).

нам также понадобится определитель 

| xc-xa dxCD |
|            |
| yc-ya dyCD |

, который точно равен determinant(c-a,c-d) из вашего кода, и определитель 

| dxAB xc-xa |
|            |
| dyAB yc-ya |

, который точно равен determinant(b-a,c-a).

Разделив эти детерминанты в соответствии с правилом Крамера, мы получим значения t и u, что в точности соответствует тому, что делается в опубликованном вами коде.

Затем код переходит к проверке значенийt и u, чтобы проверить, пересекаются ли сегменты на самом деле, т.е. принадлежат ли t и u диапазону [0, 1].И если они это сделают, он вычисляет фактическую точку пересечения, оценивая a*t+b*(1-t) (эквивалентно, он может оценить c*u+d*(1-u)).(Опять же, см. Примечание PS ниже).

PS В исходном коде точки D и C "поменялись местами" в том смысле, что код выполняет c - d, где я делаюd - c в моем объяснении.Но это не имеет значения для общей идеи алгоритма, если соблюдать осторожность со знаками.

Этот обмен точек C и D также является причиной для выражения a*(1-t)+t*b, используемого при оценке точки пересечения,Обычно, как я объяснил, можно было увидеть что-то вроде a*t+b*(1-t).(У меня есть сомнения по этому поводу, хотя. Я ожидал бы увидеть a*t+b*(1-t) там даже в вашей версии. Может быть ошибка.)

PPS Автор, если код забыл проверитьдля det == 0 (или очень близко к 0), что произойдет в случае, когда сегменты параллельны.

2 голосов
/ 12 августа 2010

Я думаю, что должно работать следующее: 

(1) for each e1 in rectangle_edges, e2 in polygon_edges
    (1.1) if edgeIntersection(e1,e2) != NO_INTERSECTION
        (1.1.1) return true
(2) if (max_polygon_x < max_rectangle_x) and (min_polygon_x > min_rectangle_x) and (max_polygon_y < max_rectangle_y) and (min_polygon_y > min_rectangle_y)
    (2.1) return true
(2) return false

Редактировать : Добавлена ​​проверка, находится ли многоугольник внутри прямоугольника.

0 голосов
/ 12 августа 2010

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

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

...