[잉여모드] 랜덤 점의 외곽선 찾기

랜덤한 위치의 점 5000개의 가장 외곽선을 이은 도형의 넓이를 구하라.

Debug

회사에서 이야기를 나누다 박차장님이 이전에 풀었던 문제라며 내 주셨던 문제.

며칠 고민하며, 알고리즘도 짜보고 하였으나 박차장님이 풀으셨다는 방법이 가장 효율적으로 보여 박차장님의 알고리즘을 바탕으로 HTML/Javascript로 구현을 해보았다.

박차장님이 구현하였던 방법의 핵심 알고리즘은 다음과 같다.

1. 최상단,최하단,최좌측,최우측 각 1개 씩 총 4개의 점을 구한다.
2. 4개의 점을 기준으로 한 4분면을 만든다.
3. 1사분면 최상단에서 최우측으로 가며 가장 상단의 점을 찾아 n번째 예비 외곽점으로 선정한다.
4. n-2 예비외곽점에서 n 예비 외곽점과 n-1 예비 외곽점을 이은 두 선 중 외곽선을 찾는다.
5. n 예비 외곽점이 n-1 예비외곽점 보다 외곽의 점으로 판별 될 경우 n-1 예비 외곽점을 예비 외곽점에서 제외하고 4번 과정을 반복한다.
6. 2사분면 최우측에서 최하단으로 가며 가장 우측의 점을 찾아 n번째 예비 외곽점으로 선정하고 4~5번을 반복한다.
7. 3사분면 최하단에서 최좌측으로 가며 가장 하단의 점을 찾아 n번째 예비 외곽점으로 선정하고 4~5번을 반복한다.
8. 4사분면 최좌측에서 최상단으로 가며 가장 좌측의 점을 찾아 n번째 예비외곽점으로 선정하고 4~5번을 반복한다.
9. 최종적으로 구한 외곽점을 잇는 도형의 넓이를 구한다.

이 중 9번 넓이를 구하는 부분은 생략하고 외곽선을 구하는 부분까지 구현하였다.
Debug를 체크하고 실행할 경우 하늘색선으로 각 사분면을 구분하고, 녹색 선으로 예비 외곽선에 대해 시도했던 것들을 볼 수 있다.

== 소스보기 ==

구현을 하며, 내 나름대로 추가했던 알고리즘은 외곽선 판별을 위해 사용한 벡터곱의 오른손 법칙.

z 축의 값이 0으로 고정 되어 있는 2차원 공간에서 두 백터의 벡터곱을 구할 경우 값이 양수이냐 음수이냐에 따라 우측 또는 좌측에 있는 선을 구할 수 있다는 점을 착안하여 외곽선을 판별하는데 응용하였다.