一种用于膨胀/缩小（偏移，缓冲）多边形的algorithm
我怎样“膨胀”一个多边形？ 也就是说，我想要做类似的事情：
要求是新的（充气的）多边形的边/点与旧的（原始的）多边形的距离相同（在他们不是的示例图片上，因为那么它将不得不使用弧来填充顶点）现在忘了这个;））。
我正在寻找的math术语实际上是向内/向外的多边形偏离 。 为了指出这一点，给balint +1。 替代的命名是多边形缓冲 。
我的search结果：
这里有一些链接：
- 多边形切断策略综述
- 多边形偏移，PROBLEM
- caching多边形数据
我想我可能会简单地提到我自己的多边形裁剪和抵消库 – 快船 。
虽然Clipper主要是为多边形裁剪操作而devise的，但它也可以进行多边形偏移。 该库是用Delphi，C ++和C＃编写的开源免费软件 。 它具有非常不受限制的Boost许可证，允许它免费使用在免费软件和商业应用程序中。
多边形偏移可以使用三种偏移样式之一来执行 – 平方，圆形和斜angular。
你正在寻找的多边形称为计算几何中的向内/向外偏移多边形 ，它与直骨架密切相关。
这些是复杂多边形的几个偏移多边形：
这是另一个多边形的直骨架：
正如在其他评论中指出的那样，根据您打算“膨胀/放气”多边形的程度，您最终可能会得到不同的输出连通性。
从计算的angular度来看：一旦你有了直骨架，就可以相对容易地构造出偏移多边形。 开放源代码和（免费用于非商业的） CGAL库有一个实现这些结构的包。 看到这个代码示例使用CGAL来计算偏移多边形。
包装手册应该给你一个很好的起点，即使你不打算使用CGAL，如何构build这些结构，并且包含对math定义和属性的论文的引用：
CGAL手册：2D直骨架和多边形偏移
听起来像你想要的是：
- 从顶点开始，沿相邻边逆时针方向。
- 用距离
d的新的平行边缘replace边缘，使其与旧的“左边”相距。 - 重复所有的边缘。
- find新边的交点来获得新的顶点。
- 检测您是否已经成为交叉多项式并决定如何处理它。 可能在交叉点添加一个新的顶点，并删除一些旧的顶点。 我不确定是否有更好的方法来检测这种情况，而不仅仅是比较每一对不相邻的边，看它们的交点是否位于两对顶点之间。
生成的多边形位于离顶点“足够远”的旧多边形所需的距离处。 在一个顶点附近，与旧的多边形距离为d的点集合，正如你所说的那样，不是一个多边形，所以所要求的规定是不能满足的。
我不知道这个algorithm是否有一个名字，在networking上的例子代码，或恶魔的优化，但我想它描述了你想要的。
这是一个替代解决scheme，看看你是否更喜欢这个。
-
做一个三angular测量 ，它不一定是delaunay – 任何三angular测量都可以。
-
膨胀每个三angular形 – 这应该是微不足道的。 如果按照逆时针顺序存储三angular形，只需将线移动到右侧并进行交叉。
-
使用修改的Weiler-Atherton剪裁algorithm合并它们
在GIS世界中，这个任务使用负面缓冲： 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
我从来没有使用Clipper （由Angus Johnson开发），但对于这些types的东西，我通常使用JTS 。 为了演示目的，我创build了这个使用JSTS （JTS的JavaScript端口）的jsFiddle 。 您只需要将坐标转换为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; }
结果是这样的：
附加信息 ：我通常使用这种types的充气/放气（为了我的目的而稍作修改），以便在地图上绘制的多边形（使用Leaflet或Google地图）上设置具有半径的边界。 你只需要将（lat，lng）对转换成JSTS坐标，其他的都是一样的。 例：
每条线都应该将飞机分割成“内”和“外”。 你可以使用通常的内部产品方法find这个。
将所有线向外移动一段距离。
考虑所有的邻居线对（线，而不是线段），find交集。 这是新的顶点。
通过删除任何相交的部分来清理新的顶点。 – 我们在这里有几个案例
（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种情况，你要保留一堆顶点。当你find与后一行重叠的行时，你推动它，当你得到后一行时popup它。 – 就像你在凸包里做的一样。
我写了一些博客post，试图通过直观的骨架algorithm来实现这种情况（通过偏移量进行多边形展开/缩小）。 当时我有两个博客。 阅读我遇到的一些问题可能会有所帮助：
问候，
马克斯
非常感谢安格斯·约翰逊为他的剪辑库。 有很好的代码示例在剪辑器主页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; }
同样在这里： http : //roombuilder.blogspot.com/2008/09/breakthrough-external-straight-skeleton.html
基于@ JoshO'Brian的build议， R语言中的rGeos包似乎实现了这个algorithm。 请参阅rGeos::gBuffer 。
另一个select是使用boost :: polygon – 这个文档有点缺乏，但是你应该发现这个方法resize和bloat ，并且重载了+=操作符，这实际上实现了缓冲。 因此，举例来说，通过某个值增加一个多边形（或一组多边形）的大小可以像下面这样简单：
poly += 2; // buffer polygon by 2
