격자 점 알고리즘 I은 대신에 모든 점 사이의 임의의 거리의 <a href="http://en.wikipedia.org/wiki/Closest_pair_of_points_problem" rel="nofollow">closest pair of points algorithm</a></p> <p>같은 알고리즘을 검색하고

Question

(격자 점을 찾는), I는 4 점 주도로 설정 그리드 시스템을 오른쪽 위, 오른쪽 아래, 오른쪽 위, 왼쪽 위 및 왼쪽 아래에 각각 있습니다. 이것은 모든 점 사이의 거리를 일정하게 유지합니다.

예를 들어이 그리드에 외부 점을 놓을 경우 가장 가까운 4 점 (그리드 스퀘어의 끝점을 지정)을 찾아 가정하면 어떤 그리드 사각형인지 찾아야합니다.

가장 가까운 점에 대한 알고리즘을 구현할 예정 이었지만, 점이 항상 서로 같은 거리에 있기 때문에 항상 다른 점이 더 효율적인 알고리즘이 될지 몰랐습니다.

답변에 대한 자세한 설명은 필요하지 않습니다. 올바른 방향으로의 한 지점입니다.

Answer 1

2 차원이라고 가정합니다. 매우 간단하게이 작업을 수행 할 수있었습니다. 비슷한 기술을 사용하여 대규모 데이터 마이닝 프로젝트에서 공간 클러스터링을 신속하게 최적화했습니다.

좌표 공간을 X 및 Y 방향의 고정 된 수의 그리드 선으로 나눕니다 (이 4 점을 동일하게 간격을두고 이미 작성한 것으로 보입니다).

점을 삽입 할 때 그리드 단계 간격만큼 X 및 Y 방향으로 원점에서 거리 (정수 나누기)를 나눕니다. 그런 다음 가장 가까운 X/Y 그리드 교차점을 식별하는 두 개의 좌표가 있습니다. 나머지 부분을 사용하여 포인트가 속한 그리드 교차점의 측면을 지정하십시오.

정말 복잡해지기를 원한다면 kD- 트리 등을 사용할 수 있습니다. 그러나이 예제는 보증 할만큼 간단하지 않다고 생각합니다. 더 복잡한 공간 분할.