How to sort a bunch of polygons/polyhedra by a specific value at their vertices (or some other distance measure)

Question

I am working on a project which will be using large datasets (both 2D and 3D) which I will be turning into triangles, or tetrahedra, in order to render them.

I will also be performing calculations on these tris/tets. Which tris/tets to use for each calculation depend on the greatest and smallest values of their vertices.

So I need to sort the tris/tets in order of their greatest valued vertex.

--

I have tried quicksort, and binary insertion sort. Quicksort so far offers the quickest solution but it is still quite slow due to the size of the data sets.

I was thinking along the lines of a bucket/map sort when creating the tris/tets in the first place; a bucket for each of the greatest valued vertices encountered, adding pointers to the triangles who all have that value as the value of their greatest valued vertex.

This approach should be linear in time, but requires more memory obviously. This is not an issue, but my programming language of choice is c. And I'm not entirely sure how I would go about coding such a thing up.

So my question to you is, how would you go about getting the triangles/tets in such a way that you could iterate through them, from the triangle whos vertex with the greatest value of its 3 vertices is the greatest valued vertex in the entire data set, all the way down to the triangle with the the smallest greatest vertex value? :)

Answer 1

Can't you just store them in a binary search tree as you generate them? That would keep them in order and easily searchable (O(log(n)) for both insertion and lookup)

Answer 2

You could use priority queue based on a heap data structure. This should also get you O(log(n)) for insertion and extraction.