지도를 주어진 반경의 원으로 나누는 방법은 무엇입니까?

Question

여러분,

어떻게하면 주를 반경 50 마일의 영역으로 나눌 수 있습니까?

아마도 내 문제를 해결하는 더 좋은 방법이 있습니다. 고유 한 도시 이름이있는 700 개의 위치 목록이 있습니다. 일부 도시는 50 마일 미만 떨어져 있습니다. 나는 그 목록을 50 마일 이상 떨어져있는 최소한의 위치로 줄여야하며, 근본적으로 그 목록에있는 인근 도시들을 포함한다. 이렇게하면 축소 된 목록에서 각 위치의 중심 반경 우편 번호를 찾은 다음 700 개 위치를 모두 반환해야하는 "50 마일 이내에있는 상점"을 검색 할 수 있습니다.

업데이트 : 다른 도시에는 5000 개의 제품과 700 개의 상점이 있습니다. 모든 제품의 재고를 확인해야합니다. 내가 확인하는 사이트는 특정 도시의 50 마일 이내에있는 상점의 인벤토리만을 보여줍니다. 즉, 350 만 건의 요청을해야합니다. 따라서, 나는 700 개의 상점을 더 적은 수로 줄이는 방법을 찾고있다.

Answer 1

작동하는 간단한 알고리즘이지만 최적은 아닙니다. 이

1. 어떤 도시는

을 남아 있지 때까지 원 안에

반복 모든 마을을 제거, 무작위로 마을을 선택하는 것이 포인트

주위에 원을 그리 후보의 도시 목록 시작

몇 번 실행하면 일부 실행에서 결과로 생성되는 서클이 훨씬 적게 생성되는지 확인할 수 있습니다.

Answer 2

x 좌표와 y 좌표의 이진 값을 연결할 수 있습니다. 직선 대신 Z 축을 따라 점을 정렬합니다. 그런 다음 가장 중요한 비트로 상한을 계산할 수 있습니다. z 커브는 종종 매핑 응용 프로그램에 사용됩니다 : http://msdn.microsoft.com/en-us/library/bb259689.aspx.