위도/경도 데이터로 효율적인 범위 검색 및 계산을 어떻게 수행 할 수 있습니까?

Question

나는 위도/경도 쌍으로 표현 된 많은 수의 포인트로 작업하고있다. (포인트는 반드시 고유 할 필요는 없으며 같은 위치에있는 여러 포인트가 세트에있을 수있다). 포인트는 데이터베이스에 저장됩니다.

내가해야할 일은 효율적으로 검색을 수행하여 임의의 지점의 주어진 반경 (예 : 25 마일) 내에있는 지점의 수를 얻는 방법을 찾는 것입니다. 카운트가 100 % 정확할 필요는 없습니다. 더 중요한 것은 빠르고 정확해야하며 정확한 카운트에 가깝습니다. WHERE 절에서 일부 삼각법과 함께 쿼리를 사용하여 참조 점까지의 거리를 기준으로 필터링 할 수 있으므로 SQL에서이 작업을 수행 할 수 있습니다. 불행하게도이 쿼리는 매우 비싸고 캐싱은 위치가 매우 분산되어 있기 때문에 많은 도움을 줄 수 없습니다.

필자는 궁극적으로 데이터의 정확성과 생동감을 일부 교환 할 수있는 이런 종류의 작업을 효율적으로 처리 할 수있는 일종의 메모리 내장 구조를 구축하려고합니다 (하루에 한 번만 다시 빌드) 속도에 대한 대가로 나는 kd 나무에 대한 연구를 해왔지만 위도/경도 데이터 (2 차원 평면의 x, y 데이터와 반대)에 이것이 얼마나 잘 적용되는지 아직 명확하지 않습니다.

아무도 내가 들여다 봐야 할 아이디어 나 해결책이 있다면 정말 고맙겠습니다. 미리 감사드립니다.

Answer 1

공간 데이터에 대해 일종의 검색 트리를 사용하십시오. a quad tree. 더 많은 데이터 구조는 "참조"에서 참조됩니다.

Answer 2

기존 비싼 검색어 샘플을 제공해 주시겠습니까?

참조 점 및 다른 데이터 점의 sine() 및 cosine()을 기반으로 올바른 대원 계산을 수행하는 경우 실제로는 해당 sin/cos을 저장하여 매우 실질적인 최적화를 수행 할 수 있습니다 lat/long 값 외에도 데이터베이스의 값.

또는 데이터베이스를 사용하여 일치하는 위도/경도 범위를 추출한 다음 실제 원형 반경 밖에있는 필터를 필터링하십시오.

위도 1 도는 적도보다 고위도에서 다소 짧은 거리라는 것을 명심하십시오. 하지만 그 직사각형의 올바른 종횡비를 쉽게 파악할 수 있어야합니다. 직사각형 선택이 극을 중첩 한 원에 대처하지 않으므로 극에 매우 가까운 영역을 고려해야 할 경우 오류가 발생합니다.

Answer 3

R-Trees을 사용하십시오.

CREATE INDEX ix_spatial ON spatial_table (locations) INDEXTYPE IS MDSYS.SPATIAL_INDEX; 

당신을 위해 R-Tree을 만들고 그 위에 검색합니다 : 오라클 공간을 사용하여 Oracle에서

는, 당신은 인덱스를 생성 할 수 있습니다.

Earth Model은 (는) WGS84, PZ-90 등을 사용할 수 있습니다.

Answer 4

이 UDF (SQL 서버) 두 개의 위도/경도 점 사이 당신에게 거리를 얻을 것이다 :

SELECT * FROM table WHERE [dbo].[zipDistance] < 25.0 

: 분명히,

CREATE FUNCTION [dbo].[zipDistance] (
    @Lat1 decimal(11, 6), 
    @Lon1 decimal(11, 6), 
    @Lat2 decimal(11, 6), 
    @Lon2 decimal(11, 6) 
) 
RETURNS 
    decimal(11, 6) AS 
BEGIN 

    IF @Lat1 = @Lat2 AND @Lon1 = @Lon2 
     RETURN 0 /* same lat/long points, 0 distance = */ 

    DECLARE @x decimal(18,13) 
    SET @x = 0.0 

    /* degrees -> radians */ 
    SET @Lat1 = @Lat1 * PI()/180 
    SET @Lon1 = @Lon1 * PI()/180 
    SET @Lat2 = @Lat2 * PI()/180 
    SET @Lon2 = @Lon2 * PI()/180 

    /* accurate to +/- 30 feet */ 
    SET @x = Sin(@Lat1) * Sin(@Lat2) + Cos(@Lat1) * Cos(@Lat2) * Cos(@Lon2 - @Lon1) 
    IF 1 = @x 
     RETURN 0 

    DECLARE @EarthRad decimal(5,1) 
    SET @EarthRad = 3963.1 

    RETURN @EarthRadius * (-1 * ATAN(@x/SQRT(1 - @x * @x)) + PI()/2) 

END 

을, 당신은 같은 별도의 쿼리에서 이것을 사용할 수 있습니다

Answer 5

이 솔루션을 사용하지 않아도됩니다. 며칠 전에 무작위로 그것에 대해 생각한 결과, 특정 지점에서 격자 사각형의 위치까지의 거리를 측정하는 것이 획일 화 된 격자가 아닌 원형을 기반으로한다고 생각합니다. 0,0에서 멀어 질수록 덜 정확합니다.

내가 한 것은 내 PostalCode 클래스에 2 개의 추가 값을 가졌기 때문입니다. 때마다 나는 그런 내가 지금처럼 내 클래스를 업데이트, 내가 X, 긴 0에서 Y 거리를 계산을 PostalCode에

public static class MathExtender 
{ 
    public static double GetDistanceBetweenPoints(double sourceLatitude, double sourceLongitude, double destLatitude, double destLongitude) 
    { 
     double theta = sourceLongitude - destLongitude; 
     double distance = 
      Math.Sin(DegToRad(sourceLatitude)) 
      * Math.Sin(DegToRad(destLatitude)) 
      + Math.Cos(DegToRad(sourceLatitude)) 
      * Math.Cos(DegToRad(destLatitude)) 
      * Math.Cos(DegToRad(theta)); 
     distance = Math.Acos(distance); 
     distance = RadToDeg(distance); 
     distance = distance * 60 * 1.1515; 
     return (distance); 
    } 


    public static double DegToRad(double degrees) 
    { 
     return (degrees * Math.PI/180.0); 
    } 

    public static double RadToDeg(double radians) 
    { 
     return (radians/Math.PI * 180.0); 
    } 
} 

위도 0 긴/위도를 업데이트

private void CalculateGridReference() 
{ 
    GridReferenceX = MathExtender.GetDistanceBetweenPoints(0, 0, 0, Longitude); 
    GridReferenceY = MathExtender.GetDistanceBetweenPoints(0, 0, Latitude, 0); 
} 

을 그래서 지금 내가 가지고있는 내 DB의 각 행에 대한 그리드 참조 0,0에서 x, y 그리드 거리 (마일). 긴/위도 5 마일의 모든 장소를 찾으려면 먼저 X, Y 그리드 참조 (예 : 25,75)를 얻고 DB에서 20 .. 30, 70..80을 검색 한 다음 결과를 메모리로 필터링

MathExtensder.GetDistanceBetweenPoints(candidate.Lat, candidate.Long, search.Lat, search.Long) < TheRadiusOfInterest 

DB 파트는 매우 빠르며 메모리 파트는 더 작은 세트에서 작동하여 매우 정확합니다.

Answer 6

Bombe의 제안에 대한 훌륭한 설명은 Jan Philip Matuschek의 기사 "Finding Points Within a Distance of a Latitude/Longitude Using Bounding Coordinates"에서 찾을 수 있습니다.