按簇索引 2d 点的算法

Algorithm to index 2d points by clusters

我有一个问题要解决,我在网上搜索后没有找到任何可用的算法,我自己也没有能够想出一个令人满意的解决方案。

问题定义:

我得到一组 N 多点,由它们的 X 和 Y 坐标定义,我应该给每个点一个介于 0 和 N 之间的唯一索引。不过有几个条件:

1)如果两点之间的几何距离很小,那么它们的指数之间的差异也应该很小。

2) 如果A点的X坐标比B点高,那么它的索引值也应该更高。

3) 如果A点的Y坐标比B点高,那么它的索引值也应该更高。

其他:

由于数据相当小(50 ~ 100 点),算法不需要特别快或特别高效。

我需要这个算法来创建一个只有 2 个按钮来浏览数据集的用户界面。使用一个按钮,用户选择下一个点,使用另一个按钮,用户选择上一个点。

欢迎所有建议。提前致谢。

示例图片:

这是可能的结果示例。请注意如何不满足所有点的条件(因为那是不可能的),但索引如何仍然很好地分布在集群中。

Morton curve aka Z-order (Wikipedia) 对点进行排序。

然后分配号码。