대략 1,600,000 포인트를 가지고 Triangulation를 해보았는데 3분이 좀 넘게 걸렸다.
테스트환경은 다음과 같다.
CPU : Core2Duo 2.4GHz
RAM : 2G
O/S : Windows Vista Ultimate 64b
container를 vector, list, set등을 이용하였는데 MemoryPool를 이용하니 알고리즘 수정없이도 3분에서 1분으로 줄어들었다. 거기다가 알고리즘을 약간 더 개선해서 지금은 40초정도 걸린다. 밤샌 보람이 ^^
하지만 자세히 DT에 대해서 찾아보니 알고리즘이 3가지가 있다.
1. Incremental, 2. Divide and Conquer, 3.Sweepline
내가 사용한 알고리즘은 Incremental이다. 아마 제일 느린 방법같다. 다른 자료를 찾아보니 Divide and Conquer방법이 상당히 빠른것 같다. 이 알고리즘으로 다시 구현해봐야 겠다.
Posted by chungki
