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

Question

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

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

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

我的搜索结果：

以下是一些链接：

• 多边形偏移策略调查
• 多边形偏移，问题
• 缓冲多边形数据

Answer 1

在我看来，你想要的是：

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

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

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

Answer 2

在 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 %20指南.pdf

Answer 3

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

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

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

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

(a) 案例 1：

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

如果你将其除以 1，你会得到这个：

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 和 4 重叠..如果你看到这个，你会删除这个点以及其间的所有点。

(b) 情况 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

如果你将其扩展为 2，你会得到这样的结果：

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

要解决这个问题，对于每一段线，你必须检查它是否与后面的线段重叠。

(c) 情况 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

消耗 1。这是情况 1 的更一般情况。

(d) 情况 4

与情况 3 相同，但消耗 2。

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

为了执行第 4 种情况，您保留一堆顶点。当您发现与后一行重叠的线时，您将其压入，当您获得后一行时，将其弹出。 ——就像你在凸包中所做的那样。

Answer 4

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

1. 进行三角测量，它不必是delaunay -任何三角测量都可以。

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

3. 使用修改后的Weiler-Atherton 裁剪算法

Answer 5

非常感谢 Angus Johnson 提供的 Clipper 库。
在 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;
    }

Answer 6

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

poly += 2; // buffer polygon by 2

Answer 7

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

Answer 8

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

1. 在每个角找到中向量和中角。 中向量是由角的边缘定义的两个单位向量的算术平均值。 中角是由边缘定义的角度的一半。

2. 如果您需要将多边形扩展（或收缩）每条边的 d 量； 您应该向外（向内）移动 d/sin(midAngle) 以获得新的角点。

3. 对所有角重复此操作

*** 小心你的方向。 使用定义角的三个点进行逆时针测试； 找出哪条路是出去或进来的。

Answer 9

要膨胀多边形，可以实现“通过计算缠绕数进行多边形偏移”一文中的算法。

算法步骤如下：

1. 将输入多边形的每一条边移到外侧，然后将移出的边与输入多边形凸顶点的圆弧和输入多边形凹顶点的两条线段连接起来，构造外偏移曲线。

一个例子。 这里，输入多边形是蓝色虚线，左侧是红色虚线 - 移动边缘，右侧是红色虚线 - 在连续自相交曲线中连接它们之后：

2. 该曲线将平面划分为多个连接的组件，其中一个必须计算每个组件的缠绕数，然后使用正绕数：

这篇文章证明，与竞争对手相比，该算法非常快，同时也很强大。

为了避免实现缠绕数计算，可以将自相交偏移曲线传递给 OpenGL 实用程序库 (GLU) tessellator 并激活设置 GLU_TESS_BOUNDARY_ONLY=GL_TRUE （跳过三角测量）和 GLU_TESS_WINDING_RULE=GLU_TESS_WINDING_POSITIVE （输出正值的边界）绕组数分量）。

Answer 10

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

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

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

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

Answer 11

这是此处中解释的算法的 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) / 2);

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

    return newPoints;
}

Answer 12

感谢您对本主题的帮助，如果有人感兴趣，这里是 C++ 代码。 测试了一下，它的工作原理。 如果你给offset = -1.5，它将缩小多边形。

    typedef struct {
        double x;
        double y;
    } Point2D;
    
    double Hypot(double x, double y)
    {
        return std::sqrt(x * x + y * y);
    }
    
    Point2D NormalizeVector(const Point2D& p)
    {
        double h = Hypot(p.x, p.y);
        if (h < 0.0001)
            return Point2D({ 0.0, 0.0 });
    
        double inverseHypot = 1 / h;
        return Point2D({ (double)p.x * inverseHypot, (double)p.y * inverseHypot });
    }
    
    void offsetPolygon(std::vector<Point2D>& polyCoords, std::vector<Point2D>& newPolyCoords, double offset, int outer_ccw)
    {
        if (offset == 0.0 || polyCoords.size() < 3)
            return;
    
        Point2D vnn, vpn, bisn;
        double vnX, vnY, vpX, vpY;
        double nnnX, nnnY;
        double npnX, npnY;
        double bisX, bisY, bisLen;
    
        unsigned int nVerts = polyCoords.size() - 1;
    
        for (unsigned int curr = 0; curr < polyCoords.size(); curr++)
        {
            int prev = (curr + nVerts - 1) % nVerts;
            int next = (curr + 1) % nVerts;
    
            vnX = polyCoords[next].x - polyCoords[curr].x;
            vnY = polyCoords[next].y - polyCoords[curr].y;
            vnn = NormalizeVector({ vnX, vnY });
            nnnX = vnn.y;
            nnnY = -vnn.x;
    
            vpX = polyCoords[curr].x - polyCoords[prev].x;
            vpY = polyCoords[curr].y - polyCoords[prev].y;
            vpn = NormalizeVector({ vpX, vpY });
            npnX = vpn.y * outer_ccw;
            npnY = -vpn.x * outer_ccw;
    
            bisX = (nnnX + npnX) * outer_ccw;
            bisY = (nnnY + npnY) * outer_ccw;
    
            bisn = NormalizeVector({ bisX, bisY });
            bisLen = offset / std::sqrt((1 + nnnX * npnX + nnnY * npnY) / 2);
    
            newPolyCoords.push_back({ polyCoords[curr].x + bisLen * bisn.x, polyCoords[curr].y + bisLen * bisn.y });
        }
    }

Answer 13

2022 年 8 月：
Clipper2 现已正式发布，它取代了 Clipper（又名 Clipper1）。

---

我想我可以简单提一下我自己的多边形裁剪和偏移库 - <强>快船。

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

可以使用四种样式之一执行多边形偏移（或 连接类型) - 斜接、方形、斜角和圆形。





注意：在 JoinType.Miter 中，顶点 A 处的内角比 B 处的内角更锐，并且 A 处的斜接偏移量将超过指定的斜接限制 2。

Answer 14

您要查找的多边形在计算几何中称为向内/向外偏移多边形，它与直骨架。

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

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

正如其他评论中指出的那样，也取决于您计划“膨胀/收缩”多边形的程度您最终可能会获得不同的输出连接。

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

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

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

Answer 15

对于这些类型的事情，我通常使用 JTS。 出于演示目的，我创建了这个使用 jsFiddle 。 com/bjornharrtell/jsts" rel="noreferrer">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;
}

结果如下所示：

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