가장 가까운 포인트 쌍 알고리즘 변형

Question

이 코드는 중복 코드 일 수 있지만 '가장 가까운 포인트 쌍'알고리즘의 변형처럼 보입니다.

그들 사이의 거리가 최대 D되도록 포인트 모든 쌍을 찾아 N 단위 사각형 점 (X, Y)과의 거리 D의 집합이 주어.

큰 경우 N 무차별 법은 선택할 수 없습니다. 'sweep line'과 'divide and conquer'방법 외에 간단한 해결책이 있습니까? 이러한 점들의 쌍은 방향이없는 그래프의 모서리입니다.이 그래프는 트래버스하고 연결되어 있는지 여부를 나타냅니다 (이미 DFS를 사용했지만 N = 100만으로 끝나지 않았습니다).

모든 의사 코드, 의견 또는 아이디어 환영합니다, 감사!

편집 : 나는 세지 책 (내가 지금의 코드를 찾고 있어요)에서 이걸 발견 :

프로그램 3.18로 프로그램 3.7의 실행 시간을 개선하기 위해 연결리스트의 2 차원 배열을 사용하여 N이 충분히 클 때 약 1/d2의 계수. 유닛 을 같은 크기의 작은 사각형의 격자로 정사각형으로 나눕니다. 그런 다음 각 사각형에 대해 해당 사각형에 속하는 모든 지점의 연결된 목록을 작성합니다. 2 차원 배열은 주어진 점에 가까운 점들의 집합을 즉시 에 액세스 할 수있는 기능을 제공합니다. 연결된 목록은 포인트를 저장할 수있는 유연성을 제공합니다. 각 격자 사각형에 몇 포인트가 떨어지는 지 미리 알 필요없이 떨어질 수 있습니다.

Answer 1

우리는 중심 (x, y)과 반지름 d의 원 안에있는 점을 찾고 있습니다.

이 인 동그라미는 중심 (x, y)의 정사각형과 측면 2d입니다. 이 스퀘어에서 벗어난 점은 체크 할 필요가 없습니다. 따라서 abs (xa - x)> d 또는 abs (ya - yb)> d 일 경우 점 a (xa, ya)가 나옵니다.

와 동일한 것은인데 그 원은 중심 (x, y)의 정사각형이고 대각선은 2d입니다. 이 사각형에서 벗어난 점은 체크 할 필요가 없습니다. 그래서 abs (xa-x) < (d * 1.412) 또는 abs (ya -yb) < (xa, ya) d * 1.412).

두 가지 간단한 규칙을 결합하면 검사 할 점수가 많이 줄어 듭니다. 포인트를 x로 정렬하고, 가능한 포인트를 필터링하고, y로 정렬하면, 실제 거리를 계산하는 데 정말로 필요합니다.

Answer 2

주어진 점에 대해 맨하탄 거리 (x-delta + y-delta) 추론을 사용하여 거리 "d"내에 있지 않은 대부분의 지점을 필터링 할 수 있습니다. 즉, 맨하탄 거리가 (sqrt (2) * d)보다 크면 나머지 점들에 대해 비싸고 정확한 거리 테스트를 실행하십시오.