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

Question

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

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

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

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

Вот некоторые ссылки:

• A Survey of Polygon Offseting Strategies
• Polygon offset, PROBLEM
• Buffering Polygon Data

Answer 1

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

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

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

Answer 2

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

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

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

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

(а) Случай 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.

(д) случай 4

же, как Вопрос 3, но расходуют от два.

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

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

Answer 3

Звуки мне нравится то, что вы хотите:

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

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

CGAL manual: 2D Straight Skeleton and Polygon Offsetting

Answer 6

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

1. http://max-on-graphics.blogspot.com/2008/06/straight-skeleton-madness-plea-for-help.html

С уважением,

Макс

Answer 7

Также здесь: http://roombuilder.blogspot.com/2008/09/breakthrough-external-straight-skeleton.html

Answer 8

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

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

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

Answer 9

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

Answer 10

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

poly += 2; // buffer polygon by 2 

Answer 11

Я никогда не использовал Clipper (разработанный Angus Johnson), но для этих типов вещей, которые я обычно использование 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, а все остальное - то же самое. Пример:

Answer 12

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