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

Question

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

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 раза (Top направо, сверху вниз слева, вверху справа внизу, внизу справа) * (все ребра моего многоугольника) будет это точно и эффективно скажите, если внутри прямоугольника есть часть или весь вогнутый многоугольник внутри? Если бы не то, что было бы пропало?

Благодаря

Answer 1

Код пытается найти точку пересечения двух сегментов - 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, даст вам пропорциональную положение точки пересечения на линии АВ (значение t) и на line CD (значение u). Эти значения будут находиться в диапазоне [0, 1], если точка принадлежит соответствующему сегменту и вне этого диапазона, если точка лежит вне сегмента (на линии, содержащей сегмент).

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

| dxAB dxCD | 
|   | 
| dyAB dyCD | 

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

И мы также должны определитель

| 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, чтобы проверить, если сегменты фактически пересекаются, т.е. ли как tu и принадлежат к [0, 1] диапазону. И если они это сделают, он вычисляет фактическую точку пересечения, оценивая a*t+b*(1-t) (эквивалентно, он мог бы оценить c*u+d*(1-u)). (Опять же, см. Примечание P.S. ниже).

P.S. В исходном коде точки D и C «заменены» в том смысле, что код делает c - d, где я делаю d - c в своих пояснениях. Но это не имеет никакого значения для общей идеи алгоритма, если вы будете осторожны со знаками.

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

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

Answer 2

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

(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 

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

Answer 3

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

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