다각형에 대한 다각형 알고리즘의 포인트

Question

다각형이있는 Google지도가 있습니다. 여기

내가 관심이있는 문제이다. 다각형의 위도을 감안할 때, LNG 점,이 점에있다 모든 다각형을 결정하는 가장 좋은 방법은 무엇

확실한 방법을 실행하는 것입니다 "점 "알고리즘을 반복적으로 각 다각형,하지만 거기에 효율적인 알고리즘을 esp 경우 수천 개의 다각형이 있으면 대답하는 궁금 해서요.

Answer 1

"각 다각형"알고리즘을 개선하는 유일한 방법은 일부 다각형을 건너 뛸 수있는 메타 데이터 집합을 만드는 것입니다. 예를 들어 수천 개의 다각형에 대해 서로 겹친 모든 다각형의 목록 또는 목록 집합이있는 경우 신속하게 많은 다 지점 간 비교를 제거 할 수 있습니다. 나는. 점을 포함하는 첫 번째 다각형을 찾은 다음 그 점을 포함하는 모든 다각형 또한 포함하고있는 다른 다각형과 겹쳐 야하기 때문에 첫 번째 다각형과 겹치거나 겹치는 다각형 만 비교하십시오. 최악의 경우는 N 개의 비교가됩니다. 각 구현에 대해

또한 특정 영역의 다각형의 논리적/물리적 영역 (예 : 사분면)을 생성 할 수 있습니다. 사분면 예제에서는 비교를 위해 3/4의 폴리곤을 제거 할 수 있어야합니다. 이 모든 것은 다각형이 어떻게 정렬되어 있느냐에 달려 있습니다.

그러나 어떤 경우 든 for-each 알고리즘의 개선은 다각형 컬렉션 중 일부 논리 그룹의 생성/구성에 있다고 생각합니다.

Answer 2

내가 무엇을 아래에 잘 모릅니다 만, 나를 위해 다각형 기능을 미리 선택 다각형을 포함하는 계층에 공간 필터을 적용 ... 예제이 하나 void GRLayer::SetSpatialFilter (OGRGeometry * poFilter) http://www.gdal.org/ogr/classOGRLayer.html#0b4ab45cf97cbc470f0d60474d3e4169입니다. 많은 GIS 환경이 비슷한 기능을 가지고 있다고 생각합니다.