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

所以，如果你看看我的其他职位，这是毫不奇怪我建立一个机器人，可以在森林中收集数据，并把它贴在地图上。我们有可以检测树木中心和树干直径的算法，并且可以将它们粘在笛卡儿XY平面上。另一个点30m以内选择矩阵中的所有点

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

是否有子设定点中的阵列或矩阵的技术？假设我有1000多棵树存放在1公里（1000米）以上，有没有办法说明，只选择距离我目前位置半径30米内的点，并且只与这些点一起工作？

我只想用一个GIS，但我在Matlab这样做的，我不知道任何GIS插件Matlab的的。

我忘了提，这个代码将在网上，这意味着它是怎么回事了实时执行的机器人。我不知道，随着地图增长到几英里，使用不同的数据结构将会有所帮助，或者如果计算到随机点的每个距离是空间数据库将要做什么。

我想镜像树木的阵列，成两个阵列，一个X排序和其它由Y.然后冒泡排序，以确定在该范围30米的。我对两个数组X，Y都做同样的事情，然后有第三个交叉链接表来选择各个值。但我不知道，那叫什么，如何编程，我确定有人已经有了，所以我不想重新发明轮子。

Cartesian Plane
GIS

来源

2010-05-11 Phil Salesses

GIS？笛卡尔飞机？ – Potatoswatter 2010-05-11 23:25:44

这是什么意思？你不知道什么意思，或者你在问什么？我在问题的底部为你添加了链接。 – 2010-05-11 23:36:44

对不起，我对地理不太熟悉，但是经纬度不是笛卡儿，森林有高度......无论如何，我认为封闭散列在这里可能会表现的很好。 – Potatoswatter 2010-05-12 02:03:40

通过计算所有的距离和扫描的简单的解决方案似乎几乎在瞬间运行：

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

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

来源

2010-05-11 22:37:41 mtrw

我忘了提及，这段代码正在上线，这意味着它正在进行实时执行的机器人。我不知道，如果地图增长到几英里，使用不同的数据结构将会有所帮助，或者如果计算每个距离就是它正在做的事情。我想重复两个数组，按X排序，另一个由Y.然后冒泡排序来找到高和低的范围。我对两个数组X，Y都做同样的事情，然后有第三个交叉链接表来选择各个值。但我不知道，这就是所谓的，如何编程，我确定有人已经拥有。 – 2010-05-11 23:29:08

如果你比较lim^2，你不应该取平方和的平方根。 – Jonas 2010-05-12 03:29:13

@Jonas - 我同意。 Matlab代码使用'hypot'，它采用sqrt，而建议的C代码使用'sqr（x）+ sqr（y）'，并且需要与sqr（lim）进行比较。 – mtrw 2010-05-12 03:42:59

您可以使用CART2POL将笛卡尔坐标转换为极坐标。然后选择特定半径内的点将是横向的。

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

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

来源

2010-05-12 00:03:22 yuk

我用你的解决方案作为加速我的解决方案的灵感。谢谢！ – mtrw 2010-05-12 00:26:40

您正在寻找像quadtree或kd-tree空间数据库。我发现了两个kd-tree实现here和here，但没有找到用于Matlab的任何四叉树实现。

来源

2010-05-12 00:03:53

使用某种空间分区的数据结构。一个简单的解决方案是简单地创建一个包含30m x 30m区域内所有对象的2d列表数组。最糟糕的情况是，你只需要比较其中四个列表中的对象。

还可以使用许多更复杂（也可能有益）的解决方案 - 类似于双树实现起来更复杂一点（但不是太多），但可以获得更优化的性能（尤其是在物体的密度变化很大）。

来源

2010-05-12 00:05:37 pdehaan

你可以看看在MATLAB Voronoi图支持：

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

如果立足于你的关键树木沃罗诺伊多边形和群集邻近树木成的多边形，将分割搜索空间通过近似（找出给定非关键点的包围多边形是快速的），但最终你会仔细研究pythagoras或trig对非关键距离的计算，并比较它们。

对于几千点（树），如果你有一个合理的处理器，蛮力可能足够快。计算树中每一棵树的距离n，然后选择30'以内的树。这与使所有树在相同的voronoi多边形中相同。

自从我在GIS工作几年以来，我发现以下内容非常有用：'C计算几何'Joseph O Rourke，ISBN 0-521-44592-2平装本。

来源

2010-05-12 01:24:18 bwinspur

我的猜测是树木大致均匀地分布在森林中。如果是这种情况，只需使用30x30（或15x15）网格块作为散列键到closed hash table。查找与搜索圈相交的所有块的关键字，并检查从该关键字开始的所有哈希项，直到其中一个被标记为其“最后”。

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），并停止为最后一个。

这将是相当高效的存储器，因为它避免了存储指针，否则这些指针相对于实际数据会有相当大的大小。尽管如此，封闭散列需要留下一些空白空间。

该图不是“按比例缩放”，因为实际上在散列键标记之间会有几个条目的空间。所以你不应该跳过任何条目，除非在当地的先行部门有更多的树比平均水平。

这确实使用散列冲突来获得优势，所以它不像散列函数那样随机。（不是每个条目都对应一个明确的散列值）。但是，由于密集的森林部分通常会相邻，因此应该将各部门的映射随机化为“桶”，因此给定的密集扇区将有望溢出到较不密集的扇区，或下一个，或下一个。

此外，还有空白扇区和终止迭代的问题。您可以在每个扇区中插入一个虚拟树，将其标记为空或其他简单的黑客。

对不起，很长的解释。这种事情比文件实施更简单。但是性能和占地面积可以很好。

来源

2010-05-12 02:01:30 Potatoswatter

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

回答

相关问题