algorithm - 一种用于膨胀/放气（偏移、缓冲）多边形的算法

Question

我将如何“膨胀”多边形？也就是说，我想做类似的事情：

替代文字

要求是新的（膨胀的）多边形的边缘/点与旧的（原始）多边形的距离相同（在示例图片上它们不是，因为那时它必须使用弧来膨胀顶点，但是让我们暂时忘记这一点；））。

我正在寻找的数学术语实际上是向内/向外多边形偏移。+1 balint 指出这一点。另一种命名是多边形缓冲。

我的搜索结果：

以下是一些链接：

score 151 · Accepted Answer

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

虽然Clipper主要是为多边形裁剪操作而设计的，但它也可以进行多边形偏移。该库是用Delphi、C++ 和 C#编写的开源免费软件。它有一个非常不受限制的Boost许可证，允许它免费用于免费软件和商业应用程序。

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

多边形偏移样式

score 43 · Accepted Answer

您正在寻找的多边形在计算几何中称为向内/向外偏移多边形，它与直骨架密切相关。

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

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

正如其他评论中所指出的那样，根据您计划“膨胀/缩小”多边形的程度，您最终可以得到不同的输出连接性。

从计算的角度来看：一旦你有了直骨架，就应该能够相对容易地构造偏移多边形。开源和（非商业免费）CGAL库有一个实现这些结构的包。请参阅此代码示例以使用 CGAL 计算偏移多边形。

即使您不打算使用 CGAL ，包手册也应该为您提供如何构建这些结构的良好起点，并包含对具有数学定义和属性的论文的引用：

CGAL 手册：2D 直骨架和多边形偏移

score 16 · Accepted Answer

对于这些类型的东西，我通常使用JTS。出于演示目的，我创建了这个使用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;
}

结果是这样的：

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

score 11 · Accepted Answer

在我看来，你想要的是：

从一个顶点开始，沿相邻边逆时针面对。
将边缘替换为新的平行边缘，该边缘放置在距离d旧边缘“左侧”的距离处。
对所有边缘重复。
找到新边的交点以获得新的顶点。
检测您是否已成为交叉多边形并决定如何处理它。可能在交叉点添加一个新顶点并删除一些旧顶点。我不确定是否有更好的方法来检测这一点，而不仅仅是比较每对非相邻边以查看它们的交点是否位于两对顶点之间。

生成的多边形位于距顶点“足够远”的旧多边形的所需距离处。正如您所说，在顶点附近，与旧多边形相距一定距离的点集d不是多边形，因此无法满足所述要求。

我不知道这个算法是否有名称、网络上的示例代码或可怕的优化，但我认为它描述了你想要的。

score 6 · Accepted Answer

在 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

score 5 · Accepted Answer

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

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

考虑所有一对相邻线（线，而不是线段），找到交点。这些是新的顶点。

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

(a) 案例一：

 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

与 case3 相同，但增加了两个。

实际上，如果你能处理案例 4。所有其他情况只是它的特殊情况，有一些线或顶点重叠。

要执行案例 4，您保留一堆顶点。当您发现与后一行重叠的行时推送，当您获得后一行时弹出它。- 就像你在凸包中所做的一样。

score 5 · Accepted Answer

这是一个替代解决方案，看看你是否更喜欢这个。

做一个三角测量，它不必是 delaunay - 任何三角测量都可以。
膨胀每个三角形——这应该是微不足道的。如果您按逆时针顺序存储三角形，只需将线移动到右侧并进行交叉。
使用修改后的Weiler-Atherton 裁剪算法合并它们

score 5 · Accepted Answer

非常感谢 Angus Johnson 的 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;
    }

score 2 · Accepted Answer

另一种选择是使用boost::polygon - 文档有些欠缺，但您应该发现方法resizeandbloat以及重载的+=运算符，它们实际上实现了缓冲。因此，例如将多边形（或一组多边形）的大小增加某个值可以很简单：

poly += 2; // buffer polygon by 2

score 1 · Accepted Answer

根据@JoshO'Brian 的建议，rGeos该语言中的包似乎R实现了该算法。见rGeos::gBuffer。

score 0 · Accepted Answer

有几个可以使用的库（也可用于 3D 数据集）。

人们还可以找到这些库的相应出版物，以更详细地了解算法。

最后一个具有最少的依赖关系，并且是独立的，可以读取 .obj 文件。

最好的祝愿，斯蒂芬

score 0 · Accepted Answer

我使用简单的几何：向量和/或三角

在每个角找到中间向量和中间角。中间向量是由角的边缘定义的两个单位向量的算术平均值。中角是边缘定义的角度的一半。
如果您需要将多边形扩展（或收缩）每条边的 d 量；您应该以 d/sin(midAngle) 的量向外 (in) 获得新的角点。
对所有角落重复此操作

*** 小心你的方向。使用定义角的三个点进行 CounterClockWise 测试；找出出或入的路。

algorithm - 一种用于膨胀/放气（偏移、缓冲）多边形的算法

12 回答 12

Related

Reference