261
2015-08-08 10:54:09
0
재미있어 보이네영
개념적으로 어떻게 하면 될까 생각해보면
1.시작점 설정 - 2. 다음점을 조건에 맞는것을 검색 - 3. 외곽조건에 최대한 만족 하는 다음점을 연결 - 2-3 의 반복, 마지막 점 까지 하면 끝.
1. 시작점 설정 조건
- 조건 : 최대한 외부에 있는 점
- 원리 : XY 축 을 기준으로 가장 가까운것 (각 점의 좌표를 기준으로, 공식을 세웁니다.
공식 : (100*100 에서 가정하면) (5 , 5) (95 , 5) (5 , 95) (95 , 95) 의 점의 위치는 같습니다. 즉, 좌표상 가장 구석에서, 거리가 가까운놈을 찾는것이죠.
2~3. 시작점에서 조건에 맞는 다음 연결점을 찾고 연결
- 조건 : 최대한 점을 지나가는 겉도는 경로만들기 = 최대한 바깥쪽 점.
- 원리 : 각 점들과 이 점의 각도를 찾기.
if : 여기서 부터 방향 및 각도가 중요.
- 공식 : 시작점에서 각 점들 과의 각도 찾기. (삼각함수에 관련되겟네요. 관련 라이브러리 참조해야할듯) 그중에서 가장 높은것 vs 낮은것을 설정하고 연결. (그리고 연결한 포인트는 리스트에서 삭제)
(여기서 부터는 높은것을 사용했다는 가정을 하겟습니다.)
∞. 연결점 재검색 - 연결. . .
- 공식 : 다시 점을 검색 합니다. 하지만, 이때 이 전에 찾았던 각도의 값을 기준으로 해서 그 다음으로 낮은 점을 찾아 연결 합니다. (만약, 이전의 점을 연결 할때, 90도위치의 점을 찾아 연결 했다면, 다음 점은 90도 아래의 값 중에서 다음으로 가까운 걸 연결 합니다.
4. 마지막 점 까지 찾으면 END