Площадь пересечения прямоугольника с прямоугольником

Question

Ниже 2 прямоугольников .Учитывая координаты вершин прямоугольника - (x1, y1) ... (x8, y8), как можно вычислить область перекрывающейся области (белой на рисунке ниже)?Обратите внимание, что:

1. Координаты точек могут быть любыми
2. Прямоугольники могут или не могут перекрываться
3. Предполагается, что область равна 0, если прямоугольники не перекрываются или перекрываютсяв точке или линии.
4. Если один прямоугольник находится внутри другого, рассчитайте площадь меньшего прямоугольника.

Answer 1

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

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

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

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

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

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

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

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

• Что если пересечение представляет собой одну точку или отрезок?

Answer 2

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

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

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

   intersection_area = bounding_box_area * num_of_dots_inside_both / num_of_repetitions

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

Answer 3

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

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

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

Answer 4

Может быть, вам нужно использовать opencv. Используйте функцию fillPoly () для создания прямоугольника. Убедитесь, что прямоугольник заливки белый (255, 255, 255). Затем используйте функцию copyTo (), и вы получите область перекрытия. Затем проверьте значение каждого пикселя, если он белый, то + 1.

Answer 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).

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

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;
}

Мой код здесь: общественное достояние

Answer 6

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

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

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

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

EDIT:

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

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