임의의 다각형 영역에 대한 좌표 결합 데이터 데이터베이스 검색

Question

각 항목이 위도/경도 좌표가있는 점으로 표시되는 관계형 데이터베이스가 있습니다. 나는 사용자에게 맵에 임의의 다각형을 표시 할 수있는 능력을 제공하고 다각형 모양의 모든 항목을 반환하려고합니다.

이것을 달성하는 가장 좋은 방법은 무엇입니까?

또한 작은 오류가 괜찮다는 것을 지적 할 가치가 있습니다 (즉, 다각형을 직사각형 세트로 바꿀 수있는 효과적인 방법이 있다면 괜찮습니다).

Answer 1

공간 확장을 사용하면 대부분의 데이터베이스에는이 기능이 있습니다. MySQL에서는 트랜잭션이 아닌 Myisam 테이블과 함께 사용할 수 있습니다.

http://dev.mysql.com/doc/refman/en/spatial-extensions.html

Answer 2

고려해야 할 점 수를 빠르게 줄이는 한 가지 방법은 다각형의 경계 사각형 (즉, 다각형의 점수의 최대 점)을 계산하는 것입니다. 경계 사각형 내의 점을 선택하십시오 (즉, X가 Min-X와 Max-X 사이이고 Y에 대해서는 동일).

물론 이러한 모든 점이 반드시 다각형 안에는 아니지만 이제 코드로 연마 할 수 있습니다.

Answer 3

오래된 해킹 :

라인을 연결하는 횟수를 계산하십시오 <point far away> 에게 <point in question> 다각형의 경계 세그먼트를 가로 지릅니다.

• 숫자조차도 포인트가 다각형 바깥에 있음을 의미합니다
• 홀수는 다각형 내부에 있음을 의미합니다