Ошибка в реализации C ++ выпуклой оболочки алгоритма Джарвиса Марша?

Question

Я написал реализацию алгоритма выпуклой оболочки С ++, которая должна была быть тривиальной.Мой код ниже следует формулам / подходу от документов .Я использую метод под названием «Джарвис марш».

Он отлично работает для 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;
};

В конце я не вижу: где конкретная ошибка вэтот код?

Answer 1

Исправьте тестовый код 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 если тебе интересно.

Answer 2

Первый наблюдатель за тем, как вы выбираете между q и i.Предположим, у вас есть эта настройка:

Вы хотите выбрать i вместо q, если (i-p)^(q-p) < 0.Но вместо этого вы поворачиваете направо.Это легко увидеть, если выбрать 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 вместо с самым маленьким.

Но все это не имеет значения.Алгоритм работает отлично. Вы можете найти его здесь .Он дает правильный ответ для вашего перемешанного массива.