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

Question

Учитывая набор пересекающихся прямоугольников, существует ли стандартный алгоритм для поиска их ограничивающего многоугольника? (Многоугольник, ограничивающий ровно ту же область, что и объединение прямоугольников.) Прямоугольники можно считать, что все ориентированы одинаково, со сторонами вдоль двух ортогональных осей.

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

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

Answer 1

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

Подход линии подвода обычно требует значительных первоначальных инвестиций: внедрение двигателя развертки. Как только это будет сделано, движок может быть немедленно использован для простой реализации любой ориентированной на заданную операцию ввода геометрии, такой как «merge», «and», «or», «diff» и т. Д.

http://en.wikipedia.org/wiki/Boolean_operations_on_polygons

В то же время, реализуя свип-линии двигателя для оси-ориентированной (isothetic) геометрия является довольно тривиальной задачей. Это было бы лучшим подходом в ситуациях, когда вам нужно обрабатывать массивные входы, т. Е. Когда количество прямоугольников относительно велико. Различные подходы, основанные на обходах, упомянутые в других ответах, будут хорошо работать только на относительно небольших входах.

Answer 2

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

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

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

Редактировать Позвольте мне попытаться выразить это более подробно.

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

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

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

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

(5) Повторяйте, пока не вернетесь к конечной точке, с которой вы начали.