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

Question

Я ищу алгоритм, который определит, полностью ли новый прямоугольник покрыт набором существующих прямоугольников.Другой способ задать вопрос: существует ли новый прямоугольник полностью с областью, покрытой существующими прямоугольниками?

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

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

Изменить - из комментария, опубликованного ОП:

Прямоугольники выровнены по оси X / Y

Answer 1

Если прямоугольники выровнены, это просто:

Допустим, у вас есть прямоугольник A0 и вы хотите узнать, полностью ли он покрыт (B1, B2, B3 ...) = B

A := (A0)
while P := pop B
  for R in A
    if P fully covers R:
      remove R from A
    else if P and R does overlap:
      remove R from A
      break R in subrentangles S := (S1, S2, S3,...) following the intersections \
                                                     with P edges
      push S into A
if A is empty:
   say B covers A0
else:
   say B does not fully cover A0

Answer 2

Если все прямоугольники имеют одинаковый угол;тогда следующее может быть более эффективным и простым в программировании:

Определите для каждой координаты y, какие прямоугольники покрывают эту координату y (вы должны делать это только для координат y, в которых изменяется покрытие;верхний или нижний предел прямоугольника).Как только вы это знаете, решите задачу для каждой такой координаты y (т.е. проверьте, все ли значения x покрыты прямоугольниками, которые «активны» для этой координаты Y).

Редактировать: я думаю, что это сложность O (n ^ 2 log (n) ^ 2), так как два вида - это все тяжелая работа, которую вы должны сделать

Answer 3

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

Answer 4

вот мой код, как вы просили:

первый метод «вычитает» (возвращает непокрытые части) из 2 прямоугольников.

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

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

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

public static List<Rectangle> SubtractRectangles(Rectangle baseRect, Rectangle splitterRect)
    {
        List<Rectangle> newRectaglesList = new List<Rectangle>();

        Rectangle intersection = Rectangle.Intersect(baseRect, splitterRect);
        if (!intersection.IsEmpty)
        {
            Rectangle topRect = new Rectangle(baseRect.Left, baseRect.Top, baseRect.Width, (intersection.Top - baseRect.Top));
            Rectangle bottomRect = new Rectangle(baseRect.Left, intersection.Bottom, baseRect.Width, (baseRect.Bottom - intersection.Bottom));

            if ((topRect != intersection) && (topRect.Height != 0))
            {
                newRectaglesList.Add(topRect);
            }

            if ((bottomRect != intersection) && (bottomRect.Height != 0))
            {
                newRectaglesList.Add(bottomRect);
            }
        }
        else
        {
            newRectaglesList.Add(baseRect);
        }

        return newRectaglesList;
    }

    public static List<Rectangle> SubtractRectangles(Rectangle baseRect, List<Rectangle> splitterRectList)
    {
        List<Rectangle> fragmentsList = new List<Rectangle>();
        fragmentsList.Add(baseRect);

        foreach (Rectangle splitter in splitterRectList)
        {
            List<Rectangle> toAddList = new List<Rectangle>();

            foreach (Rectangle fragment in fragmentsList)
            {
                List<Rectangle> newFragmentsList = SubtractRectangles(fragment, splitter);
                toAddList.AddRange(newFragmentsList);
            }

            if (toAddList.Count != 0)
            {
                fragmentsList.Clear();
                fragmentsList.AddRange(toAddList);
            }
        }

        return fragmentsList;
    }

Answer 5

Попробуйте это

Исходный прямоугольник: X0, Y0, ширина, высота

// В основном сравниваем края

if ((((X0> = xi) && (X0 + ширина <= Xi)) && ((Y0> = Yi) && (Y0 + высота <= Yi)) { // рассмотреть прямоугольник } еще { // сбросить } </p>

Answer 6

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

, если есть пересечение, отбросить его (пересекаемая часть) и добавить непокрытые сегменты в массив прямоугольников

* 1004.* затем, ищите пересечение между новыми сегментами и другими существующими (все еще непроверенными) прямоугольниками.

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

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

, если в массиве еще есть несколько прямоугольников, перекрытие не является полным, так как остаются еще некоторые части.

надеюсь, это поможет

Я могу попытаться найти свой код, если это то, что вы ищете.Я думаю, что в C #

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

Answer 7

Вы можете использовать алгоритм, который используется для расчета площади объединения прямоугольников.Поскольку вы хотите проверить, покрыт ли прямоугольник a прямоугольниками B = {b_1, b_2, ...,}.

Сначала вы вычисляете площадь объединения прямоугольников в B, мы получаем area_1 в качестве значения.

Затем вы вычисляете область объединения прямоугольников в B + {a}, мы получаем area_2 в качестве значения.
Итак, если area_1 == area_2, то вы уверены, что прямоугольник a покрыт прямоугольниками B. В противном случаеответ неверен.

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