从 XY 坐标排序点

计算科学 计算几何 几何学
2021-12-24 08:12:10

我有一系列从规则网格中提取的点,它们的 X/Y 坐标。以前的算法(我无法修改!)输出这些坐标的列表,但是这些点的顺序在此问题的范围内是随机的,由以下 python 样式表示法表示:

[ [X_O,Y_O], [X_M, Y_M], [X_D, Y_D], ... ]

其中 XY 是每个点的 X 和 Y 坐标。我现在正尝试使用以下逻辑对它们“排序”(在网格可视化上从 A 点到 R 点):

[ [X_A,Y_A], [X_B, Y_B], [X_C, Y_C], ... ]

点排序目标

最终目标是在 Z 网格上绘制具有实际值的轮廓。我尝试了一种“hacky”方式,只识别每个点的邻居并订购尚未处理的邻居,但它不够可靠,因为我面临许多工件。

是否有我错过的针对该问题设计的算法?我做了一些研究,但我觉得我错过了一些东西。

谢谢!

2个回答

这是经典的轮廓跟踪问题,通常使用 Pavlidis 描述的算法来解决

Pavlidis:图形和图像处理算法。第 129-165 页,施普林格,1982 年

Gamera 框架中的contour_pavlidis提供了一个现成的python 函数。这个实现的 C++ 代码可以在 github上找到,它受 GNU GPL 许可的约束。

我认为 C++ 中最简单的方法是制作一个元组向量。 std::vector< std::tuple< int, int, double>> 该向量包含 X 和 Y 坐标以及 Z 值作为元组。之后,您可以简单地使用sort(). 如果将 Z 值存储在元组的第三位,则需要一个额外的函数进行排序。因此,我建议将需要排序的值放在元组的第一位。在这里查看本教程希望这就是你要找的。