J'ai besoin de trier un tableau de points (un point est une structure avec deux types Types - un pour Les points doivent être triés alors quand ils sont traversés, ils forment un motif de zig-zag à partir du point le plus haut de gauche , se déplaçant vers le point J'ai besoin de cela pour pouvoir convertir des polygones arbitraires vers des tableaux de bande triangulaire que je peux ensuite dessiner à l'aide de gants. Quel serait le moyen le plus efficace de trier ces points en utilisant des pointeurs (c.-à-d. Passer et réorganiser les pointeurs sur les structures de points) ou en copiant et en déplaçant les données dans les structures directement? x et un pour y ) d'une manière spéciale.
7 Réponses :
J'utiliserais qsort () avec une fonction de comparaison personnalisée () que comme @stefan a noté, trie des décroissants par Y alors alternes (max / min) pour x.
Si on se soucierait d'un "vrai zig-zag", alterner par Max / min serait faux puisque la position dans la liste importe ;-)
@Dan: Comment cela fonctionnerait-il exactement? Comment la fonction de comparaison voudrait-elle savoir quelle alternative s'applique?
Évidemment, on ne pourrait pas / ne pouvait pas le faire dans la fonction de comparaison. Tri par Y et décider par la suite de gauche / droite.
@Gareth - je devrais aller laids à ce sujet - utilisez un (osez-moi le dire?) Variable globale pour garder une trace de la gauche ou de la droite. Daniel a un très bon exemple d'exemple qui ferait ma solution moins que souhaitable
Je vous recommande vivement d'utiliser Triangulation de Delaunay . OpenCV (il est disponible en C) a une belle mise en œuvre. < / p>
Le problème avec des algorithmes complexes comme celui-ci est l'efficacité. J'ai besoin de quelque chose de rapide qui peut travailler avec des formes simples (rien de plus de 10 points). La mise en œuvre la plus simple de cet algorithme que j'ai trouvé était composée de plus de 16 000 lignes de code source.
Bonne suggestion, mais cela ne résout pas le problème total de l'OP (elle veut un dépouillement ainsi que la triangulation).
@Garethrees La question de l'OP est plutôt incertaine, cette solution est vraiment liée à la question et m'a rendu heureux. Je suis reconnaissant pour cette réponse! :-)
Non. Delaunay Triangulation serait une surenvérement sévère dans une situation lorsque l'ensemble de points d'origine a déjà certaines propriétés pratiques et agréables. (C'est juste que l'OP semble avoir du mal à formuler ces propriétés). De plus, je soupçonne que le problème initial (que l'OP se cache de nous) est une triangulation polygone pas un point de triangulation. Delaunay ne va pas beaucoup aider si c'est le cas. L'OP semble avoir besoin de décomposition monotone suivie de la triangulation classique.
Je ne pense pas que vous ayez donné un ordre bien défini. Par exemple, à quel ordre les points doivent-ils être connectés si elles ressemblent à ceci:
@Tina Brooks: la photo que vous avez postée ne correspond pas à la photo demandée par Daniel
@Tinabrooks sur la photo que vous avez fournie, deux des points sont mélangés. Les trois premiers points du haut doivent devenir progressivement plus éloignés à droite.
Je recommanderais directement de déplacer des données des structures.
La taille de la structure ponctuelle est de seulement 8 à 16 octets (16Bytes si le flotteur est de 8.tes). Si vous triez la matrice via des pointeurs, vous copiez presque la même quantité de données (ou même quantité de données si le flotteur est de 4bytes et un pointeur de 8bytes sur 64 bits).
Je recommanderais de trier via le pointeur si la structure est grande.
Vous semblez nous présenter une version déjà réduite de votre problème d'origine, estimant que vous êtes sur le chemin droit de la solution. Je pourrais avoir tort, mais ça ne ressemble pas à toi.
Il semble (à en juger par vos autres questions) que vous recherchez finalement une triangulation . Et, tout à fait éventuellement, une triangulation de polygone ou polygones (par opposition à un ensemble de points indépendants). Si tel est le cas, je vous suggère de jeter un coup d'œil à certains algorithmes de triangulation de base, comme celui basé sur la décomposition monotone. Le problème que vous présentez ici ressemble vraiment à une tentative [éventuellement erronée] de faire quelque chose de similaire à la décomposition monotone.
Vous devez d'abord trouver la médiane (valeur moyenne) des points (basée sur les valeurs horizontales). Cela divisera l'ensemble des points en gauche et à droite. Suivant Triez les 2 séries basées sur la valeur verticale. Vous pouvez alors simplement itérer depuis le haut de chaque ensemble: prenez l'élément supérieur de gauche, puis élément supérieur de la droite .. et ainsi de suite.
Pour trouver la médiane, il existe un court algorithme basé sur une trace rapide. Mais plus rapide que rapide. Je viens de recueillir sur la partie où la médiane est (pas à la fois à la fois en tri rapide).
Vous devriez être capable de le faire dans l'inverse: tout d'abord par la valeur verticale, puis divisé par l'horizontale (peut-être que c'est mieux lorsque vous avez un nombre impair de points).
N'est-ce pas la même chose que le tri décroissant de Y puis décider de la commande de nœuds identique?
Pouvez-vous clarifier votre terme "haut à droite"? Voulez-vous dire "le plus nord-est", "le plus élevé des points les plus à droite", ou "le plus à droite des points les plus élevés"? (Le diagramme semble exclure le second de ceux-ci, mais soyons approfondis.)
Les points sont donc fixés dans l'espace et vous devez décider des bords entre points?
En outre, un modèle de zig-zag est-il garanti? Dans votre exemple, supposons que le deuxième point (directement connecté à
Démarrer ) manque?Pourquoi ne pas utiliser un convertisseur existant?
@JaCob alors commence alors à être connecté au point de droite le plus proche. C'est Moreso de former des triangles et non de zig-zags.
Pourquoi n'utilisez-vous pas simplement Delaunay Triangulation ?
@Tina Brooks: La déclaration du problème n'a aucun sens. Points de connexion en 1st Lef le plus -> 1ère à droite -> 2e à gauche, etc. L'ordre ne produit généralement pas de zigzag. Si vous avez des garanties supplémentaires sur vos points, vous devez les énoncer. Sans garanties supplémentaires, le problème, encore une fois, n'a aucun sens.