Получить контур множества прямоугольников

Question

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

Мне нужна идея о том, как написать такую ​​функцию:

IEnumerable<Point> GetContour( IEnumerable<Rect> rects )

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

Answer 1

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

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

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

Я сделал это совсем недавно (хотя это не ограничивалось речами, и я уже сделал первый проход), и это работало довольно хорошо. Я видел, что он способен рассчитывать маршрут на графике примерно на 30 точек в секунду больше, чем я мог рассчитывать в int, поэтому производительность казалась довольно хорошей, хотя это было в C ++.

Answer 2

Это, кажется, частный случай проблемы вогнутой оболочки . Существует множество алгоритмов для решения противоположных проблем выпуклой оболочки :

• Джарвис Март ( Википедия ) O (n ^ 2)
• Сканирование Грэма ( Википедия ) O (nlogn)

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

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

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