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

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个回答

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

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

- user2800464 · Answer 1

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

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

2. 如果您需要将多边形沿每条边扩展（或收缩）d的量，则应该沿着d / sin(midAngle)的量向外（内）走，以获得新的角点。

3. 对于所有角落都要重复此过程。

*** 注意你的方向。使用定义角落的三个点进行逆时针测试，以找出哪个方向是外部或内部。

- Emad · Answer 2

这是一个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;
}

- Csanyi Bence · Answer 3

感谢在这个话题中的帮助，这是C++代码，如果有人感兴趣的话。已经测试过了，它可以正常工作。如果你将偏移量设置为-1.5，它将缩小多边形。

    typedef struct {
        double x;
        double y;
    } Point2D;
    
    double Hypot(double x, double y)
    {
        return std::sqrt(x * x + y * y);
    }
    
    Point2D NormalizeVector(const Point2D& p)
    {
        double h = Hypot(p.x, p.y);
        if (h < 0.0001)
            return Point2D({ 0.0, 0.0 });
    
        double inverseHypot = 1 / h;
        return Point2D({ (double)p.x * inverseHypot, (double)p.y * inverseHypot });
    }
    
    void offsetPolygon(std::vector<Point2D>& polyCoords, std::vector<Point2D>& newPolyCoords, double offset, int outer_ccw)
    {
        if (offset == 0.0 || polyCoords.size() < 3)
            return;
    
        Point2D vnn, vpn, bisn;
        double vnX, vnY, vpX, vpY;
        double nnnX, nnnY;
        double npnX, npnY;
        double bisX, bisY, bisLen;
    
        unsigned int nVerts = polyCoords.size() - 1;
    
        for (unsigned int curr = 0; curr < polyCoords.size(); curr++)
        {
            int prev = (curr + nVerts - 1) % nVerts;
            int next = (curr + 1) % nVerts;
    
            vnX = polyCoords[next].x - polyCoords[curr].x;
            vnY = polyCoords[next].y - polyCoords[curr].y;
            vnn = NormalizeVector({ vnX, vnY });
            nnnX = vnn.y;
            nnnY = -vnn.x;
    
            vpX = polyCoords[curr].x - polyCoords[prev].x;
            vpY = polyCoords[curr].y - polyCoords[prev].y;
            vpn = NormalizeVector({ vpX, vpY });
            npnX = vpn.y * outer_ccw;
            npnY = -vpn.x * outer_ccw;
    
            bisX = (nnnX + npnX) * outer_ccw;
            bisY = (nnnY + npnY) * outer_ccw;
    
            bisn = NormalizeVector({ bisX, bisY });
            bisLen = offset / std::sqrt((1 + nnnX * npnX + nnnY * npnY) / 2);
    
            newPolyCoords.push_back({ polyCoords[curr].x + bisLen * bisn.x, polyCoords[curr].y + bisLen * bisn.y });
        }
    }

- stephanmg · Answer 4

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

用户还可以找到这些库的相应出版物，以更详细地了解算法。

最后一个具有最少的依赖关系，是自包含的，并且可以读取 .obj 文件。

- Fedor · Answer 5

为了扩展一个多边形，可以实现“通过计算绕组数进行多边形偏移”的算法article。

该算法的步骤如下：

通过从输入多边形中取出每条边并将其向外移动来构造外部偏移曲线，然后在输入多边形的凸顶点处连接移动边缘和圆弧，在凹顶点处连接两条线段。

以下是一个示例。这里输入多边形为虚线蓝色，左侧为红色 - 移动边缘，右侧为在连续自相交曲线中连接它们后的结果：

曲线将平面分成许多连通的部分，需要计算每个部分中的绕数，然后取所有绕数为正的连通部分的边界：

本文证明该算法与竞争对手相比非常快速且同时具有鲁棒性。

为了避免实现绕数计算，可以将自交偏移曲线传递给OpenGL实用库（GLU）tessellator并激活设置GLU_TESS_BOUNDARY_ONLY=GL_TRUE（跳过三角剖分）和GLU_TESS_WINDING_RULE=GLU_TESS_WINDING_POSITIVE（输出正绕数组件的边界）。