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

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

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

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

https://i.stack.imgur.com/LqZeh.png

---

您要查找的多边形在计算几何中称为向内/向外偏移多边形，它与 straight skeleton 密切相关。

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

https://i.stack.imgur.com/vCgNf.png

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

https://i.stack.imgur.com/lETWh.png

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

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

package manual 应该为您提供一个很好的起点，让您了解如何构建这些结构，即使您不打算使用 CGAL，并且包含对具有数学定义和属性的论文的引用：

CGAL manual: 2D Straight Skeleton and Polygon Offsetting

---

对于这些类型的东西，我通常使用 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;
}

结果是这样的：

https://i.stack.imgur.com/C7Wf8.png

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

https://i.stack.imgur.com/ryZNC.png

---

在我看来，你想要的是：

从一个顶点开始，沿相邻边逆时针面对。

将边缘替换为新的平行边缘，该边缘位于旧边缘“左侧”距离 d 处。

对所有边缘重复。

找到新边的交点以获得新的顶点。

检测您是否已成为交叉多边形并决定如何处理它。可能在交叉点添加一个新顶点并删除一些旧顶点。我不确定是否有更好的方法来检测这一点，而不仅仅是比较每对非相邻边以查看它们的交点是否位于两对顶点之间。

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

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

---

在 GIS 世界中，有人为此任务使用负缓冲：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

---

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

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

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

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

(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，您保留一堆顶点。当您发现与后一行重叠的行时推送，当您获得后一行时弹出它。 - 就像你在凸包中所做的一样。

---

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

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

---

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

---

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

poly += 2; // buffer polygon by 2

---

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

---

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

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

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

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

最好的祝愿，斯蒂芬

---

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

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

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

---

这是 here 中解释的算法的 C# 实现。它也使用 Unity 数学库和集合包。

public static NativeArray<float2> ExpandPoly(NativeArray<float2> oldPoints, float offset, int outer_ccw = 1)
{
    int num_points = oldPoints.Length;
    NativeArray<float2> newPoints = new NativeArray<float2>(num_points, Allocator.Temp);

    for (int curr = 0; curr < num_points; curr++)
    {
        int prev = (curr + num_points - 1) % num_points;
        int next = (curr + 1) % num_points;

        float2 vn = oldPoints[next] - oldPoints[curr];
        float2 vnn = math.normalize(vn);
        float nnnX = vnn.y;
        float nnnY = -vnn.x;

        float2 vp = oldPoints[curr] - oldPoints[prev];
        float2 vpn = math.normalize(vp);
        float npnX = vpn.y * outer_ccw;
        float npnY = -vpn.x * outer_ccw;

        float bisX = (nnnX + npnX) * outer_ccw;
        float bisY = (nnnY + npnY) * outer_ccw;

        float2 bisn = math.normalize(new float2(bisX, bisY));
        float bislen = offset / math.sqrt(1 + nnnX * npnX + nnnY * npnY);

        newPoints[curr] = new float2(oldPoints[curr].x + bislen * bisn.x, oldPoints[curr].y + bislen * bisn.y);
    }

    return newPoints;
}

---