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

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

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

我的搜索结果:

以下是一些链接:

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


当前回答

这是另一个解决方案,看看你是否更喜欢这个。

做一个三角测量,不一定是delaunay,任何三角测量都可以。 膨胀每个三角形——这应该是微不足道的。如果你以逆时针的顺序存储三角形,只要将线移动到右手边并做交点。 使用改进的Weiler-Atherton裁剪算法合并它们

其他回答

对于这些类型的事情,我通常使用JTS。出于演示目的,我创建了这个使用JSTS (JTS的JavaScript端口)的jsFiddle。你只需要将坐标转换为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;
}

结果是这样的:

附加信息:我通常使用这种类型的膨胀/收缩(为我的目的做了一点修改)在地图上绘制的多边形上设置半径边界(使用传单或谷歌地图)。您只需将(lat,lng)对转换为JSTS坐标,其他一切都是相同的。例子:

这是另一个解决方案,看看你是否更喜欢这个。

做一个三角测量,不一定是delaunay,任何三角测量都可以。 膨胀每个三角形——这应该是微不足道的。如果你以逆时针的顺序存储三角形,只要将线移动到右手边并做交点。 使用改进的Weiler-Atherton裁剪算法合并它们

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

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

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

这是这里解释的算法的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;
}

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