0

For simplicity, if I have a vector of points which looks something like:

x = c(1,4,5,8,9)

I'm trying to find the n points which are equidistant from one another. In this case my n=3 so my ideal answer would be:

1,5,9

Since 5-1=4 and 9-5=4.

The actual vectors are much larger/complex as well as n. Any ideas on how I can achieve this?

Thanks in advance!

Omar Wagih
  • 8,504
  • 7
  • 59
  • 75
  • 2
    To be honest I don't get why `1,5,9` are equidistant. A point is said to be equidistant from a set of objects if the distances between that point and each object in the set are equal. – storaged Jun 18 '13 at 21:17
  • Why "most likely" equidistant? Equidistance is either true or false, right? A set is equidistant if the distance between any two points in the set is the same real number. In your example, 1,5,9 is not equidistant since |5-1| != |9-1|. – Codie CodeMonkey Jun 18 '13 at 21:25
  • It seems like there could be several vectors of length `n` that would be equidistant, especially if `length(x)` is large, and `n` is small. – rbatt Jun 18 '13 at 22:22

2 Answers2

1

Consistent with comments above, here's something that might be what you want, not necessarily what you ask for. I'm sure there is a more efficient way to do this, though. 

x = c(1,4,5,8,9)
x2 <- as.matrix(expand.grid(x, x))
x2 <- as.data.frame(t(apply(x2, 1, sort)))
x2 <- x2[!duplicated(x2), ]
x2 <- cbind(x2, d =abs(mapply("-", x2[,1], x2[,2])))
x2[order(x2$d), ]
# V1 V2 d
# 1   1  1 0
# 7   4  4 0
# 13  5  5 0
# 19  8  8 0
# 25  9  9 0
# 8   4  5 1
# 20  8  9 1
# 2   1  4 3
# 14  5  8 3
# 3   1  5 4
# 9   4  8 4
# 15  5  9 4
# 10  4  9 5
# 4   1  8 7
# 5   1  9 8
Jack Ryan
  • 2,134
  • 18
  • 26
1

This isn't the whole solution, but I think it is the start of one. First, computing the distance matrix will probably be helpful.

> x <- c(1,4,5,8,9)
> dx <- dist(x)
> dx
  1 2 3 4
2 3      
3 4 1    
4 7 4 3  
5 8 5 4 1

Second, you can identify points which are the same distance apart by sorting the distances and run-length encoding them.

> rdx <- rle(sort(dx))
> rdx
Run Length Encoding
  lengths: int [1:6] 2 2 3 1 1 1
  values : num [1:6] 1 3 4 5 7 8

you can select the set of points you want and then get back to the indices in the original distance matrix using the order function. Taking the third group -- of points separated by distance 4 -- as an example

> i=3
> orderedIndex <- sum(rdx$lengths[1:(i-1)])
> order(dx)[(orderedIndex+1):(orderedIndex+rdx$lengths[i])]
[1] 2 6 9

(the indices count from the top down then from left to right). So here you have identified the 4s in the distance matrix: these are distances between the 1st/3rd, 2nd/4th, and 3rd/5th points in x. But you still have to do some more work to eliminate the 2nd and 4th points. Presumably you choose the 1st, 3rd and 5th points because they are connected?

I think you would want to process all groups of points identified by the rle function as over your chosen size, and then check for connectivity.

TooTone
  • 7,129
  • 5
  • 34
  • 60
  • PS there is a [great answer here](http://stackoverflow.com/a/17191756/834521) as to how to go from the index in a distance matrix back to (row,columns) – TooTone Jun 19 '13 at 14:47