1
J'ai créé un programme de coque convexe qui est capable de dessiner les points et les lignes et tout ce qui est nécessaire pour le rendre visuellement attrayant. Ma question, est-ce qu'il y a un moyen de la concevoir de sorte qu'une seule boucle soit nécessaire? Au lieu de faire une coque supérieure et inférieure? Je n'arrive pas à comprendre comment je pourrais suivre une fois que la coque supérieure atteint la fin/commence plus bas.Création d'un plus petit algorithme de coque convexe, peut-il être fait avec 1 boucle?
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);
Vous pouvez utiliser une seule boucle for, mais vous avez toujours besoin de deux matrices et d'ajuster les "points de contrôle". Fondamentalement, si le crossproduct, 'checkPoints', est inférieur à' 0' vous le placez dans un tableau, supérieur à '0' vous le placez dans un autre tableau et s'il est égal à' 0', vous le placez dans les deux tableaux. Note: Votre algorithme est un peu étrange car il va de droite à gauche puis de gauche à droite plutôt que de changer les signes (pas sûr que cela soit valide). La seule façon d'éviter les coques supérieure et inférieure est d'utiliser un algorithme différent. J'ai essayé de le faire il y a un certain temps et je n'ai pas trouvé de réel bénéfice pour une boucle ou deux boucles. – Nuclearman