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

Question

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

algorithmgeometrypolygoncomputational-geometrybuffering

242

我该如何“膨胀”一个多边形？也就是说，我想要做类似于这样的操作：

alt text

要求新的（膨胀的）多边形的边缘/顶点与旧的（原始的）多边形保持相同的常量距离（在示例图片上它们不是，因为这样就必须使用弧线来膨胀顶点，但现在先忘记这个 ;) ）。

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

我的搜索结果：

以下是一些链接：

- Igor Brejc

22

这绝非一个简单的问题：如果通货紧缩/通货膨胀很小，就不会发生什么严重的事情，但是在某个时刻，顶点将会消失。可能之前已经有人做过了，因此我建议：使用别人的算法，不要自己构建。 - Martijn

1

实际上，如果你的多边形一开始就是凹的（就像上面的例子），你必须决定在天真算法想要创建一个自相交的“多边形”时应该发生什么... - AakashM

是的，多边形的凹部分是主要问题，这也是复杂性所在。我仍然认为计算何时必须消除某个特定顶点不应该是什么大问题。主要问题是需要哪种渐近复杂度。 - Igor Brejc

1

你好，这也是我的问题，只不过我需要在三维中完成。除了论文https://arxiv.org/pdf/0805.0022.pdf中描述的三维多面体直骨架方法之外，是否有其他替代方案？ - stephanmg

这些的另一个名称是平行曲线，用于偏移轮廓/轮廓线：https://en.wikipedia.org/wiki/Parallel_curve - Dwayne Robinson

点击这个答案查看JavaScript参考。 - undefined

15个回答

48

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

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

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

如其他评论所指出的那样，根据你计划“膨胀/收缩”多边形的程度，输出的连通性可能会有所不同。

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

即使您不打算使用CGAL，package manual也应该为您提供构建这些结构的良好起点，并包含有关数学定义和属性的论文引用： CGAL manual: 2D Straight Skeleton and Polygon Offsetting

- balint.miklos

16

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

结果大致如下所示：

结果类似于这个样子：

其他信息：我通常使用这种膨胀/缩小（有些修改以适应我的目的），为在地图上绘制的多边形设置半径边界（使用Leaflet或Google Maps）。您只需将（纬度，经度）对转换为JSTS坐标，其余部分都是相同的。示例：

- Marko Letic

12

听起来您想要的是：

从一个顶点开始，沿一个相邻的边逆时针走。
将该边替换为一条新的平行边，距旧边向“左”方向距离为 d 。
对所有边重复上述步骤。
查找新边缘交点以获取新顶点。
检测是否成为交叉多边形并决定如何处理。可能在交点处添加新顶点并丢弃一些旧顶点。我不确定是否有比仅比较每对非相邻边来查看它们的交点是否位于两对顶点之间更好的检测方法。

所得到的多边形距离旧多边形要求的距离“足够远”，远离顶点。在接近顶点的地方，与旧多边形距离为 d 的点集合，正如您所说，不是多边形，因此无法满足所述要求。

我不知道这个算法是否有名称、网络上的示例代码或者有没有更加巧妙的优化方式，但我认为这描述了您想要的内容。

- Steve Jessop

7

在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

- stryeko

5

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

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

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

通过删除任何相交的部分来清理新的顶点——我们有几种情况：

（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

如果您将其乘以二，就会得到这个结果：

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

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

(c) 情况3

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

扩展1。这是第一种情况的更普遍情况。

(d) 第4种情况

与第3种情况相同，但是需要扩展两个。

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

要处理第4种情况，您需要保留一个顶点堆栈。当您发现某些线与后面的线重叠时，请将其推入堆栈中；当您到达后面的线时，请将其弹出 - 就像在凸包中所做的那样。

- J-16 SDiZ

你知道这个的伪代码算法吗？ - EmptyData

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;
    }

- PainElemental

5

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

进行三角剖分，不一定要是Delaunay-任何三角剖分都可以。
膨胀每个三角形-这应该很简单。如果你按逆时针顺序存储三角形，只需将线移动到右侧并进行交集。
使用修改后的Weiler-Atherton剪切算法合并它们

- J-16 SDiZ

你如何精确地填充三角形？你的输出是否取决于三角剖分？使用这种方法，你能处理缩小多边形的情况吗？ - balint.miklos

你确定这种方法对于多边形膨胀真的有效吗？当多边形的凹部膨胀到需要消除一些顶点时会发生什么？问题在于：当你观察多边形膨胀后三角形的变化时，三角形并没有膨胀，而是被扭曲了。 - Igor Brejc

1

Igor：Weiler-Atherton 切割算法可以正确处理“必须消除一些顶点”的情况； - J-16 SDiZ

@balint：膨胀三角形很简单：如果您按照正常顺序存储顶点，则右侧始终为“外部”。只需将这些线段视为线条，向外移动它们，并找到交互点-它们就是新的顶点。对于三角剖分本身，经过再次思考，Delaunay三角剖分可能会产生更好的结果。 - J-16 SDiZ

注意：如果你从头开始实现所有东西，这种方法比我提出的另一种方法更复杂。然而，如果你有一个好的计算几何库，(1)和(3)都是标准算法，应该很容易获得。 - J-16 SDiZ

5

我认为这种方法很容易得出糟糕的结果。即使是一个简单的例子，如使用对角线进行四边形三角剖分。对于两个放大的三角形，你会得到：http://img200.imageshack.us/img200/2640/counterm.png ，它们的并集不是你想要的。我看不出这种方法有什么用处。 - balint.miklos

2

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

poly += 2; // buffer polygon by 2

- Paul R

我不明白如何使用boost::polygon，因为它只支持整数坐标？假设我有一个一般的（浮点坐标）多边形，我想要扩展它 - 我该怎么办？ - David Doria

@DavidDoria：这取决于您需要的坐标分辨率/精度和动态范围，但您可以使用32位或64位整数，并配以适当的缩放因子。顺便说一句，我曾经（无意中）在使用boost::polygon时使用了浮点坐标，它似乎可以正常工作，但可能不是100％健壮的（文档警告不要这样做！）。 - Paul R

我可以接受“它大部分时间都能工作”：）。我尝试了这个：http://ideone.com/XbZeBf，但它无法编译 - 有什么想法吗？ - David Doria

我没有看到明显的错误，但在我的情况下，我使用了直角坐标系的特殊化（polygon_90），所以我不知道是否有所不同。虽然我已经有几年没有再尝试过这个了。 - Paul R

好的 - 或许最好遵循文档并考虑使用固定点方法（即整数坐标和隐式缩放因子）？ - Paul R

显示剩余5条评论

1

根据@JoshO'Brian的建议，看起来R语言中的rGeos包实现了这个算法。请参见rGeos::gBuffer。

- Carl Witthoft

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Angus Johnson · Accepted Answer

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

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

虽然Clipper主要用于多边形裁剪操作，但它也可以进行多边形偏移。该库是用Delphi、C++和C#编写的开源免费软件。它采用了非常自由的Boost许可证，可以在免费软件和商业应用中免费使用。

多边形偏移可以使用四种样式（或连接类型）之一进行，包括尖角、方角、斜角和圆角。注意：在尖角连接类型中，顶点A的内角比顶点B的内角更锐，因此在A处的尖角偏移将超过指定的尖角限制2。