Выберите все точки в матрице в пределах 30 м от другой точки

Question

Так что, если вы посмотрите на мои другие посты, не удивительно, что я создаю робота, который может собирать данные в лесу и прикреплять их на карту. У нас есть алгоритмы, которые могут определять центры деревьев и диаметры стволов и прикреплять их к декартовой плоскости XY.

Мы планируем использовать определенные «ключевые» деревья в качестве естественных ориентиров для локализации робота, используя триангуляцию и трилатерацию среди других методов, но программирование этого и обеспечение точности и эффективности данных становится затруднительным с использованием только Matlab.

Есть ли метод для поднабора массива или матрицы точек? Скажем, у меня хранится 1000 деревьев на расстоянии более 1 км (1000 м), есть ли способ сказать, выбирать только точки в радиусе 30 м от моего текущего местоположения и работать только с этими?

Я бы просто использовал ГИС, но я делаю это в Matlab и не знаю ни одного плагина ГИС для Matlab.

Я забыл упомянуть, этот код запущен в сети, то есть робот работает в режиме реального времени. Я не знаю, поможет ли карта по мере увеличения расстояния в несколько миль использовать другую структуру данных или если вычисление каждого расстояния до случайной точки является тем или иным образом пространственной базой данных.

Я думаю о зеркальном отражении массива деревьев в два массива, один из которых отсортирован по X, а другой по Y. Затем сортировка по пузырькам для определения 30-метровой дальности. Я делаю то же самое для обоих массивов, X и Y, а затем у меня есть третья таблица перекрестных ссылок, которая выберет отдельные значения. Но я не знаю, как это называется, как программировать это, и я уверен, что кто-то уже есть, поэтому я не хочу изобретать велосипед.

Декартовой самолет
GIS

Answer 1

Вы ищете пространственную базу данных, например quadtree или kd-tree . Я нашел две реализации дерева kd здесь и здесь , но не нашел ни одной реализации дерева квадрантов для Matlab.

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 ГГц я могу обработать 1 миллион деревьев (1 МТр?) За <0,4 секунды. </p>

Вы запускаете код Matlab прямо на роботе? Вы используете мастерскую в реальном времени или что-то? Если вам нужно перевести это на C, вы можете заменить hypot на sqr(trees[i].x - pos.x) + sqr(trees[i].y - pos.y) и заменить проверку ограничения на < lim^2. Если вам действительно нужно иметь дело только с 1 KTree, я не знаю, стоит ли вам реализовывать более сложную структуру данных.

Answer 3

Вы можете преобразовать свои декартовы координаты в полярные координаты с помощью CART2POL . Тогда выбор точек внутри определенного радиуса будет прямым.

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

где X0, Y0 - координаты текущего местоположения.

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) и остановитесь, так как это последнее.

Это будет весьма эффективно с точки зрения памяти, поскольку позволит избежать хранения указателей, которые в противном случае имели бы значительный размер по сравнению с фактическими данными. Тем не менее, закрытое хеширование требует наличия некоторого пустого пространства.

Иллюстрация не "в масштабе", так как на самом деле между маркерами хеш-ключа должно быть пространство для нескольких записей. Поэтому вам не нужно пропускать какие-либо записи, если в локальном предыдущем секторе деревьев больше, чем в среднем.

Это использует коллизии хешей в ваших интересах, так что это не так случайно, как обычно это делает хеш-функция. (Не каждая запись соответствует отдельному хэш-значению.) Однако, поскольку плотные участки леса часто будут смежными, вы должны рандомизировать отображение секторов в «сегменты», так что данный плотный сектор, как мы надеемся, будет переполнен на менее плотный, или следующий, или следующий.

Кроме того, существует проблема пустых секторов и завершения итерации. Вы можете вставить фиктивное дерево в каждый сектор, чтобы пометить его как пустое, или какой-то другой простой взлом.

Извините за длинное объяснение. Такого рода вещи проще реализовать, чем документировать. Но производительность и площадь могут быть отличными.

Answer 5

Вы можете посмотреть на поддержку диаграммы вороной в Matlab:

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

Если вы строите многоугольники вороного на своих ключевых деревьях и кластерируете соседние деревья в эти многоугольники, это разделит ваше пространство поиска по близости (поиск включающего многоугольника для данной неключевой точки будет быстрым), но в конечном итоге вы собираемся приступить к вычислению ключа к неключевым расстояниям с помощью Пифагора или трига и сравнивать их.

Для нескольких тысяч точек (деревьев) грубая сила может быть достаточно быстрой, если у вас есть разумный процессор на борту. Вычислите расстояние любого другого дерева от дерева n, затем выберите те в пределах 30 '. Это то же самое, что все деревья в одном и том же многоугольнике вороного.

Прошло несколько лет с тех пор, как я работал в ГИС, но я нашел следующее полезное: «Вычислительная геометрия в Си» Джозеф О Рурк, ISBN 0-521-44592-2 Мягкая обложка.

Answer 6

Использовать какую-то пространственно разделенную структуру данных. Простым решением было бы просто создать двумерный массив списков, содержащий все объекты в области 30 х 30 м. В худшем случае вам нужно сравнивать только объекты в четырех из этих списков.

Можно также использовать множество более сложных (и потенциально полезных) решений - что-то вроде двух деревьев немного сложнее в реализации (хотя и не намного), но может получить более оптимальную производительность (особенно в случаях, когда плотность объектов значительно варьируется).