Как определить граничные точки области, перекрытой между 2 прямоугольниками в 2D?

Question

Я хочу вернуть координаты точек, ограничивающих область перекрытия между 2 произвольными прямоугольниками в 2D.Как лучше всего подойти к этому, чтобы позаботиться обо всех особых случаях, например:

• Прямоугольники, пересекающиеся только в одной вершине?(программа должна была бы вернуть одинокую вершину)
• Прямоугольники, которые разделяют всю или часть стороны?(программа должна будет возвращать конечные точки общего отрезка)

Чтобы добавить к сложности, она должна упорядочить точки по часовой стрелке / против часовой стрелки.Таким образом, я могу использовать алгоритм выпуклой оболочки, чтобы упорядочить их перед отчетом, но если есть алгоритм, который может напрямую определять ограничивающие точки по порядку, это будет лучшим !!

Любые идеи о том, чтопроспекты, на которые я должен смотреть?Я не ищу проекты кода и т. Д., Только общее представление об общем алгоритме, для которого мне не нужно хранить много кода типа if "special case" then "do this".

РЕДАКТИРОВАТЬ: прямоугольники произвольны -то есть они могут / не могут быть параллельны оси X / Y ...

Answer 1

Хорошо, мы попробуем это снова ...

Рассмотрим объединение двух, состоящих из областей, определенных путем рисования линии от каждой вершины в ABCD (черным) до EFGH (красным):

Здесь сложная часть состоит из всех форм, определяемых этими линиями (как серые линии, так и исходные линии, исходящие из прямоугольников ABCD и EFGH.)

Как только вы это выясните, создайте связанный список этих фигур и предположим, что каждая из этих фигур существует в пересечении.

Шаг 1. Перевести иповерните все так, чтобы ABCD имела одну вершину на 0,0, а ее линии параллельны / перпендикулярны осям x и y.

Шаг 1A. Найдите наименьшую вершину значения y в ABCD, а затем вычесть его из всех других вертиков в сцене.Предположим для целей демонстрации, что этой вершиной является C. Вычитая C из каждой вершины сцены, мы эффективно переместим начало координат (0,0) в C, упрощая вращение вокруг C.

for all shapes in linked list {
    for all vertices in shape {
        vertex -= C;
    }
}

Шаг 1B. Повернуть все вокруг начала координат на угол, равный углу между вектором C-> B и осью x, чтобы B попал на ось x:

// see http://en.wikipedia.org/wiki/Atan2
float rotRadians = atan2(B.x, B.y);  // assuming ABCD vertices are labelled clockwise

for all shapes in linked list {
    for all vertices in shape {
        rot(thisVert, rotRadians);
    }
}


// ...

// function declaration
void rot(theVertex, theta) {
    tempX = theVertex.x;
    tempY = theVertex.y;

    theVertex.x = cos(theta) * tempX + sin(theta) * tempY;
    theVertex.y = cos(theta) * tempY - sin(theta) * tempX;

}

Если вершины ABCD были помечены по часовой стрелке, вершины ABCD теперь должны выглядеть следующим образом:

A = ABCDx , ABCDy
B = ABCDx ,   0
C = 0     ,   0
D = 0     , ABCDy

(Если они не были помечены по часовой стрелке, то проверка «лежит внутри» на шаге 2 выиграна »это работает, поэтому убедитесь, что вершина, используемая в вызове atan2(...), является вершиной против часовой стрелки от самой нижней вершины.)

Шаг 2. Теперь мы можем легко проанализировать, есть ли формалежит внутри прямоугольника ABCD, например, if (thisVert.x >= 0 && thisVert.y >= 0 && thisVert.x <= ABCDx && thisVert.y <= ABCDy).Пройдите по связанному списку фигур и убедитесь, что каждая вершина каждой фигуры находится внутри ABCD.Если одна вершина фигуры не лежит внутри ABCD, то эта фигура не является частью пересечения ABCD / EFGH.Отметьте его как не являющийся частью пересечения и перейдите к следующей фигуре.

Шаг 3. Отмените поворот на шаге 1B, затем отмените перевод на шаге 1A.

Шаг 4. Повторите шаги 1-3 с EFGH вместо ABCD, и вы получите набор пересечений.

---

Если единственным пересечением между двумя наборами является линия,тогда вышеупомянутое ничего не возвратит как пересечение.Если пересечение == NULL, то проверьте, пересекаются ли линии.

Если пересечение все еще равно NULL, то проверьте точки пересечения.

Answer 2

Просто используйте общий метод пересечения выпуклых многоугольников. Посмотри вверх intersect convex polygons rotating calipers.

Answer 3

Я нашел разумный метод, который должен охватывать все возможные случаи:

Все, что нам нужно, это в основном 3 шага:

Шаг 1:

for each side Si of R1
    for each side Sj of R2
           Check if Si and Sj intersect. If they do, push the point in results array
           (This also has to take care of the case in case Si and Sj overlap, which is 
           basically checking if they  have the same equation or not - if so, push in 
           the points of overlap. This also takes care of the case where a vertex of 
           R2 lies on Si).
    next
next

Шаг 2:

for each vertex Vi of R1
   Check if Vi lies inside R2, If so, push it in the results array.
next

Шаг 3:

for each vertex Vi of R2
   Check if Vi lies inside R1, If so, push it in the results array.
next

Теперь упорядочите массив результатов и верните

Для шагов 2 и 3 (как найти, лежит ли точка внутри прямоугольника) - я бы использовал эту превосходную статью (последний алгоритм, изложенный там).

Answer 4

Найти все пересечения сегментов прямоугольников.Результат состоит из некоторых из них и некоторых из начальных вершин.Чтобы найти их, просто проверьте каждую точку в обоих прямоугольниках.Удалите ненужные точки (если на одной линии 3 или более).Результат выпуклый, и ни одна полученная точка не находится строго внутри него, поэтому (если их хотя бы 3) сортируйте точки по некоторой внутренней точке по углу и наслаждайтесь результатом.

Answer 5

Это, вероятно, очень грубо, но:

object rectangle { 

     pos  { x, y }              // top-left position
     size { height, width }     // rectangle-size
}


collision::check (rectangle rect) {

     // collision-detection logic 

     collision->order_coords(coords);   // order-coords clockwise;
     return collision_result_object;    // return collided vertices, ordered clockwise, or 0 if rect hit nothing
}

collision::order_rects (rectangle *rect, opt angle)  {

     return clockwise_rects; // returns rectangles ordered clockwise
}

collision::order_coords (coordinate *coord, opt angle) {

     return ordered_coords; // recieves coordinates and returns ordered clockwise
}

rectangle rects; // bunch of rectangles

ordered_rects = collision->order_rects (rects); // order rects starting at 12PM

loop {    

       foreach ordered_rects as i {

           if (collision->check(i)) {

           array_of_collision_result_objects[i] = collision->check(i);      // start checking rects starting at 12PM, if collision found, return ordered vertexes
           }
       }

}