| [ QuizWit ] in KIDS 글 쓴 이(By): valken (> 아슈람 <) 날 짜 (Date): 1998년 6월 6일 토요일 오후 05시 14분 37초 제 목(Title): Re: geometry 5. A---B\ F---G | C | \H E---D/ J---I/ 0. 두개의 볼록다각형이 겹치지 않는다고 가정합니다.. 1. 일단.. 컨벡스 폴리곤은 각 점들을 순서를 매길수 있습니다.. (반드시) 컨벡스 폴리곤의 중심(무게중심?)을 기준으로 시계방향으로 순서를 매기면 됩니다.. 첫번째 폴리곤의 경우 A-B-C-D-E 의 순서.. 두번째 폴리곤의 경우 F-G-H-I-J 의 순서.. 이 순서는 하나의 폴리곤에 대해서 unique 하게 존재한다고 가정해도 됩니다. 원순열 과 반대 방향의 순열은.. 같다고 가정해 버리죠.. ^^! 2. 두 폴리곤 사이의 거리는 다음 두가지 경우만 존재 합니다.. a. 점과 점이 최소 거리가 되는 경우. b. 점과 모서리가 최소 거리가 되는 경우.. b의 경우는 위의 그림과 같은 경우이고,, a 의 경우는 뻔한거죠.. 또, 한가지..모서리와 모서리가 최소거리가 되는 경우도 있는데.. 이 것은 두 모서리가 평행한 경우이고, 이는 b 또는 a 로 바뀌어집니다. 3. 일단.. 두 폴리곤을 1번과 같은 순서로 sorting 합니다.. --> O(MlogM + NlogN) 4. 그럼 시작점인 A 와 F 가 나오고,, 이 둘의 거리를 구합니다.. A 의 앞뒤인 B 와 E, F 의 앞뒤인 G J 에 대해서.. A~G, A~J, B~F, E~F 의 거리를 구합니다.. 이중 가장 작은 것을 골라서 현재 거리 A~F 보다 작다면 선택합니다. 이 과정을 더이상 작아지지 않을 때까지 반복합니다.. 그러면 두 폴리곤 사이에 가장 가까운 두 점이 구해집니다.. 위 그림이라면., C~F 또는 C~J 가 선택되겠죠.. --> O(M + N) 에 수행이 가능합니다.. 5. 그 두개의 점에 접한 4개의 모서리를 찾습니다.. 이 경우, CB, CD, FG, FJ 가 되겠죠.. 그리고 두 점과 반대편의 두 모서리와의 거리를 각각구합니다. C~FG, C~FJ, F~CB, F~CD 계산이 복잡하게찌만.. constant time 에 계산가능합니다.. 6. 두 점과의 거리, 두점과 모서리와의 거리중.. 최소값이.. 두 폴리곤의 최소거리입니다.. MIN(C~F, C~FG, C~FJ, F~CB, F~CD) 위 그림과 같은경우 C~FJ 가 되겠죠.. 7. 적절한 증명이 필요하겠지만.. 저는 그런거 몰라요,. ^^! 8. 정렬되어 있다면.,. O(M+N) 이고.. 그렇지 않다면.. O(MlogM + NlogN) 이겠죠.. - 아슈람 - - Valken the SEXy THief~~ ^_* - |