Linestrings가 포함 된 데이터 세트를 최적화하는 가장 좋은 방법. 일부 선은 같은 좌표로 시작하고 끝납니다

StackOverflow https://stackoverflow.com/questions/462640

문제

설정
리 스트링이 포함 된 테이블이 있습니다. Linestrings는 여러 지리적 지점으로 구성됩니다. 각 지점은 위도와 경도로 구성됩니다. 참고 : Linestring 값은 데이터베이스에 텍스트로 저장됩니다.

따라서 테이블의 한 줄은 다음과 같이 보일 수 있습니다.
ID : 정수
Linestring : x1, y2, x2, y2, x3, y3, x4, y4

문제
Google지도를 통해 한 번에 최대 1000 개의 요소 만 표시 할 수 있습니다. 제 경우에는 850 개의 리 스트링을 표시하고 있으며 앞으로 더 많은 것을 추가해야합니다.

질문
꽤 많은 Linestrings는 하나 이상의 다른 Linestrings와 연결되므로 동일한 좌표로 시작 및/또는 종료 함을 의미합니다. 내가 생각하는 것은 데이터 세트를 최적화하는 가장 좋은 방법을 찾는 것입니다. 따라서 끝에 연결되는 Linestrings는 DB 테이블에 병합됩니다. DB 테이블을 구문 분석하고 Google지도의 디스플레이 파일을 작성하면 총 요소 수가 줄어 듭니다.

예시
이 예에서는 알파 (A, B, C) 값이 지리적 지점을 나타냅니다. 최적화되지 않은 테이블은 다음과 같습니다.

최적화 전 :
이드 리 스트링
1 a, b, c
2 C, d
3 b, a
4 F, G, H.
5 g, i
6 시간, j

최적화 후 :
1 a, b, c, d
2 F, G, H, J.
3 g, i

그렇다면 데이터를 최적화하는 가장 좋은 방법은 무엇입니까? 가장 잘 작동하는 특정 알고리즘이 있습니까? 나는 공식화하고 추가 할 솔루션에 대한 아이디어가 있지만, 그들은 장황하고 유죄 판결을받는 것처럼 보입니다.

나는 CS 전공이 아니므로 조잡한 용어를 변명하고 어디에서나 설명이 필요한지 알려주세요. 감사!

참고로 .. MySQL DB를 사용하고 있습니다. 나는 공간 확장을 사용하지 않습니다. 공간 확장을 사용하는 당황스럽고 간단한 솔루션이 있다면 어쨌든 듣고 싶습니다.

도움이 되었습니까?

해결책

깨달아야 할 한 가지는 주어진 Linestring에 연결할 수있는 Linestring이 하나 이상 있으면 선택한 사람은 중요하지 않습니다 - 최적화 된 테이블의 최종 리 스트링 수는 동일합니다.

이 경우, 더 이상 그러한 쌍을 찾을 수 없을 때까지 결합 할 수있는 한 쌍의 린 스트링을 찾는 간단한 탐욕 전략은 최적의 테이블을 제공합니다. 본질적으로 의사 코드는 다음과 같습니다.

while (there exists a pair of linestrings x and y that share an endpoint) {
    delete(x)
    delete(y)
    insert(x . y)
}

결과적인 Linestring 가능성 때문에 단일 SQL 쿼리에서는 수행 할 수 없습니다. x . y 다시 사용됩니다. T-SQL과 같은 절차 언어 또는 스크립팅 언어 (예 : 데이터베이스 액세스를 위해 DBI 사용)를 사용하여 while 루프를 작성하고 SQL Select 쿼리를 사용하여 쌍 또는 쌍 목록을 찾아야합니다. 그런 다음 삭제 및 삽입 문을 사용하여 각각 처리합니다.

테이블에 두 개의 필드를 추가하는 것이 좋습니다. begin 그리고 end, 검색 속도를 높이기 위해 색인.

다른 팁

여기로가는 가장 쉬운 방법은 MySQL 공간 확장을 사용하는 것입니다.

특히 나는 Oracle Spatial Extension 만 사용했습니다. Oracle에서는 기능을 사용할 수 있습니다 SDO_GEOM. Relate 또는 SDO_RELATE 두 객체 사이의 공간 관계를 찾으려면 (포함, 터치, 교차 등)

MySQL에 동등한 공간 기능이 있다고 확신합니다.

편집하다:

여기에 있습니다 링크 여기에는 사용 가능한 모든 MySQL 공간 기능이 나와 있습니다.

모든 엔드 포인트가 최대 두 번 나타나면 (하나의 린 스트링을 끝내고 다른 하나를 시작) 고유 한 솔루션이있을 것입니다. 예 : 당신이 가지고 있다면 어떻게되는지 :

  1. a, b, c
  2. CD
  3. C, E, f

이 생산해야합니다 :

  1. a, b, c, d
  2. C, E, f

또는:

  1. a, b, c, e, f
  2. CD

?

아니면 신경 쓰지 않습니까?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top