Объединение (логическое объединение) прямоугольных областей с целочисленной точностью

Question

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

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

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

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

Answer 1

Я понятия не имею, удовлетворяет ли это вашим требованиям к производительности, но оно должно работать:

1. Начните с пустого набора прямоугольников.
2. Добавьте каждый прямоугольник в набор.Если прямоугольник перекрывает существующий прямоугольник, разбейте прямоугольники на столько прямоугольников, сколько необходимо, чтобы ни один прямоугольник не перекрывал другой.
3. Добавьте четыре стороны каждого непересекающегося прямоугольника к набору линий.
4. Удалите все строки, которые не являются уникальными.

Результирующий набор содержит все линии, составляющие контур.

---