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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для таких вещей я обычно использую 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, а все остальное тоже самое. Пример:

Похоже, что вы хотите, это:

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

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

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

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

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

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

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

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

(а) Случай 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 вы сохраняете стек вершин. Вы нажимаете, когда обнаруживаете, что линии перекрываются с последней, и выталкиваете его, когда получаете последнюю строку. - так же, как то, что вы делаете в выпуклой оболочке.

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

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

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

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

Большое спасибо Ангусу Джонсону за его библиотеку клиперов. Есть хорошие примеры кода для выполнения отсечения на домашней странице отсечения по адресу 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;
    }

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

poly += 2; // buffer polygon by 2

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

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

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

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

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

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

Я использую простую геометрию: векторы и / или тригонометрию

1. В каждом углу найдите средний вектор и средний угол. Средний вектор - среднее арифметическое двух единичных векторов, определенных краями угла. Средний угол - это половина угла, определенного краями.

2. Если вам нужно расширить (или сжать) свой полигон на величину d от каждого ребра; Вы должны выйти (в) на величину d / sin (midAngle), чтобы получить новую угловую точку.

3. Повторите это для всех углов

*** Будьте осторожны в вашем направлении. Сделайте CounterClockWise Test, используя три точки, определяющие угол; выяснить, какой выход, или в.