Используйте алгоритм строчной линии, используя тот факт, что прямолинейный многоугольник определяется его вершинами.
Представляет вершины вместе с прямоугольником, которому они принадлежат, то есть что-то вроде (x, y, #rect). К этому набору точек добавьте те точки, которые являются результатом пересечений всех ребер. Эти новые точки имеют вид (x, y, final), поскольку мы уже знаем, что они принадлежат результирующему набору точек.
Сейчас:
- отсортировать все точки по их x-значению
- использовать линию развертки, начиная с первой x-координаты; для каждой новой точки:
- если это «начальная точка», добавьте ее во временный набор
T. Отметьте его как «окончательный», если это точка из прямоугольника A и между y-координатами из точек из прямоугольника B в T (или наоборот).
- если это «конечная точка», удалите ее и соответствующую ей начальную точку из T.
После этого все точки, помеченные как «окончательные», обозначают вершины результирующего многоугольника.
Пусть N - общее количество баллов. Далее, предполагая, что проверка того, должны ли мы отмечать точку как «конечную», занимает время O (log (n)) путем поиска T, весь этот алгоритм находится в O (N * log (N)).
Обратите внимание, что задача нахождения всех пересечений может быть включена в вышеупомянутый алгоритм, поскольку нахождение всех пересечений эффективно само по себе является алгоритмом линии развертки. Также обратите внимание, что результирующий набор точек может содержать более одного многоугольника, что затрудняет восстановление многоугольников решения из «конечных» вершин.