Можно ли создать меньший алгоритм выпуклой оболочки, используя 1 цикл?

Я создал работающую программу для выпуклой оболочки, которая способна рисовать точки и линии, а также все необходимое, чтобы сделать ее визуально привлекательной. Мой вопрос, есть ли способ спроектировать его так, чтобы нужен был только один цикл for? Вместо того, чтобы сделать верхний и нижний корпус? Не могу понять, как я смогу отслеживать, когда верхняя часть корпуса достигает конца/начинается ниже.

void computeConvexHull(QPainter * painter)
{
    int k = 0;
    std::vector<QPointF> vecLinePoints(2*vecPoints.size());

    // Sort points lexicographically
    std::sort(vecPoints.begin(),vecPoints.end(), xyCompare());

    //begin with far left, work our way to lower hull
    // Build upper hull
    for (int i = vecPoints.size()-2, j = k+1; i >= 0; i--)
    {
        while (k >= j && checkPoints(vecLinePoints[k-2], vecLinePoints[k-1], vecPoints[i]) <= 0)
            k--;
        vecLinePoints[k++] = vecPoints[i];
    }

    // Build lower hull
    for (int i = 0; i < vecPoints.size(); ++i)
    {
        while (k >= 2 && checkPoints(vecLinePoints[k-2], vecLinePoints[k-1], vecPoints[i]) <= 0)
            k--;
        vecLinePoints[k++] = vecPoints[i];
    }



    //reduce size of vector
    vecLinePoints.resize(k);

person Psychosupreme    schedule 27.11.2015    source источник
comment
Вы можете использовать один цикл for, но вам все равно понадобятся два массива и настройка контрольных точек. По сути, если перекрестное произведение checkPoints меньше 0, вы помещаете его в один массив, больше 0 вы помещаете его в другой массив, а если оно равно 0, вы помещаете его в оба массива. Примечание. Ваш алгоритм немного странный в том смысле, что он идет справа налево, а затем слева направо, а не меняет знаки (не уверен, что это правильно). Единственный способ избежать верхней и нижней оболочек — использовать другой алгоритм. Я пытался сделать это некоторое время назад и не нашел реальной пользы для одного или двух циклов.   -  person Nuclearman    schedule 01.12.2015


Ответы (1)


Конечно, вы всегда можете сделать и верхнее, и нижнее одновременно... но это пустая трата времени. Существуют более эффективные алгоритмы, чем монотонная цепочка Эндрю; см. Википедию.

Надеюсь это поможет.

person Dúthomhas    schedule 27.11.2015