Points de tri dans l’ordre dans le sens horaire ?

Question

Étant donné un tableau de x,y des points, comment puis-je trier les points de ce tableau dans le sens horaire (autour de leur moyenne générale center point)? Mon objectif est de passer les points d'une ligne-création de la fonction de quelque chose à la recherche plutôt "solide", comme convexe que possible, sans les lignes d'intersection.

Pour ce que ça vaut, je suis en utilisant Lua, mais tout pseudocode serait appréciée. Merci beaucoup pour toute aide!

Mise à jour: Pour la référence, c'est le code Lua basé sur Ciamej excellente réponse (ignorer mon "app" (préfixe):

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then return false
    end

    local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
    local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
    return d1 > d2
end

function appGetCenterPointOfPoints(points)
    local pointsSum = {x = 0, y = 0}
    for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
    return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end

Answer 1

Calculez d'abord le point central. Ensuite trier les points utilisant n'importe quel algorithme de tri que vous voulez, mais utilisation spécifique de la routine de comparaison pour déterminer si un point est moins que les autres.

Vous pouvez vérifier si un point (un) est à la gauche ou à la droite de l'autre (b) par rapport au centre, par ce simple calcul:

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

si le résultat est zéro, alors qu'ils sont sur la même ligne à partir du centre, si il est positif ou négatif, alors il est sur un côté ou de l'autre, de sorte que le point de précéder les autres. En l'utilisant, vous pouvez construire une relation de comparer les points et déterminer l'ordre dans lequel ils doivent apparaître dans le tableau trié. Mais vous devez définir où se trouve le début de cette ordonnance, je veux dire ce que l'angle de départ (par exemple le positif de la moitié de l'axe des x).

Le code de la fonction de comparaison peut ressembler à ceci:

bool less(point a, point b)
{
    if (a.x - center.x >= 0 && b.x - center.x < 0)
        return true;
    if (a.x - center.x < 0 && b.x - center.x >= 0)
        return false;
    if (a.x - center.x == 0 && b.x - center.x == 0) {
        if (a.y - center.y >= 0 || b.y - center.y >= 0)
            return a.y > b.y;
        return b.y > a.y;
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;

    // points a and b are on the same line from the center
    // check which point is closer to the center
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 > d2;
}

Ce sera l'ordre des points dans le sens horaire à partir de 12 heures. Des Points sur la même "heure" sera commandée à partir de celles qui sont plus loin du centre.

Si vous utilisez les types integer (qui ne sont pas vraiment présents dans Lua) vous devez assurer que det, d1 et d2 sont les variables d'un type qui sera en mesure de tenir le résultat de calculs exécutés.

Si vous voulez obtenir quelque chose de solide, comme convexe que possible, alors je suppose que vous êtes à la recherche pour une enveloppe Convexe. Vous pouvez calculer à l'aide de la Graham Scan. Dans cet algorithme, vous avez également de trier les points des aiguilles d'une montre (ou dans le sens antihoraire) à partir d'un point de pivot. Puis vous répétez simple boucle étapes à chaque fois de vérifier si vous tournez à gauche ou à droite de l'ajout de nouveaux points de l'enveloppe convexe, cette vérification est basée sur les produits, tout comme dans le rapport ci-dessus de la fonction.

Edit:

Ajouter un de plus si l'instruction if (a.y - center.y >= 0 || b.y - center.y >=0) pour s'assurer que les points x=0 et négatifs y sont triés à partir de celles qui sont plus loin du centre. Si vous n'avez pas de soins sur l'ordre des points sur la même 'heure', vous pouvez omettre cette instruction if et toujours revenir a.y > b.y.

Corrigé de la première si les déclarations avec l'ajout d' -center.x et -center.y.

Ajout de la seconde si l'instruction (a.x - center.x < 0 && b.x - center.x >= 0). C'était une omission évidente qu'il manquait. Si les déclarations peuvent être réorganisé maintenant, parce que certains contrôles sont redondantes. Par exemple, si la première condition dans la première si l'énoncé est faux, alors la première condition de la seconde si doit être vrai. J'ai décidé, cependant, de laisser le code tel qu'il est par souci de simplicité. C'est tout à fait possible que le compilateur d'optimiser le code et produisent le même résultat, de toute façon.

Answer 2

Ce que vous demandez est un système de coordonnées polaires. La Conversion de Cartésiennes en coordonnées polaires se fait facilement dans n'importe quelle langue. Les formules peuvent être trouvés dans cette section.

Je ne sais pas Lua, mais cette page semble offrir des extraits de code pour cette conversion.

Après la conversion en coordonnées polaires, en quelque sorte, par l'angle theta.

Answer 3

Une alternative intéressante approche à votre problème serait de trouver le minimal approximatif pour le Problème du voyageur de commerce (TSP), c'est à dire. l'itinéraire le plus court reliant tous vos points. Si votre formulaire de points d'une forme convexe, il devrait être la bonne solution, sinon, il doit toujours bon (un "solide" de la forme peut être définie comme un seul qui a un faible périmètre/aire de ratio, qui est ce que nous sommes en optimisant ici).

Vous pouvez utiliser la mise en œuvre d'un optimiseur pour le TSP, dont je suis assez sûr que vous pouvez trouver une tonne dans la langue de votre choix.