c++ - C++ 凸包 jarvis March 算法实现中的错误？

问题描述

我为 C++ 凸包算法编写了一个实现，这应该是微不足道的。我下面的代码遵循文书工作中的公式/方法。我使用称为“贾维斯进行曲”的方法。

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

在对相同点的输入向量进行混洗后：

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

您可能认为该错误与“最后一个”凸包线有关。但它有些不同，在这里可以观察到：

编码：

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;
};

最后，我没有看到：这段代码中的具体错误在哪里？

标签： c++algorithmconvex-hull

更正 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++ - C++ 凸包 jarvis March 算法实现中的错误？

问题描述

解决方案

推荐阅读