2017-01-30 13 views
1

У меня есть два набора мест: A (20K мест) и B (2k мест). Я хочу иметь карту для всех местоположений в наборе А в их ближайшем месте в наборе В на основе их широты и долготы.Расположение карт до ближайшего местоположения в зависимости от широты и долготы

Есть ли какое-либо решение в java или R. Java-решение предпочтительнее.

+0

Думаю, вам нужно вычислить все расстояния для всех точек. Все другие идеи, о которых я могу думать, в первую очередь нуждаются в расстоянии ... – IQV

+0

Являются ли эти местоположения в динамиках A и B в памяти? Или у вас их в базе данных или в некоторых? Если вам нужно создавать эту карту памяти каждый раз, когда ваше приложение выполняется, оно должно быть очень хорошим в производительности. Но если это может быть только однократная операция, и карта может быть сохранена где-то, ее не нужно оптимизировать. Это просто, поскольку все те места, где установлен A, вычисляют минимальное расстояние от этих местоположений в B. Это будет от 'O (n * n)' – STaefi

+0

Плюс никто не напишет это для вас. Вы должны сделать это самостоятельно, а затем, если у вас возникнут проблемы, вы должны предоставить [MCVE], чтобы получить помощь. – STaefi

ответ

1

Я согласен с @STaefi в комментариях, это хорошая идея показать хотя бы немного работы с вашей стороны, прежде чем просить других писать код для вас. Сказав это, ваша проблема вызвала мой интерес, чтобы схватить несколько минут моего времени, так что вот в R. Обратите внимание, что это только считается расстоянием как функция координат, которая не будет точна нигде, кроме экватора. Вам нужно будет изменить это, если вам нужна более высокая точность.

Возьмите небольшой гипотетический набор данных:

pointsA <- data.frame(lat = c(10, 12, 20), lon = c(12, 17, 10)) 
pointsB <- data.frame(lat = c(11, 15), lon = c(15, 15)) 

Написать функцию для вычисления ближайшей точки:

closest_point <- function(lat1, lon1, lat2, lon2) { 
    x_dist <- abs(lon1 - lon2) 
    y_dist <- abs(lat1 - lat2) 
    dist <- sqrt(x_dist^2 + y_dist^2) 
    closest <- data.frame(lat = lat2[ which.min(dist) ], 
          lon = lon2[ which.min(dist) ]) 
    return(closest) 
} 

Мы можем выполнить эту функцию на одной точке из pointsA, возвращающегося ближайшую точку из pointsB:

closest_point(pointsA[1,"lat"], pointsA[1,"lon"], pointsB[,"lat"], pointsB[,"lon"]) 
# lat lon 
# 1 11 15 

Или, мы можем применить его ко всем точкам из pointsA, возвращая ближайшую точку из pointsB для каждой из точек в pointsA

closest.points <- lapply(seq_len(nrow(pointsA)), 
          function(x) { 
           closest_point(lat1 = pointsA[x,"lat"], 
              lon1 = pointsA[x,"lon"], 
              lat2 = pointsB[,"lat"], 
              lon2 = pointsB[,"lon"]) 
          }) 
closest.points <- do.call(rbind, closest.points) 
closest.points 
# lat lon 
# 1 11 15 
# 2 11 15 
# 3 15 15 
2

Как из ответа от @rosscova

Возьмите очки, но в качестве матрицы

pointsA <- as.matrix(data.frame(lat = c(10, 12, 20), lon = c(12, 17, 10))) 
pointsB <- as.matrix(data.frame(lat = c(11, 15), lon = c(15, 15))) 

Затем, когда вы имеете дело с координатами, вы можете предпочесть использовать расстояние Великого круга (WGS84 эллипсоида) вместо евклидова. Я обычно использую spDists функцию из зр пакета

library(sp) 
out_Dists <- spDists(x = pointsA, y = pointsB, longlat = TRUE, segments = FALSE, diagonal = FALSE) 

и в конце с помощью применить функцию с which.min по рядам, чтобы получить ближайший pointB к pointA

pointsA[ apply(out_Dists, 1, which.min), ] 
+0

Отличная идея с использованием spDists, намного приятнее моего решения. Я отредактировал для вывода точек, но вместо ссылок, которые могут быть более полезными для вывода. – rosscova

+0

Спасибо! Да, это более полезно, поскольку требуемый результат должен быть картой местоположений. Подождем ответа OP! –

+0

Я снова отредактировал ответ, потому что возвращаемый вектор из «apply (out_Dists, 1, which.min)» будет иметь длину 3, например, data.frame «pointsA», к которой он ссылается, используя MARGIN 1. Вместо этого, если вы используете поле 2 было бы правильным ссылкой на точки dfB. –

0

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

Предполагается, что земля является сферической. Если вам нужны «идеальные» результаты, вам нужно будет преобразовать ваши координаты, используя более близкое приближение (например, WGS84).

import java.util.List; 
import java.util.stream.Collectors; 
import java.util.stream.Stream; 

import static java.lang.Math.*; 

public class LatLong { 
    public static void main(String[] args) throws Exception { 
     // A random lat/long 
     double[] target = randLatLong(); 
     // Transform to ECEF vector 
     double[] targetv = toEcef(target); 
     // 2000 random candidates 
     List<double[]> b = Stream.generate(LatLong::randLatLong).limit(2000).collect(Collectors.toList()); 
     // Transform candidates to ECEF representation 
     List<double[]> bv = b.stream().map(LatLong::toEcef).collect(Collectors.toList()); 

     // Find the closest candidate to the target 
     int i = closest(targetv, bv); 

     System.out.println("Closest point to " + target[0] + ", " + target[1] + " is " + b.get(i)[0] + ", " + b.get(i)[1]); 
    } 

    // index of closest vector to target from list of candidates 
    public static int closest(double[] target, List<double[]> candidates) { 
     double p = Double.MIN_VALUE; 
     int closest = -1; 
     for (int i = 0; i < candidates.size(); i++) { 
      double next = dotProduct(target, candidates.get(i)); 
      if (next > p) { 
       p = next; 
       closest = i; 
      } 
     } 
     return closest; 
    } 

    // dot product of two 3vectors 
    public static double dotProduct(double[] v1, double[] v2) { 
     return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]; 
    } 

    // lat/long in degrees to normalised ECEF vector 
    public static double[] toEcef(double[] latLong) { 
     return toEcef(toRadians(latLong[0]), toRadians(latLong[1])); 
    } 

    // lat/long in radians to normalised ECEF vector 
    public static double[] toEcef(double φ, double λ) { 
     return new double[] {cos(φ) * cos(λ), cos(φ) * sin(λ), sin(φ)}; 
    } 

    // A random lat/long 
    public static double[] randLatLong() { 
     return new double[] {Math.random() * 180 - 90, Math.random() * 360 - 180}; 
    } 
}