Создание меньшего алгоритма выпуклой оболочки, это можно сделать за 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);

1

Решение

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

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

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector