首页 文章

用于膨胀/收缩（抵消，缓冲）多边形的算法

提问于
浏览 次
180

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

alt text

要求是新的（膨胀的）多边形的边/点都与旧的（原始）多边形处于相同的恒定距离（在示例图片上它们不是，因为那时它必须使用弧来填充顶点，但是让我们暂时忘掉它;）） .

我正在寻找的数学术语实际上是 inward/outward polygon offseting . 1指向balint指出这一点 . 替代命名是 polygon buffering .

Results of my search:

以下是一些链接：

algorithm geometry polygon computational-geometry buffering

12 回答

  • 8

    我想我可能会简单地提一下我自己 polygon clipping and offsetting library - Clipper .

    虽然Clipper主要是为多边形裁剪操作而设计的，但它也会进行多边形偏移 . 该库是 open source freeware ，写在 Delphi, C++ and C# 中 . 它具有非常无阻碍的许可证，允许它免费用于免费软件和商业应用程序 .

    可以使用三种偏移样式中的一种执行多边形偏移 - 方形，圆形和斜接 .

    Polygon offsetting styles

    回复于
  • 5

    您正在寻找的多边形在计算几何中称为 inward/outward offset polygon ，它与straight skeleton密切相关 .

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

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

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

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

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

    CGAL manual: 2D Straight Skeleton and Polygon Offsetting

    回复于
  • 127

    听起来像你想要的是：

    • 从顶点开始，沿相邻边缘逆时针方向 .

    • 用一条新的平行边缘替换边缘，该边缘位于距旧"left"的"left"处 .

    • 对所有边重复 .

    • 找到新边的交点以获取新顶点 .

    • 检测是否've become a crossed polynomial and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'我不确定是否有更好的方法来检测这个，而不仅仅是比较每对非相邻边缘，看它们的交点是否位于两对顶点之间 .

    生成的多边形位于距顶点的旧多边形"far enough"所需的距离处 . 在顶点附近，与旧多边形相距距离 d 的点集合，如您所说，不是多边形，因此无法满足所述要求 .

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

    回复于
  • 37

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

    结果是这样的：

    enter image description here

    附加信息：我通常使用这种类型的充气/放气（为我的目的稍微修改）来设置在 Map 上绘制的多边形上的半径边界（使用Leaflet或Google Map ） . 您只需将（lat，lng）对转换为JSTS坐标，其他所有内容都相同 . 例：

    enter image description here

    回复于
  • 1

    每条线应将平面分成“内部”和“轮廓”;你可以使用通常的内积方法找到它 .

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

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

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

    （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，你要保留一堆顶点..当你找到与后一行重叠的行时你推，当你得到后一行时弹出它 . - 就像你在凸壳中做的那样 .

    回复于
  • 0

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

    • 做一个triangulation，它不必是delaunay - 任何三角测量都可以 .

    • 给每个三角形充气 - 这应该是微不足道的 . 如果以逆时针顺序存储三角形，只需将线条移动到右侧并进行交叉 .

    • 使用修改后的Weiler-Atherton clipping algorithm合并它们

    回复于
  • 7

    在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

    回复于
  • 3

    非常感谢Angus Johnson的快船库 . 在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;
    }
    回复于
  • 0

    根据@JoshO'Brian的建议， R 语言中的 rGeos 包实现了这种算法 . 见 rGeos::gBuffer .

    回复于
  • 1

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

    poly += 2; // buffer polygon by 2
    回复于
  • 5

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

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

    最后一个具有最少的依赖项并且是自包含的并且可以读入.obj文件 .

    祝福，斯蒂芬

    回复于
  • 5

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

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

    • 如果需要根据每条边的d量扩展（或收缩）多边形;你应该以d / sin（midAngle）的数量出去（in）以获得新的角点 .

    • 对所有角落重复此操作

    ***小心你的方向 . 使用定义角落的三个点进行CounterClockWise测试;找出哪个出路或出路 .

    回复于

相关问题