一种用于膨胀/缩小(偏移,缓冲)多边形的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,看看你是否更喜欢这个。

  1. 做一个三angular测量 ,它不一定是delaunay – 任何三angular测量都可以。

  2. 膨胀每个三angular形 – 这应该是微不足道的。 如果按照逆时针顺序存储三angular形,只需将线移动到右侧并进行交叉。

  3. 使用修改的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来实现这种情况(通过偏移量进行多边形展开/缩小)。 当时我有两个博客。 阅读我遇到的一些问题可能会有所帮助:

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

问候,

马克斯

非常感谢安格斯·约翰逊为他的剪辑库。 有很好的代码示例在剪辑器主页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 – 这个文档有点缺乏,但是你应该发现这个方法resizebloat ,并且重载了+=操作符,这实际上实现了缓冲。 因此,举例来说,通过某个值增加一个多边形(或一组多边形)的大小可以像下面这样简单:

 poly += 2; // buffer polygon by 2