Étant donné un tableau de points x, y, comment trier les points de ce tableau dans le sens des aiguilles d'une montre (autour de leur point central moyen global)? Mon objectif est de passer les points à une fonction de création de ligne pour aboutir à quelque chose qui semble plutôt "solide", aussi convexe que possible sans intersection de lignes.
Pour ce que ça vaut, j'utilise Lua, mais n'importe quel pseudocode serait apprécié.
Mise à jour: Pour référence, voici le code Lua basé sur l'excellente réponse de Ciamej (ignorez mon préfixe "app"):
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
ipairs(tbl)qui itère sur les indices et les valeurs de tbl de 1 à #tbl. Donc, pour le calcul de la somme, vous pouvez le faire, ce que la plupart des gens trouvent plus propre:for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y endipairsest nettement plus lent que la boucle for numérique.Réponses:
Commencez par calculer le point central. Triez ensuite les points en utilisant l'algorithme de tri de votre choix, mais utilisez une routine de comparaison spéciale pour déterminer si un point est inférieur à l'autre.
Vous pouvez vérifier si un point (a) est à gauche ou à droite de l'autre (b) par rapport au centre par ce simple calcul:
si le résultat est zéro, alors ils sont sur la même ligne à partir du centre, si c'est positif ou négatif, alors c'est d'un côté ou de l'autre, donc un point précédera l'autre. En l'utilisant, vous pouvez construire une relation inférieure à pour comparer les points et déterminer l'ordre dans lequel ils doivent apparaître dans le tableau trié. Mais vous devez définir où est le début de cet ordre, je veux dire quel angle sera l'angle de départ (par exemple la moitié positive de l'axe des x).
Le code de la fonction de comparaison peut ressembler à ceci:
Cela ordonnera les points dans le sens des aiguilles d'une montre à partir de 12 heures. Les points sur la même «heure» seront commandés à partir de ceux qui sont plus éloignés du centre.
Si vous utilisez des types entiers (qui ne sont pas vraiment présents dans Lua), vous devez vous assurer que les variables det, d1 et d2 sont d'un type qui pourra contenir le résultat des calculs effectués.
Si vous voulez obtenir quelque chose qui a l'air solide, aussi convexe que possible, alors je suppose que vous recherchez une coque convexe . Vous pouvez le calculer à l'aide du Graham Scan . Dans cet algorithme, vous devez également trier les points dans le sens horaire (ou anti-horaire) à partir d'un point de pivot spécial. Ensuite, vous répétez des étapes de boucle simples à chaque fois en vérifiant si vous tournez à gauche ou à droite en ajoutant de nouveaux points à la coque convexe, cette vérification est basée sur un produit croisé, tout comme dans la fonction de comparaison ci-dessus.
Éditer:
Ajout d'une instruction if supplémentaire
if (a.y - center.y >= 0 || b.y - center.y >=0)pour s'assurer que les points qui ont x = 0 et y négatif sont triés en commençant par ceux qui sont plus éloignés du centre. Si vous ne vous souciez pas de l'ordre des points sur la même «heure», vous pouvez omettre cette instruction if et toujours revenira.y > b.y.Correction des premières instructions if avec l'ajout
-center.xet-center.y.Ajout de la deuxième instruction if
(a.x - center.x < 0 && b.x - center.x >= 0). C'était un oubli évident qu'il manquait. Les instructions if pourraient être réorganisées maintenant car certains contrôles sont redondants. Par exemple, si la première condition de la première instruction if est fausse, la première condition de la seconde if doit être vraie. J'ai cependant décidé de laisser le code tel quel par souci de simplicité. Il est fort possible que le compilateur optimise le code et produise de toute façon le même résultat.la source
atan(), pas de racine carrée et même pas de division. Ceci est un bon exemple de pensée infographique. Éliminez tous les cas faciles dès que possible, et même dans les cas difficiles, calculez le moins possible pour connaître la réponse requise.Une approche alternative intéressante à votre problème serait de trouver le minimum approximatif au problème du voyageur de commerce (TSP), c'est-à-dire. l'itinéraire le plus court reliant tous vos points. Si vos points forment une forme convexe, cela devrait être la bonne solution, sinon, cela devrait toujours avoir l'air bien (une forme "solide" peut être définie comme une forme qui a un faible rapport périmètre / surface, ce que nous optimisons ici) .
Vous pouvez utiliser n'importe quelle implémentation d'un optimiseur pour le TSP, dont je suis sûr que vous pouvez en trouver une tonne dans la langue de votre choix.
la source
Ce que vous demandez, c'est un système appelé coordonnées polaires . La conversion des coordonnées cartésiennes en coordonnées polaires se fait facilement dans n'importe quelle langue. Les formules se trouvent dans cette section .
Après la conversion en coordonnées polaires, triez simplement par l'angle, thêta.
la source
Une autre version (retourne true si a vient avant b dans le sens antihoraire):
C'est plus rapide, car le compilateur (testé sur Visual C ++ 2015) ne génère pas de saut pour calculer dax, day, dbx, dby. Voici l'assembly de sortie du compilateur:
Prendre plaisir.
la source
Enfin, vous obtenez des verts triés par Anticlockwize
list.Reverse () .................. Clockwise_order
la source