c - 在C中有效地对点数组进行排序？

Question

我需要以一种特殊的方式对一个点数组（一个点是一个具有两种float类型的结构 - 一种 forx和一种 for ）进行排序。y

这些点必须进行排序，因此当它们被遍历时，它们会形成一个锯齿形图案，从最左上点开始，移动到最右上点，然后向下到最左边的第二个点，到最右边的第二个点，依此类推。

我需要这个能够将任意多边形转换为三角带阵列，然后我可以使用 GLes 绘制。通过使用指针（即传递和重新排列指向点结构的指针）或直接复制和移动结构中的数据，对这些点进行排序的最有效方法是什么？

score 3 · Accepted Answer

我将 qsort() 与自定义 compare() 函数一起使用，正如@stefan 指出的那样，按 y 降序排序，然后为 x 交替（最大/最小）。

score 2 · Accepted Answer

我强烈建议您使用Delaunay Triangulation。OpenCV（它在 C 中可用）有一个很好的实现。

score 1 · Accepted Answer

我认为你没有给出明确的命令。例如，如果这些点看起来像这样，它们应该以什么顺序连接：

score 1 · Accepted Answer

您似乎向我们展示了您的原始问题的一个已经简化的版本，相信您正走在通往解决方案的正确道路上。我可能错了，但看起来不像你。

看来（根据您的其他问题判断）您最终正在寻找triangulation。而且，很可能是一个或多个多边形的三角剖分（而不是一组独立的点）。如果是这样，我建议你看看一些基本的三角测量算法，比如基于单调分解的算法。您在此处提出的问题实际上看起来像是 [可能被误导的] 尝试做类似于单调分解的事情。

score 0 · Accepted Answer

我建议直接从结构中移动数据。

点结构的大小只有 8 到 16 个字节（如果 float 为 8 个字节，则为 16 个字节）。如果您通过指针对数组进行排序，您将复制几乎相同数量的数据（或者如果浮点数是 4 字节，并且在 64 位系统上为 8 字节指针，则复制相同数量的数据）。

如果结构很大，我建议通过指针进行排序。

score 0 · Accepted Answer

您似乎正在尝试重新发明某种单调的多边形链。一些多边形三角测量方法在wiki和这里有代码链接的简短描述

score 0 · Accepted Answer

您应该首先找到点的中值（中间值）（基于水平值）。这会将点集分成左右两部分。接下来根据垂直值对 2 个集合进行排序。然后，您可以从每个集合的顶部进行迭代：从左侧集合中获取顶部元素，然后从右侧获取顶部元素......等等。

为了找到中位数，有一个基于快速排序的简短算法。但比快速排序更快。只需在中位数所在的部分递归（不像快速排序那样在两者上都递归）。

您应该能够以相反的方式进行操作：首先按垂直值排序，然后按水平拆分（当您有奇数点时，这可能会更好）。

7 回答 7