Алгоритм раздувания / дефляции (смещения, буферизации) полигонов

Как бы я «раздул» многоугольник? То есть, я хочу сделать что-то похожее на это:

alt text

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

Математическим термином для того, что я ищу, является фактическое смещение многоугольника внутрь / наружу . +1 для balint для указания этого. Альтернативное именование – это многоугольная буферизация .

Результаты моего поиска:

Вот несколько ссылок:

  • Обзор страtagsй сопоставления полигонов
  • Смещение многоугольника, ПРОБЛЕМА
  • Буферные данные многоугольника

Я подумал, что могу кратко упомянуть о своей полигоне, отсекающей библиотекуClipper .

Хотя Clipper в первую очередь предназначен для операций обрезки полигонов, он также выполняет многоугольную коррекцию. Библиотека представляет собой бесплатное ПО с открытым исходным кодом, написанное на Delphi, C ++ и C # . Он имеет очень свободную лицензию Boost, позволяющую использовать ее как в бесплатных, так и в коммерческих приложениях бесплатно.

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

Стили многоугольника

Полигон, который вы ищете, называется многоугольником смещения / наружу в вычислительной геометрии и тесно связан с прямым скелетом .

Это несколько смежных полигонов для сложного многоугольника:

И это прямой скелет для другого полигона:

Как указано в других комментариях, также, в зависимости от того, как далеко вы планируете «раздувать / дефлировать» ваш полигон, вы можете получить различные возможности для вывода.

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

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

Руководство CGAL: 2D Скелет с прямым скелетом и многоугольником

Мне кажется, что вы хотите:

  • Начиная с вершины, поверните против часовой стрелки вдоль соседнего края.
  • Замените край новым, параллельным краем, расположенным на расстоянии d до «левого» старого.
  • Повторите для всех ребер.
  • Найдите пересечения новых ребер, чтобы получить новые вершины.
  • Определите, стал ли вы перекрещенным многочленом и решите, что с ним делать. Вероятно, добавьте новую вершину в точку пересечения и избавьтесь от некоторых старых. Я не уверен, есть ли лучший способ обнаружить это, чем просто сравнить каждую пару несмежных ребер, чтобы увидеть, находится ли их пересечение между обеими парами вершин.

Полученный многоугольник лежит на нужном расстоянии от старого многоугольника «достаточно далеко» от вершин. Вблизи вершины множество точек на расстоянии d от старого многоугольника, как вы говорите, не является многоугольником, поэтому требование, как указано, не может быть выполнено.

Я не знаю, имеет ли этот алгоритм имя, пример кода в Интернете или дьявольскую оптимизацию, но я думаю, что он описывает то, что вы хотите.

Я никогда не использовал Clipper (разработанный Ангусом Джонсоном), но для этих типов вещей я обычно использую JTS . Для демонстрационных целей я создал этот jsFiddle, который использует JSTS (порт JavaScript JTS). Вам просто нужно преобразовать координаты в координаты JSTS:

 function vectorCoordinates2JTS (polygon) { var coordinates = []; for (var i = 0; i < polygon.length; i++) { coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y)); } return coordinates; } 

Результат выглядит примерно так:

введите описание изображения здесь

Дополнительная информация : Обычно я использую этот тип раздувания / дефляции (немного измененный для моих целей) для установки границ с радиусом на полигонах, которые нарисованы на карте (с картами Листовки или Google). Вы просто конвертируете (lat, lng) пары в координаты JSTS, а все остальное - то же самое. Пример:

введите описание изображения здесь

Каждая строка должна разделить плоскость на «внутри» и «набросок»; вы можете найти это, используя обычный метод внутреннего продукта.

Переместите все линии наружу на некоторое расстояние.

Рассмотрим все пары соседних строк (линии, а не отрезки), найдите пересечение. Это новая вершина.

Очистите новую вершину, удалив любые пересекающиеся части. – у нас есть несколько случаев здесь

(a) Случай 1:

  0--7 4--3 | | | | | 6--5 | | | 1--------2 

если вы потратите его на один, вы получите следующее:

 0----a----3 | | | | | | | b | | | | | 1---------2 

7 и 4 перекрываются. Если вы видите это, вы удаляете эту точку и все точки между ними.

(b) случай 2

  0--7 4--3 | | | | | 6--5 | | | 1--------2 

если вы потратите его на два, вы получите следующее:

 0----47----3 | || | | || | | || | | 56 | | | | | | | 1----------2 

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

(c) случай 3

  4--3 0--X9 | | | 78 | | | 6--5 | | | 1--------2 

расходуйте на 1. Это более общий случай для случая 1.

(d) случай 4

то же, что и в случае3, но расходуйте на два.

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

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

Вот альтернативное решение, посмотрите, нравится ли вам это лучше.

  1. Сделайте триангуляцию , это не должно быть delaunay – любая триангуляция будет делать.

  2. Надуйте каждый треугольник – это должно быть тривиально. если вы храните треугольник в порядке против часовой стрелки, просто переместите линии вправо и выполните перекресток.

  3. Объедините их с помощью модифицированного алгоритма отсечения Weiler-Atherton

В мире ГИС для этой задачи используется отрицательная буферизация: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

Библиотека JTS должна сделать это за вас. См. Документацию по операции с буфером: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Подробный обзор см. Также в Руководстве для разработчиков: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Большое спасибо Ангусу Джонсону за его библиотеку клиперов. Есть хорошие примеры кода для создания отсечения на главной странице клипера по адресу http://www.angusj.com/delphi/clipper.php#code, но я не видел примера для переноса многоугольника. Поэтому я подумал, что, возможно, это полезно для кого-то, если я отправлю свой код:

  public static List GetOffsetPolygon(List originalPath, double offset) { List resultOffsetPath = new List(); List polygon = new List(); foreach (var point in originalPath) { polygon.Add(new ClipperLib.IntPoint(point.X, point.Y)); } ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset(); co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon); List> solution = new List>(); co.Execute(ref solution, offset); foreach (var offsetPath in solution) { foreach (var offsetPathPoint in offsetPath) { resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y))); } } return resultOffsetPath; } 

Основываясь на совете от @ JoshO’Brian, кажется, что пакет rGeos на языке R реализует этот алгоритм. См. rGeos::gBuffer .

Еще один вариант заключается в использовании boost :: polygon – документации несколько не хватает, но вы должны обнаружить, что методы resize и bloat , а также перегруженный оператор += , который фактически реализует буферизацию. Так, например, увеличение размера многоугольника (или множества полигонов) некоторым значением может быть таким простым, как:

 poly += 2; // buffer polygon by 2 

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

  1. https://github.com/otherlab/openmesh
  2. https://github.com/alecjacobson/nested_cages
  3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

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

Последний имеет наименьшие зависимости и является автономным и может читать в .obj-файлах.

С наилучшими пожеланиями, Стефан

Давайте будем гением компьютера.