СуперСортировка точек по расстоянию друг от друга

[qssaka]

Основная задача, найти все точки, расположенные ближе, чем в 1 м друг от друга. "Друг от друга" - ключевое условие. Есть ли готовый инструмент для этого и как им пользоваться ? К примеру "Анализ близости" в аркгис ??

Если нет такого инструмента, то:
Есть файл. В нем номера точек N и прямоугольные координаты каждой из них (X, Y). Нужно их отсортировать по степени их удаленности друг от друга. Очевидно, что проще всего отсортировать все возможные пары точек! [Всего таких пар будет, видимо, N*(N-1) ]

заголовки:........N....X..Y ............................. N_пары .... D --(расстояние между точками в паре)
на входе:........ А = (0, 1).............на выходе.... A,B ........ d_1
.................... В = (10, 4) .............................B,D........ d_2
.................... C = (1, 0)...............................C,A ........d_3
.....................D = (10, 5) .............................B,C.........d_4
................................................................С,D ........d_5

т.е. пары точек должны быть сортированы по убыванию от расстояния. лучше, но не критично, чтобы А,B и B,A не дублировались.

[gamm]

Основная задача, найти все точки, расположенные ближе, чем в 1 м друг от друга. "Друг от друга" - ключевое условие. Есть ли готовый инструмент для этого и как им пользоваться ?

1) инструмент есть, называется R
2) если точек мало, то считаем матрицу взаимных расстояний dist(), переводим ее в векторный вид, и выбираем нужные пары
3) если много, для точного решения используем k-d дерево, в R вроде так реализован поиск соседей, деталей не помню, давно было.
4) если не нашли готового, то строим пространственный индекс - на сетке с шагом 1км нужно брать только точки из соседних 8 ячеек и из нее самой, делаем цикл по ячейкам сетки, объединяем результаты (ну и там всякие граничные эффекты учитываем).

[qssaka]

я не такой профи как вы, опыта в R нету совсем: а) не понятно как туда импортировать свои данные (1500 точек); b) не понятно, что такое k-d дерево и как его "строить"; c) не понятно, "если не нашли готового" ?решения?, "то строим пространственный индекс" - каким образом?

[gamm]

а) не понятно как туда импортировать свои данные (1500 точек);

read.table(), читаем help

b) не понятно, что такое k-d дерево и как его "строить"; c) не понятно, "если не нашли готового" ?решения?, "то строим пространственный индекс" - каким образом?

поскольку мало точек, то используем план (а)

Код: Выделить всё

p<-read.table("my_data.dat",header=TRUE)
p.dist<-as.double(as.matrix(dist(p[,c("X","Y")])))
p.xy<-expand.grid(1:nrow(p),1:nrow(p))
p.all<-data.frame(Id1=p.xy[,1],Id2=p.xy[,2],dist=p.dist)
ind<-(p.dist<1000) & (p.all$Id1 != p.all$Id2) # assume coord in meters
p.1km<-p.all[ind,]
write.table(p.1km,"res.dat",row.names=FALSE,quote=FALSE)

[Алекс]

Нанести точки на карту (геокодирование), построить вокруг них буферные зоны радиусом 1м и найти пересечения этих зон.
Я думаю, такой инструментарий есть в разных ГИС.

[qssaka]

to gamm Спасибо, все получилось !
------------------------------------------------------------------
тем не менее, вопрос не снят. как в аркгис просто и быстро реализавать тоже через тулбокс ?

[gamm]

тем не менее, вопрос не снят. как в аркгис просто и быстро реализавать тоже через тулбокс ?

про кнопки не скажу, потому как Аркой не пользуюсь (надобности нет). А идеологически написано постом выше: строим буфер в отдельный слой, и делаем overlay (point-in-region)