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

发布于 2024-09-01 08:49:17 字数 817 浏览 4 评论 0原文

因此，如果您查看我的其他帖子，您就会发现我正在构建一个可以在森林中收集数据并将其粘贴在地图上的机器人，这并不奇怪。我们的算法可以检测树中心和树干直径，并将它们粘贴在笛卡尔 XY 平面上。

我们计划使用某些“关键”树作为定位机器人的自然地标，使用三角测量和三边测量等方法，但仅使用 Matlab 对其进行编程并保持数据的直接和高效变得困难。

是否有一种技术可以对点数组或矩阵进行子设置？假设我有 1000 棵树存储在 1km (1000m) 范围内，有没有办法说，仅选择当前位置 30m 半径内的点并仅处理这些点？

我只会使用 GIS，但我在 Matlab 中执行此操作，我不知道有任何适用于 Matlab 的 GIS 插件。

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

我正在考虑将树数组镜像为两个数组，一个按 X 排序，另一个按 Y 排序。然后冒泡排序以确定其中的 30m 范围。我对两个数组 X 和 Y 执行相同的操作，然后使用第三个交叉链接表来选择各个值。但我不知道这叫什么，如何编程，而且我确信有人已经知道了，所以我不想重新发明轮子。

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

海的爱人是光 2024-09-08 08:49:17

您正在寻找一个空间数据库，例如 quadtree 或 kd-tree。我在此处和此处，但没有找到任何 Matlab 的四叉树实现。

回复收藏 0 原文

苦妄 2024-09-08 08:49:17

计算所有距离并扫描的简单解决方案似乎几乎可以立即运行：

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 机器上，我可以在 <100 万棵树（1 MTree？）中处理 100 万棵树（1 MTree？）。 0.4秒。

您是否直接在机器人上运行 Matlab 代码？你在使用实时工作室之类的吗？如果您需要将其转换为 C，可以将 hypot 替换为 sqr(trees[i].x - pos.x) + sqr(trees[i].y - pos.y) )，并将限制检查替换为 < lim^2。如果你真的只需要处理 1 个 KTree，我不知道是否值得你花时间去实现一个更复杂的数据结构。

The simple solution of calculating all the distances and scanning through seems to run almost instantaneously:

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

On a 1.2 GHz machine, I can process 1 million trees (1 MTree?) in < 0.4 seconds.

Are you running the Matlab code directly on the robot? Are you using the Real-Time Workshop or something? If you need to translate this to C, you can replace hypot with sqr(trees[i].x - pos.x) + sqr(trees[i].y - pos.y), and replace the limit check with < lim^2. If you really only need to deal with 1 KTree, I don't know that it's worth your while to implement a more complicated data structure.

回复收藏 0 原文

许仙没带伞 2024-09-08 08:49:17

您可以使用 CART2POL。然后在一定半径内选择点将是直接的。

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

其中X0，Y0是当前位置的坐标。

You can transform you cartesian coordinates into polar coordinates with CART2POL. Then selecting points inside certain radius will be strait-forward.

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

where X0, Y0 are coordinates of the current location.

回复收藏 0 原文

夏九 2024-09-08 08:49:17

我的猜测是，树木在森林中的分布大致均匀。如果是这种情况，只需使用 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)，然后停止。

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

该插图并非“按比例”，因为实际上哈希键标记之间会有多个条目的空间。因此，除非本地先前扇区中的树木数量多于平均水平，否则您不必跳过任何条目。

这确实利用了哈希冲突，因此它不像哈希函数通常那样随机。（并非每个条目都对应一个不同的哈希值。）但是，由于森林的密集部分通常是相邻的，因此您应该将扇区映射到“存储桶”随机化，因此给定的密集扇区有望溢出到密度较低的扇区，或下一个，或下一个。

此外，还存在空扇区和终止迭代的问题。您可以在每个扇区中插入一棵虚拟树以将其标记为空，或者进行其他一些简单的修改。

抱歉这么长的解释。这种事情实施起来比记录起来更简单。但性能和占用空间都非常出色。

My guess is that trees are distributed roughly evenly through the forest. If that is the case, simply use 30x30 (or 15x15) grid blocks as hash keys into an closed hash table. Look up the keys for all blocks intersecting the search circle, and check all hash entries starting at that key until one is flagged as the last in its "bucket."

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

For example, to get the trees in (0,0)…(30,30), map (0,0) to the address 0 and read entries (1,3), (10,15), reject (3,46) because it's out of bounds, read (24,9), and stop because it's flagged as the last tree in that sector.

To get trees in (0,60)…(30,90), map (0,60) to address 20. Skip (24, 9), read (23, 65), and stop as it's last.

This will be quite memory efficient as it avoids storing pointers, which would otherwise be of considerable size relative to the actual data. Nevertheless, closed hashing requires leaving some empty space.

The illustration isn't "to scale" as in reality there would be space for several entries between the hash key markers. So you shouldn't have to skip any entries unless there are more trees than average in a local preceding sector.

This does use hash collisions to your advantage, so it's not as random as a hash function typically is. (Not every entry corresponds to a distinct hash value.) However, as dense sections of forest will often be adjacent, you should randomize the mapping of sectors to "buckets," so a given dense sector will hopefully overflow into a less dense one, or the next, or the next.

Additionally, there is the issue of empty sectors and terminating iteration. You could insert a dummy tree into each sector to mark it as empty, or some other simple hack.

Sorry for the long explanation. This kind of thing is simpler to implement than to document. But the performance and the footprint can be excellent.

回复收藏 0 原文