c - 如何按顶点处的特定值(或其他距离度量)对一堆多边形/多面体进行排序

Question

我正在开发一个项目，该项目将使用大型数据集(2D 和 3D)，我将把它们转换成三角形或四面体，以便渲染它们。

我还将对这些 tris/tet 进行计算。每次计算使用哪些 tris/tet 取决于其顶点的最大值和最小值。

所以我需要按照其最大值(value)顶点的顺序对 tris/tets 进行排序。

--

我尝试过快速排序和二进制插入排序。到目前为止，快速排序提供了最快的解决方案，但由于数据集的大小，它仍然相当慢。

在首先创建 tris/tets 时，我正在考虑桶/映射排序；一个存储桶，用于存储遇到的每个最大值(value)的顶点，添加指向所有具有该值作为其最大值(value)顶点的值的三角形的指针。

这种方法在时间上应该是线性的，但显然需要更多的内存。这不是问题，但我选择的编程语言是 c。而且我并不完全确定我将如何编写这样的东西。

所以我问你的问题是，你如何以一种可以迭代的方式获取三角形/四边形，从三角形中，其 3 个顶点中具有最大值的顶点是整个数据集，一直到具有最小最大顶点值的三角形？ :)

Answer 1

你不能将它们存储在 binary search tree 中吗？当你生成它们时？这将使它们保持有序且易于搜索(插入和查找都为O(log(n)))