充气/放气(偏移、缓冲)多边形的算法

我想我可以简单地提一下我自己的 多边形裁剪和偏移库 - Clipper .

同时 Clipper 主要设计用于多边形裁剪操作,也可以进行多边形偏移。图书馆是 开源免费软件 写在 Delphi、C++与C语言 . 它有一个非常没有阻碍的 Boost 许可证允许它在免费软件和商业应用程序中使用。

多边形偏移可以使用三种偏移样式之一执行-方形、圆形和斜接。

你要找的多边形叫做 向内/向外偏移多边形 在计算几何中,它与 straight skeleton .

这些是复杂多边形的多个偏移多边形:

这是另一个多边形的直骨架:

正如其他评论中指出的那样,根据你计划对多边形“充气/放气”的程度,你最终可以得到不同的输出连接。

从计算的角度来看:一旦你有了直骨架,你应该能够相对容易地构造偏移多边形。开源和(非商业免费) CGAL 库有一个实现这些结构的包。见 this code example 使用cgal计算偏移多边形。

这个 package manual 应该给你一个很好的起点,说明如何构建这些结构,即使你不打算使用cgal,并且包含对具有数学定义和属性的论文的参考:

CGAL manual: 2D Straight Skeleton and Polygon Offsetting

我觉得你想要的是:

• 从顶点开始,沿相邻边逆时针朝向。
• 将边缘替换为新的平行边缘,放置在远处 d 在旧的“左边”。
• 对所有边重复此操作。
• 找到新边的交点以获得新顶点。
• 检测您是否已成为一个交叉多项式,并决定如何处理它。可能在交叉点添加一个新顶点,然后去掉一些旧顶点。我不确定是否有更好的方法来检测这一点,而不仅仅是比较每对非相邻边,看看它们的交点是否位于两对顶点之间。

生成的多边形与旧多边形的距离“足够远”,与顶点的距离为所需距离。在一个顶点附近,距离上的一组点 D 正如您所说,来自旧多边形的不是多边形,因此无法满足所述的要求。

我不知道这个算法是否有名字,网页上的示例代码,或者一个疯狂的优化,但是我认为它描述了你想要的东西。

我从不使用 Clipper (由安格斯·约翰逊开发)但是对于这些类型的东西我通常使用 JTS . 为了演示,我创建了这个 jsFiddle 使用的 JSTS (jts的javascript端口)。您只需将需要的坐标转换为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;
}

结果是这样的:

附加信息 :我通常使用这种类型的充气/放气(为我的目的稍微修改一下)来设置地图上绘制的多边形的半径边界(使用传单或谷歌地图)。您只需将(lat,lng)对转换为JST坐标,其他一切都是相同的。例子:

每一行都应该将平面拆分为“内部”和“轮廓”;您可以使用通常的内部积方法找到这一点。

将所有线向外移动一段距离。

考虑所有相邻线对(直线,而不是线段),找到交叉点。这是新的顶点。

通过删除任何相交部分来清理新顶点。--我们这里有几个箱子

(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种情况,需要保留一个顶点堆栈。当你发现行与后一行重叠时,你推它,当你得到后一行时弹出它。--就像你在凸面船体上所做的。

这里有一个替代方案,看看你是否更喜欢这个。

1. 做一个 triangulation 不必是Delaunay——任何三角测量都可以。

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

3. 使用修改后的 Weiler-Atherton clipping algorithm

在地理信息系统的世界中,我们使用负缓冲来完成这项任务: 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

非常感谢安格斯·约翰逊为他的快船图书馆。 在Clipper的主页上,有一些很好的代码示例可以用来进行剪辑。 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;
    }

根据@josho'brian的建议,似乎 rGeos 包中 R 语言实现了这个算法。见 rGeos::gBuffer .

另一个选择是使用 boost::polygon -文档有点欠缺,但是您应该发现方法 resize 和 bloat 以及超载 += 运算符,它实际上实现缓冲。例如,将一个多边形(或一组多边形)的大小增加一个值可以简单到:

poly += 2; // buffer polygon by 2

有几个库可以使用(也可用于三维数据集)。

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

您还可以找到这些库的相应出版物,以便更详细地了解算法。

最后一个依赖性最小,是自包含的,可以读取.obj文件。

最美好的祝福, 斯蒂芬