用于膨胀/收缩(抵消,缓冲)多边形的算法

Question

我如何"膨胀"多边形？也就是说,我想做类似的事情:

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

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

我的搜索结果:

以下是一些链接:

• 多边形脱靶策略综述
• 多边形偏移,问题
• 缓冲多边形数据

Answer 1

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

虽然Clipper主要用于多边形裁剪操作,但它也可以进行多边形偏移.该库是用Delphi,C++和C#编写的开源免费软件.它具有非常无阻碍的Boost许可证,允许它免费用于免费软件和商业应用程序.

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

Answer 2

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

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

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

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

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

该包装说明书应该给你如何构建这些结构,即使你不打算使用CGAL一个很好的起点,并含有与数学定义和属性的文件引用:

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

Answer 3

听起来像你想要的是:

• 从顶点开始,沿着相邻边缘逆时针方向.
• 用新的平行边缘替换边缘,该边缘与d旧的"左" 相距一定距离.
• 重复所有边缘.
• 找到新边的交点以获取新顶点.
• 检测您是否已成为交叉多项式并决定如何处理它.可能在交叉点添加一个新的顶点并摆脱一些旧的顶点.我不确定是否有更好的方法来检测这个,而不仅仅是比较每对非相邻边缘,看看它们的交点是否位于两对顶点之间.

得到的多边形位于距离顶点"足够远"的旧多边形所需的距离处.在顶点附近,与d旧多边形相距一定距离的点集,如您所说,不是多边形,因此无法满足所述要求.

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

Answer 4

对于这些类型的东西,我通常使用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地图).您只需将(lat,lng)对转换为JSTS坐标,其他所有内容都相同.例:

Answer 5

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

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

考虑所有相邻线(线,而不是线段),找到交点.这些是新的顶点.

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

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

Answer 6

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

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

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

3. 使用修改的Weiler-Atherton裁剪算法合并它们

Answer 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

Answer 8

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