Область пересечения прямоугольника и прямоугольника

Ответ 1

Поскольку вы заявили, что прямоугольники не могут быть выровнены, возможные ответы могут быть ничем, точкой, сегментом линии или полигоном с 3-8 сторонами.

Обычным способом выполнения этой операции 2d boolean является выбор порядка краев по часовой стрелке, а затем оценка краевых сегментов между критическими точками (пересечениями или углами). На каждом перекрестке вы переключаетесь между краевым сегментом первого прямоугольника на край второго или наоборот. Вы всегда выбираете сегмент слева от предыдущего сегмента.

Есть много деталей, но основным алгоритмом является поиск всех пересечений и упорядочение их по их краям с соответствующей структурой данных. Выберите пересечение (если оно есть) и выберите отрезок линии, ведущий от этого пересечения. Найдите сегмент другого прямоугольника слева от выбранного начального сегмента. На рисунке мы выбираем зеленый сегмент на пересечении a (в направлении, указанном стрелкой) в качестве эталонного сегмента. Сегмент другого прямоугольника, который находится справа, является отрезком от a до b. Используйте это как следующий ссылочный сегмент и выберите зеленый сегмент слева от него. Что сегмент от b до c. Найти сегмент cd так же. Следующий сегмент от d до угла, поэтому угол также находится в списке вершин для пересечения. Из кукурузы мы возвращаемся к.

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

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

Некоторые детали, которые я оставляю вам, следующие:

• Что делать, если угол совпадает с краем или вершиной другого треугольника?

• Что делать, если пересечений нет? (один прямоугольник внутри другого, или они не пересекаются - вы можете использовать проверки "точка-в-полигон", чтобы понять это. См. Статья в Википедии о полигонах.

• Что делать, если пересечение является одной точкой или сегментом?

Ответ 2

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

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

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

  intersection_area = bounding_box_area * num_of_dots_inside_both/ num_of_repetitions

Результат, конечно, будет более точным, если число повторений будет больше. Кстати, этот метод называется методом Монте-Карло.

Ответ 3

Вы можете вычислить точки пересечения путем решения уравнений пересечения для всех пар сторон фигур: /frac {x - a} {b - a} =/frac {x - c} {d - c}

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

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

Ответ 4

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

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

По существу это становится проблемой триангуляции.

Существует хорошее введение здесь с некоторыми указателями на структуры данных и алгоритмы.

EDIT:

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

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

Ответ 5

Если вы используете Qt, то пересечение может быть вычислено как пересечение QPolygonF. Примерно так:

QPolygonF p1,p2, intersected;
p1 << QPointF(r1x1,r1y1) << ... << QPointF(r1x4, r1y4);
p2 << QPointF(r2x1,r2y2) << ... << QPointF(r2x4, r2y4);
intersected = p1.intersected(p2);

float area = polyArea(intersected); // see code block below

(r1 = прямоугольник 1, r2 = прямоугольник 2, с 4 соответствующими координатами x и y).

Теперь вычислите область (используя уже упомянутую формулу Shoelace):

inline float polyArea(const QPolygonF& p)
{
    //https://en.wikipedia.org/wiki/Polygon#Area_and_centroid
    const int n = p.size();
    float area = 0.0;
    for (int i=0; i<n; i++)
    {
        area += p[i].x()*p[(i+1)%n].y() - p[(i+1)%n].x()*p[i].y();
    }
    if (area < 0)
        return -0.5*area;
    else
        return 0.5*area;
}

Мой код здесь: public domain