일련의 점들이 주어졌을 때 서로 가장 멀리 있는 두 점을 어떻게 찾을 수 있습니까?[복제하다]

Question

가능한 중복:
최대 선형 치수 2D 점 집합

각 점 사이의 거리를 계산하고 가장 큰 점을 선택할 수 있지만 점 수가 많을 때(> 1000) 점 수가 있을 때 그렇게 하는 것은 매우 효율적인 방법처럼 들리지 않습니다.

메모:아이폰용이라 처리능력이 부족하네요.

Answer 1

당신은 계산을 요구하고 있습니다 지름 세트의.표준 기술은 먼저 볼록 껍질을 계산하는 것인데, 이는 볼록 다각형의 직경을 찾는 문제를 줄여줍니다.어떤 점도 제거하지 않는 경우에도 이 추가된 정보는 문제를 효율적으로 해결하는 데 꼭 필요한 정보입니다.그러나 볼록 다각형의 지름을 찾는 것은 완전히 쉬운 일이 아닙니다.이 작업에 대한 알고리즘을 포함하는 여러 출판된 논문은 잘못된 것으로 판명되었습니다.

여기 상당히 읽기 쉬운 토론 작업에 대한 올바른 O(n) 알고리즘(여기서 n은 볼록 껍질의 점 수)입니다.

또한, 아이폰은 그렇지 않습니다. 저것 제한된;완전히 순진한 알고리즘이라도 신중하게 작성된 구현은 10분의 1초 이내에 1000개의 포인트를 처리할 수 있습니다.물론, 올바른 알고리즘을 사용하면 훨씬 더 빠르게 작업을 수행할 수 있습니다 =)

Answer 2

왜 계산하지 마십시오 볼록한 선체 포인트의? 에 따라 연산 당신은 사용합니다 O(n) 또는 O(n log n) 고려에서 모든 내부 지점을 시간과 제거합니다. 그런 다음 가장 먼 지점 만 확인하여 가장 먼 곳을 찾으십시오.

Answer 3

가장 낮은 x 코드로 점으로 시작하십시오. (포인트 X를 호출) 지점 X부터 시작하는 "경계 지점"의 구조 세트와 지점을 통해 수직선이 있어야합니다. Pointx의 왼쪽에 다른 지점이 없어야합니다) 라인을 시계 방향으로 천천히 회전시켜 경계에서 다음 지점을 찾으십시오 (또는 반 시계 방향) 라인이 다른 지점에 닿을 때까지 (아래 참조). 그 지점을 세트에 추가하고 다음 지점으로 반복하여 다음 지점을 얻으려면 결국 원래 지점 X로 돌아갈 때까지 다음 점을 얻습니다. NPW에는 전체 세트의 경계를 형성하는 포인트 세트가 있습니다. 이 감소 된 세트에서 각 쌍 사이의 거리를 비교하여 가장 멀리 떨어진 쌍을 찾으십시오.

"라인을 회전시키기 위해"(각 순차적 경계 지점을 찾으려면) 마지막 경계 지점에 사용 된 선에 수직으로 "가장 먼"지점을 가져 와서 마지막 경계 지점과 그 사이의 새로운 선을 구성하십시오. " 다음 "포인트. 그런 다음 해당 새로운 라인에 의해 형성된 새로운 수직 방향에 다른 점이 없는지 확인하십시오. 이 라인에 수직 인 흙에 "Furthur out"이 없다면 다음 경계 지점에 대한 올바른 cjhoice입니다. 그러한 점이 있으면 해당 포인트로 전환하고 다시 테스트하십시오.

Answer 4

보다 이 페이지 ( "다음"링크를 클릭하여 링크 된 페이지와 페이지에 도달 할 수있는 페이지)는 포인트 세트의 볼록 헐의 직경을 계산할 때.

내 빠른 요약 :

1. COMPUTE COMPUTE CONVEX HULL (= O (n log n)의 포인트 세트, O (n)을 얻는 유일한 시간은 O (n log n)를 차지하는 목록을 먼저 정렬하는 것입니다.
2. 경계를 따라 주문하십시오 (사용하는 경우 무료로 제공합니다. 그레이엄 스캔 #1)
3. 직경이 가장 큰 O (N) 직경 알고리즘 중 하나를 사용하여 직경이 가장 큰 항체 지점을 스캔하십시오. 샤모 알고리즘 그것이 하나이기 때문에 나에게 좋아 보인다 회전 캘리퍼 알고리즘.