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

Question

• Каждый прямоугольник состоит из 4 двойных символов: (x0, y0, x1, y1)

• Ребра параллельны осям X и Y

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

Мне нужно найти область, образованную их перекрытием - всю область на холсте, которую «покрывает» более одного прямоугольника (например, двумя прямоугольниками, это будет пересечение)

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

Answer 1

На первый взгляд кажется, что алгоритм O (n ^ 2) должен быть простым, поскольку мы можем просто проверить все попарные точки. Однако это создало бы проблему двойного счета, поскольку все точки, которые находятся в 3 прямоугольниках, будут подсчитаны 3 раза! После осознания этого алгоритм O (n ^ 2) теперь не выглядит для меня плохо. Если вы можете придумать тривиальный алгоритм O (n ^ 2), пожалуйста, напишите.

Вот алгоритм O (n ^ 2 log ^ 2 n).

Структура данных: Point (p) {x_value, isBegin, isEnd, y_low, y_high, rectid}

[Для каждой точки у нас есть одно значение x_value, два значения y_value и идентификатор прямоугольника, из которого эта точка пришла]

1. С учетом n прямоугольников сначала создайте 2n точек, как указано выше, используя значения прямоугольника x_left и x_right.

2. Создать список точек и отсортировать его по x_value. Это занимает O (n log n) время

3. Начните слева (индекс 0), используйте карту, чтобы поставить, когда вы видите начало, и удалите, когда вы видите конечную точку.

Другими словами:

Map m = new HashMap();  // rectangles overlapping in x-axis
for (Point p in the sorted list) {
    if (p.isBegin()) {
        m.put(p);  // m is keyed off of rectangle id
        if (s.size() >= 2) {
            checkOverlappingRectangles(m.values())
        }
    } else {
        m.remove(p);  // So, this takes O(log n) time
    }
}

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