2

我确实有 4 个校准点的 x 和 y 坐标列表。这些没有特定的顺序,也没有在任何轴上对齐(它们来自带有轻微旋转和失真的真实校准图片),但列表具有相同的索引并且不能以每个列表升序/降序的方式排序。它们也不包含整数值,而是浮点数。我现在正试图找到给定点的四个相邻点。

例如,搜索点 [150,150] 的邻居将返回 [140,140]、[140,160]、[160,140]、[160,160](除了它们实际上更像 [139.581239,138.28812])。

目前,我必须查看每个点的所有校准点以进行检查。大约有 500 个校准点。

在此过程的后期,我需要知道 1600x1400 网格内随机点的 4 个邻居数百万次。因此,尽可能快地找到这些点以避免几天甚至几周的计算时间是至关重要的。

我的第一种方法是检查每个点的约 500 个校准点,以检查并查看它们与检查点的相对位置(x_calib > x 和 y_calib > y 将位于该点的顶部右侧区域)并计算他们与它的距离。然后每个区域中的最近点(左上、右上、左下、右下)将是各自的相邻点。这似乎根本没有效率,而且需要很多时间。

第二种方法是为每个 1600x1400 点创建一个彩虹表并保存各自的邻居(准确地说,将索引保存在坐标列表中)。稍后,该过程将在位置 [x,y,0]、[x,y,1]、[x,y,2] 和 [x,y,3] 处检查此彩虹表,以获得 4 个索引4个邻居点。虽然计算彩虹表需要一些时间(大约 200 万个点需要大约 20 分钟),但这种方法加快了后面的处理速度。不幸的是,这种方法使得调试过程的后续步骤变得困难,因为在其余步骤开始之前需要这么多时间。

我仍然认为应该有优化的空间,我将不胜感激任何建议或帮助加快整个事情。我已经阅读了有关 kd-tree 的内容,但并没有完全看到在这里使用它的可能性。我希望这种未排序(和不可排序)的点列表有一种方法,它比彩虹表更有效 - 或者至少在创建表时更快。

提前致谢!

4

0 回答 0