개념
임의의 다각형 또는 꺾인 선을 그릴때 날카로운 꼭지점을 부드럽게 표현할 때 사용할 수 있는 알고리즘이다.
1974년 유타 주립대의 George Chaikin이 만든 알고리즘으로, 점과 점 사이 거리의 비율로 새로운 점을 생성하여 해당 점들로 선들을 다시 이어주는 방식을 사용해서 모서리를 깎아나가는 방식이다.
해당 알고리즘을 거치는 횟수가 많아지면 곡선이 부드러워지지만, 횟수가 많아질수록 새로 생성되는 점이 많아 처리 속도가 느려질 수 있는 단점이 존재한다.
또한 기존에 존재하던 꼭지점을 지나지 않기 때문에 꼭지점을 반드시 지나야 하는 경우에는 사용할 수 없다.
풀이
임의의 다각형 또는 꺾인 선을 이루고 있는 점 중에서 2점을 연결한 직선을 그리고, 해당 직선상의 거리비율로 새로운 점을 생성한다. 기본 체이킨의 방식은 1/4 비율로 선을 나누게 된다.
선을 나누면 아래의 식으로 Q점과 R점을 나타낼 수 있다.
해당 과정을 모든 선에 대해서 실시하고, 새로 생긴 점들을 연결해주면 한번의 Chaikin 알고리즘이 완료된다. 이때 꺾인 선의 경우 시작점과 끝점이 사라지기 때문에 따로 추가하여 연결해주는 것이 좋다.
Chaikin 알고리즘은 많이 실시할수록 부드러운 곡선의 형태로 변화하지만 점의 수가 많아져 연산에 무리가 생길 수 있다.
폐합된 다각형의 경우 한 번 Chaikin 알고리즘을 거칠때마다 2배씩 늘어나며
꺾인 선은 한 번 Chaikin 알고리즘을 거칠때마다 시작점과 끝점을 제외한 지점들이 2배씩 늘어난다.
또한 기본적으로 비율은 1/4이지만 분모가 커질수록 원래의 모습을 최대한 유지하면서 부드러운 곡선을 생성하고, 분모가 작아질수록 원래의 모습보단 최대한 걸림이 없는 곡선을 생성한다.
'잡동사니 > 기하학' 카테고리의 다른 글
| 직선과 원이 만나는 지점의 좌표 구하기 (0) | 2023.02.18 |
|---|---|
| 한 점에서 직선에 가장 가까운 좌표 구하기 (0) | 2023.02.18 |
| 한 직선에 수직인 직선의 기울기 (0) | 2023.02.18 |
| 2점을 지나는 직선의 방정식 (0) | 2023.02.15 |
| 3점을 지나는 원의 방정식 (0) | 2023.02.15 |
댓글