选择矩阵中距离另一个点30米以内的所有点。

Question

如果你看过我的其他帖子，那么我正在制作一个可以在森林中收集数据并将其放在地图上的机器人，这一点并不奇怪。我们有算法可以检测树干直径和树心，并将它们放在笛卡尔坐标系的平面上。

我们计划使用某些“关键”树木作为自然地标来定位机器人，使用三角测量和三边测量等方法，但是仅使用Matlab编程并保持数据整洁和高效变得困难。 是否有一种对点数组或矩阵进行子集化的技术？比如说我有1000棵树存储在1公里（1000米）之内，是否有一种方法只选择当前位置半径30米范围内的点并仅处理这些点？ 我会使用GIS，但我正在Matlab中进行此操作，而我不知道任何Matlab的GIS插件。

我忘了提到，这段代码正在上线，也就是说它正在机器人上进行实时执行。当地图扩大到几英里时，我不知道是否使用不同的数据结构会有所帮助，或者计算到随机点的每个距离是否就是空间数据库要做的事情。

我考虑将树木数组镜像成两个数组，一个按X排序，另一个按Y排序。然后使用冒泡排序来确定该范围内的30米范围。我对X和Y两个数组都执行相同的操作，然后有一个第三个交叉链接表将选择单个值。但是我不知道那叫什么，如何编程，我相信有人已经这样做了，所以我不想重复发明轮子。 笛卡尔平面
GIS

- Phil Salesses

---

这是什么意思？你不知道它们的含义还是在问其他问题？我已经在问题底部添加了链接。 - Phil Salesses

对不起，我对地理不太熟悉，但是我认为纬度和经度不是笛卡尔坐标系，而且森林有高度...无论如何，我认为封闭散列可能在这里做得很好。 - Potatoswatter

Answer 1

你正在寻找一个空间数据库，例如四叉树或kd树。我找到了两个kd树的实现这里和这里，但没有找到Matlab的任何四叉树实现。

- Justin Peel

Answer 2

计算所有距离并进行扫描的简单解决方案似乎几乎瞬间运行：

lim = 1;
num_trees = 1000;

trees = randn(num_trees,2); %# list of trees as Nx2 matrix
cur = randn(1,2); %# current point as 1x2 vector
dists = hypot(trees(:,1) - cur(1), trees(:,2) - cur(2)); %# distance from all trees to current point
nearby = tree_ary((dists <= lim),:); %# find the nearby trees, pull them from the original matrix

在一台1.2 GHz的机器上，我可以在小于0.4秒的时间内处理1百万（1 MTree？）棵树。

您是直接在机器人上运行Matlab代码吗？或者您使用了Real-Time Workshop之类的东西吗？如果需要将其转换为C语言，您可以使用sqr（trees [i] .x-pos.x）+sqr（trees [i] .y-pos.y）替换hypot，并用<lim^2替换限制检查。如果您真的只需要处理1KTree，那么实现更复杂的数据结构可能不值得。

- mtrw

---

我忘了提到，这段代码将要上线，也就是说它将在机器人上进行实时执行。当地图扩大到几英里时，我不知道使用不同的数据结构是否有帮助，或者计算每个距离是否仍然是它正在做的事情。我考虑复制两个数组，一个按X排序，另一个按Y排序。然后使用冒泡排序来查找高和低范围。我对X和Y两个数组都做同样的操作，然后有第三个交叉链接表来选择单个值。但我不知道那被称为什么，如何编程，我相信已经有人做过了。 - Phil Salesses

如果你要比较lim^2，就不应该对平方和取平方根。 - Jonas

@Jonas - 我同意。Matlab代码使用了 hypot，它会进行平方根运算，而建议的C语言代码使用了sqr(x) + sqr(y)，需要与sqr(lim)进行比较。 - mtrw

Answer 3

使用CART2POL函数可以将笛卡尔坐标转换为极坐标，然后选择一定半径内的点将变得简单明了。

[THETA,RHO] = cart2pol(X-X0,Y-Y0);
selected =  RHO < 30;

X0和Y0是当前位置的坐标。

- yuk

---

我以你的解决方案为灵感，对我的解决方案进行了加速。谢谢！ - mtrw

Answer 4

我猜树木在森林中分布大致均匀。如果是这样，只需将30x30（或15x15）网格块用作哈希键插入封闭哈希表中。查找所有与搜索圆相交的块的键，并检查从该键开始的所有哈希条目，直到其中一个被标记为其“桶”中的最后一个。

0---------10---------20---------30--------40---------50----- address # line
(0,0)     (0,30)     (0,60)     (30,0)    (30,30)    (30,60) hash key values

(1,3) (10,15) (3,46) (24,9.) (23,65.) (15,55.) tree coordinates + "." flag

例如，要获取(0,0)…(30,30)中的树木，请将(0,0)映射到地址0，并读取条目(1,3)、(10,15)，拒绝(3,46)因为它超出了边界，读取(24,9)，并停止，因为它被标记为该区域中的最后一棵树。

要获取(0,60)…(30,90)中的树木，请将(0,60)映射到地址20。跳过(24,9)，读取(23,65)，并停止，因为它是最后一个。

这将非常节省内存，因为它避免了存储指针，否则相对于实际数据来说，指针的大小将相当大。然而，闭散列需要留出一些空间。

图示不是“按比例缩放”的，因为实际上在哈希键标记之间会有几个条目的空间。因此，除非在本地前面的区域中有比平均值更多的树木，否则您不应该跳过任何条目。

这种方法利用了哈希碰撞的优势，因此它不像哈希函数通常那样随机。(并非每个条目都对应于一个不同的哈希值。) 然而，由于森林的密集区域通常是相邻的，您应该将扇区映射到“桶”的过程随机化，以便给定的密集扇区有望溢出到较少密集的扇区、下一个扇区或下下个扇区。

此外，还存在空扇区和终止迭代的问题。您可以在每个扇区中插入一个虚拟树来标记为空，或者使用其他简单的技巧。

很抱歉解释这么长。这种方法比记录更容易实现。但性能和占用空间可能非常优秀。

- Potatoswatter

Answer 5

使用某种空间分区数据结构。一个简单的解决方案是创建一个二维数组，其中包含30m x 30m区域内所有对象的列表。最坏情况下，您只需要与这些列表中的四个对象进行比较。

还可以使用许多更复杂（并且可能更有益）的解决方案 - 类似于双树的东西稍微复杂一些（但不太多），但可以获得更优化的性能（特别是在对象密度差异很大的情况下）。

- pdehaan

Answer 6

你可以查看 Matlab 中的 Voronoi 图支持：

http://www.mathworks.com/access/helpdesk/help/techdoc/ref/voronoi.html

如果您将 Voronoi 多边形基于关键树，然后将相邻的树聚类到这些多边形中，那么这将通过接近性将您的搜索空间分区（查找给定非关键点的包围多边形很快），但最终您将通过勾股定理或三角函数计算关键到非关键距离并进行比较。

对于几千个点（树），如果您的处理器足够合理，暴力方法可能足够快。计算每棵树与树 n 的距离，然后选择其中在 30 英尺内的树。这与所有树位于同一 Voronoi 多边形中相同。

我已经有几年没有在 GIS 中工作了，但我发现以下内容很有用：“C 语言计算几何”Joseph O Rourke，ISBN 0-521-44592-2 平装本。

- bwinspur