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

Question

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

Для таких вещей я обычно использую 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;
}

Результат примерно такой:

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

Answer 4

Звучит так, как ты хочешь:

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

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

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

Answer 5

В мире ГИС для этой задачи используется отрицательная буферизация: 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

Answer 6

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

1. Выполните триангуляцию , это не должно быть делоне - любая триангуляция подойдет.

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

3. Объедините их, используя модифицированный Алгоритм отсечения Вейлера-Атертона

Answer 7

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

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

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

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

(а) Дело 1:

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

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

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

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

(б) дело 2

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

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

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

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

(с) кейс 3

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

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

(d) дело 4

То же, что и case3, но расход на два.

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

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

Answer 8

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

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        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<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        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;
    }

Answer 9

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

poly += 2; // buffer polygon by 2

Answer 10

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