我如何“膨胀”一个多边形?也就是说,我想做一些类似的事情:

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

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

我的搜索结果:

以下是一些链接:

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


当前回答

听起来你想要的是

Starting at a vertex, face anti-clockwise along an adjacent edge. Replace the edge with a new, parallel edge placed at distance d to the "left" of the old one. Repeat for all edges. Find the intersections of the new edges to get the new vertices. Detect if you've become a crossed polygon and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'm not sure whether there's a better way to detect this than just to compare every pair of non-adjacent edges to see if their intersection lies between both pairs of vertices.

生成的多边形位于所需的距离上,与旧多边形距离顶点“足够远”。在一个顶点附近,距离旧多边形d的点的集合,正如你所说,不是一个多边形,所以不能满足所述的要求。

我不知道这个算法是否有名字,网络上的示例代码,或者是一个残酷的优化,但我认为它描述了你想要的东西。

其他回答

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

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

在每个角求中向量和中角。中向量是由边角定义的两个单位向量的算术平均值。中角是边角的一半。 如果你需要扩展(或收缩)你的多边形的数量d从每条边;你应该向外(向内)乘以d/sin(中角)来得到新的角点。 对所有的角重复这个步骤

注意你的方向。使用定义角的三个点进行逆时针测试;找出哪条路是出去,哪条路是进去。

非常感谢安格斯·约翰逊的快船库。 在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;
    }

听起来你想要的是

Starting at a vertex, face anti-clockwise along an adjacent edge. Replace the edge with a new, parallel edge placed at distance d to the "left" of the old one. Repeat for all edges. Find the intersections of the new edges to get the new vertices. Detect if you've become a crossed polygon and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'm not sure whether there's a better way to detect this than just to compare every pair of non-adjacent edges to see if their intersection lies between both pairs of vertices.

生成的多边形位于所需的距离上,与旧多边形距离顶点“足够远”。在一个顶点附近,距离旧多边形d的点的集合,正如你所说,不是一个多边形,所以不能满足所述的要求。

我不知道这个算法是否有名字,网络上的示例代码,或者是一个残酷的优化,但我认为它描述了你想要的东西。

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

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

多边形偏移可以使用三种偏移样式之一-方形,圆形和斜切。

2022年8月: Clipper2现在已经正式发布,它取代了Clipper(又名Clipper1)。