Как нарисовать контур группы из нескольких прямоугольников?

Question

Мне нужно нарисовать охватывающий многоугольник группу прямоугольников, расположенных рядом друг с другом.

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

Можете ли вы придумать простой алгоритм/процедуру рисования многоугольника (соединенных прямых путей) вокруг этих объектов.

Вот демонстрация различных потенциальных случаев (A, B, C и т. д.).В примере А я также нарисовал синий многоугольник — путь, который мне нужно нарисовать, очерчивающий группу прямоугольников.

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

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

Спасибо!

Answer 1

ИМХО, это должно быть так.Сделайте список оборовни и посмотреть, если некоторые наложены: это должно быть просто, если прямоугольники выровнены с осью X, Y.Вы просто найдете края, которые имеют вершины на том же x или y, а другие координаты должны быть между.После этого оставшиеся края должны образовывать контур.

Другой способ найти общие края - это нарушать все прямоугольники вдоль каждого оси x и y, где у вас есть вершины.Это должно выглядеть так, как будто вы расти все линии до бесконечности.После этого все общие края будут иметь общие вершины и могут быть устранены.

Answer 2

У вас есть две строки и три разных y-ценности.Скажем так y0 это самое главное, y2 это нижний конец, и y1 отмечает середину между обоими рядами.
Каждая строка имеет максимальное и минимальное значение x, скажем, верхняя строка начинается с x0_min к x0_max, а нижняя строка из x2_min к x2_max.Учитывая эти значения, вы просто рисуете вокруг этой вещи:

(x0_min,y0)->
(x0_max,y0)->
(x0_max,y1)->
(x2_max,y1)->
(x2_max,y2)->
(x2_min,y2)->
(x2_min,y1)->
(x0_min,y1)->
(x0_min,y0)