寻边和连接算法

Question

我的背景和问题的根源来自生物医学研究，所以我不是一个熟练的程序员。我有一种情况，我想平滑 2D 网格的外表面。拉普拉斯平滑看起来是满足我需求的不错选择，但我注意到它需要我为网格编写连接算法。例如，我想要以下坐标

像这样连接

().

现在，我认识到连接这些点的另一种方式可以是这样的

有人对 A）如何为所述点开发连接算法有一些建议吗？ B）我可以包含什么样的权重/参数来促进算法像第一个示例中那样建立连接，而不是第二个示例。我的一个想法是尝试最大化面积，但不确定那会是什么样子。

Answer 1

最简单的解决方案是使用凸边界多边形。

找到这一点的最简单方法是实现礼品包装算法（https://en.wikipedia.org/wiki/Gift_wrapping_algorithm）

这是一些 C++ 代码

void cWrap::wrap()
{
    vWrap.clear();

    // find leftmost point
    cxy leftmost = vPoints[0];
    for (cxy &p : vPoints)
        if (p.x < leftmost.x)
            leftmost = p;
    vWrap.push_back(leftmost);

    // wrap around points
    cxy prev = cxy(leftmost.x, leftmost.y - 1);
    cxy last = leftmost;
    for (;;)
    {
        // loop over points
        cxy next = vPoints[0];
        double amin = 10;
        for (cxy &maybe : vPoints)
        {

            double a =
                2 * 3.142 - cxy::clockwise(
                                prev,
                                last,
                                maybe);

            if (a < 0.01)
                continue;

            // save point with least clockwise turn
            if (a < amin)
            {
                amin = a;
                next = maybe;
            }
        }
        // check if back at start
        if (next == leftmost)
            return;

        // save point
        vWrap.push_back(next);
        prev = last;
        last = next;
    }
}

完整的应用程序代码位于 https://github.com/JamesBremner/GiftWrap