Я создал работающую программу для выпуклой оболочки, которая способна рисовать точки и линии, а также все необходимое, чтобы сделать ее визуально привлекательной. Мой вопрос, есть ли способ спроектировать его так, чтобы нужен был только один цикл 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);
checkPoints
меньше0
, вы помещаете его в один массив, больше0
вы помещаете его в другой массив, а если оно равно0
, вы помещаете его в оба массива. Примечание. Ваш алгоритм немного странный в том смысле, что он идет справа налево, а затем слева направо, а не меняет знаки (не уверен, что это правильно). Единственный способ избежать верхней и нижней оболочек — использовать другой алгоритм. Я пытался сделать это некоторое время назад и не нашел реальной пользы для одного или двух циклов. - person Nuclearman   schedule 01.12.2015