Comment trier un groupe de polygones/polyèdres par une valeur spécifique à leurs sommets (ou une autre mesure de distance)

Question

Je travaille sur un projet qui utilisera de grands ensembles de données (2D et 3D) que je vais transformer en triangles, ou tétraèdres, pour les rendre.

Je vais également effectuer des calculs sur ces tris/tets. Les tris/tets à utiliser pour chaque calcul dépendent des plus grandes et des plus petites valeurs de leurs sommets. J'ai donc besoin de trier les tris/tets dans l'ordre de leur plus grand sommet évalué.

-

J'ai essayé quicksort, et le tri par insertion binaire. Quicksort offre la solution la plus rapide jusqu'à présent, mais elle est encore assez lente en raison de la taille des ensembles de données. Je pensais dans le sens d'un tri de seau/carte lors de la création des tris/tets en premier lieu; un seau pour chacun des sommets les plus importants rencontrés, en ajoutant des pointeurs aux triangles qui ont tous cette valeur comme valeur de leur plus grand sommet évalué.

Cette approche devrait être linéaire dans le temps, mais nécessite évidemment plus de mémoire. Ce n'est pas un problème, mais mon langage de programmation est c. Et je ne suis pas tout à fait sûr de savoir comment je pourrais coder une telle chose. Donc ma question est la suivante: comment voulez-vous obtenir les triangles/tets de telle manière que vous puissiez les parcourir, à partir du triangle dont le sommet avec la plus grande valeur de ses 3 sommets est le plus grand sommet évalué? dans tout l'ensemble de données, jusqu'au triangle avec la plus petite valeur de sommet la plus grande? :)

Answer 1

Ne pouvez-vous pas simplement les stocker dans un binary search tree pendant que vous les générez? Cela les garderait dans l'ordre et facilement consultable (O(log(n)) pour l'insertion et la recherche)

Answer 2

Vous pouvez utiliser priority queue basé sur un heap data structure. Cela devrait également vous obtenir O(log(n)) pour l'insertion et l'extraction.