C++ 凸包 jarvis 行进算法实现中的错误？

Question

我为 C++ 凸包算法编写了一个实现，这应该是微不足道的。我的下面代码遵循 the paperwork 中的 formulas/approach。我使用名为 "Jarvis march".

的方法

它在 20000 点时工作正常，在性能方面要低得多，但如果我随机化输入点数组的顺序（使用 std::shuffle），我可以看到有时它会显示错误

打乱相同点的输入向量后：

（绿线是给定黑点计算的凸包）

您可能认为该错误与 "last" 凸包线有关。但它有些不同，在这里可以观察到：

代码：

using namespace std;

vector<Point> m_in;

inline double cross(const Point &a, const Point &b)
{
    return (a.x * b.y) - (b.x * a.y);
}

// conterclockwise test
inline bool CCW(const Point &p, const Point &i, const Point &q)
{
//    auto a = p.x,
//            b = p.y,
//            c = i.x,
//            d = i.y,
//            e = q.x,
//            f = q.y;

// the same:
//    return ((f - b) * (c - a)) > ((d - b) * (e - a));

// the same:
//    Point va { c - a, d - b }; // i - p
//    Point vb { e - a, f - b }; // q - p
//    return cross(va, vb) > 0;

// the same, compact:
    return cross(i - p, q - p) > 0;
}


void Reset(vector<Point> &in)
{
    m_in = move(in);
}

vector<Line> GetLine() const
{
    vector<Line> res;

    Point l = m_in.front();

    for(auto &i : m_in)
    {
        if(l.x < i.x)
        {
            l = i;
        }
    }

    Point p = l;
    for(auto &pi : m_in)
    {
        Point q = pi;
        for(auto &i : m_in)
        {
            if(CCW(p, i, q))
            {
                q = i;
            }
        }

        res.push_back(Line { p, q });
        p = q;
    }

    return res;
}

基于图像：

类型，要清楚：

struct Point
{
    double x, y;

    friend Point operator+(const Point& a, const Point& b);
    friend Point operator-(const Point& a, const Point& b);
    friend bool operator!=(const Point& a, const Point& b);
};

struct Line
{
    Point a;
    Point b;
};

最后没看出来：这段代码具体错误在哪里？

Answer 1

首先观察你如何在q和i之间做出选择。假设你有这样的设置：

如果 (i-p)^(q-p) < 0，您想选择 i 而不是 q。但是你转向右边。如果选择 p = (0,0), q = (1,0), i = (0,1):

就很容易看出

i
|
|
p-----q

然后 (i-p)^(q-p) = (0,1)^(1,0) = 0 - 1 = -1 < 0，应该选择 i 而不是 q。

还要注意，您是从最大 x 而不是最小的点开始的。

但这一切都不重要了。该算法工作正常。 你可以找到它 here。它会为您的随机排列数组生成正确答案。

Answer 2

修正CCW测试代码：

inline bool CCW(const Point &p, const Point &i, const Point &q)
{
    return cross(i - p, q - p) < 0.0;
}

不要手动循环遍历输入数组以找到最低的 X 坐标。使用 std::sort() 按 X 坐标对输入数组进行排序。这并没有破坏论文对方法的描述。

void Reset(vector<Point> &in)
{
    sort(in.begin(), in.end(), [](const Point &a, const Point &b) { return a.x < b.x; });

    m_in = move(in);
}

重写代码，使其使用迭代器（算法描述中令人困惑的行是 q = p + 1，它实际上并未在 OP 的代码中实现）。尝试保留语法的原始方法，因为没有人喜欢在其他地方广泛监督的 C 风格或 C++98 示例。

vector<Line> GetLine() const
{
    vector<Line> res;

    if(m_in.empty())
    {
        return res;
    }

    auto    l = m_in.begin(),
            r = m_in.end() - 1;

    auto p = l;
    do
    {
        auto q = p + 1;
        if(q > r) {
            q = l;
        }

        for(auto i = l; i <= r; i++)
        {
            if(CCW(*p, *i, *q)) {
                q = i;
            }
        }

        res.push_back(Line{*p, *q});
        p = q;
    }
    while(p != l);

    return res;
}

如果您有兴趣，可以在 Github 上找到我的应用程序的完整代码。

C++ 凸包 jarvis 行进算法实现中的错误？

Bug in C++ convex hull jarvis march algorithm implementation?

c++

algorithm

convex-hull