Я пытаюсь найти, пересекает ли прямоугольник вогнутый многоугольник. Этот алгоритм выполняет это?
Я пытаюсь найти, пересекает ли прямоугольник вогнутый многоугольник. Я нашел этот алгоритм:
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 ответа
Код пытается найти точку пересечения двух сегментов - 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 |
, который в точности равен определителю (b - a, c - d) из вашего кода. (На самом деле, у меня есть определитель (b - a, d - c) , но это не очень важно для целей этого объяснения. Код, который вы опубликовали по какой-то причине, меняет местами C и D, см. примечание PS ниже).
И нам также понадобится определитель
| xc-xa dxCD |
| |
| yc-ya dyCD |
, который является точно определителем (ca, cd) из вашего кода, и определитель
| dxAB xc-xa |
| |
| dyAB yc-ya |
, который в точности является определителем (ba, ca) .
Разделив эти детерминанты в соответствии с правилом Крамера, мы получим значения t и u , что и сделано в опубликованном вами коде.
Затем код переходит к проверке значений t и u , чтобы проверить, действительно ли сегменты пересекаются, то есть, оба ли t и u относятся к диапазону [0, 1] .И если они это сделают, он вычисляет фактическую точку пересечения путем вычисления a * t + b * (1-t) (эквивалентно, он может вычислить c * u + d * (1-u) ). (Опять же, см. Примечание P.S. ниже).
P.S. В исходном коде точки D и C «поменяны местами» в том смысле, что код выполняет c - d , где я делаю d - c в моем объяснении. Но это не имеет значения для общей идеи алгоритма, если только осторожно обращаться со знаками.
Эта замена точек C и D также является причиной того, что выражение a * (1-t) + t * b используется при оценке точки пересечения. Обычно, как и в моем объяснении, можно ожидать увидеть там что-то вроде a * t + b * (1-t) . (У меня есть сомнения по этому поводу. Я ожидал увидеть там a * t + b * (1-t) даже в вашей версии. Это может быть ошибка.)
P.P.S. Автор, если код забыл проверить det == 0 (или очень близко к 0), что произойдет в случае, если сегменты параллельны.
Думаю, должно работать следующее:
(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
Изменить : Добавлена проверка, находится ли многоугольник внутри прямоугольника.
Насколько я могу судить после беглого взгляда, он пытается определить, пересекаются ли 2 отрезка линии, и если да, то каковы координаты точки пересечения.
Нет, этого недостаточно, чтобы определить, пересекаются ли ваш прямоугольник и ваш многоугольник, потому что вы все равно пропустите случай, когда многоугольник полностью внутри прямоугольника, или наоборот.