두 개의 점이 주어지는 경우 이들을 잇는 가장 단순한 곡선은 직선이다. 또 직선은 두 점을 잇는 가장 짧은 거리를 갖는 곡선이기도 하다. 그러면
특징:
- 주어진 점들 위에서 정의됨(interpolation)
- 국소적인 변동 특성(노이즈에 안정적)
- 일차 미분의 연속성
두 점
이 곡선이
이 조건에서 계수들은
로 주어진다;
그러나 미분 값을 직접 정해서 넣는 것은 문제가 있다.
4 이상의 점들이 주어지는 경우에는 컨트롤상에서의 미분 값을 그 점 주위의 두 점을 있는 직선의 기울기 값으로 근사 시킬 수 있다:
이 미분 값을 사용하면 네 개의 컨트롤 점
로 표현된다. 다시 정리하면
로 쓸 수 있는데, 이는 각각의 입력점 사이 구간에서 매개변수를 이용해서 표현하기 좋은 꼴이다. 만약 매개변수를 knots으로 주어지는 경우는 다음과 같은 형식으로 바꾸어서 사용하는 것이 편리하다.
열린 곡선으로 보간을 하는 경우 처음과 끝 구간에는 미분 값을 구할 수 없으므로 정의가 안되지만, 나머지 구간에서는 주어진 점들을 연결하는 충분히 부드러운 곡선이 된다. 양 끝 구간의 보간은 동일점을 반복함으로써 전체적인 구간에서 잘 정의되게 만들 수 있다(끝점에서 기울기를 그 점과 인접점과의 기울기/2로 잡는 것과 같은 효과임). 닫힌 곡선인 경우에는 모든 구간에서 잘 정의가 된다. Catmull-Rom spline은 Bezier나 B-Spline 곡선의 경우와 다르게 컨트롤 점의 convex hull 내부에서만 정의되는 특성을 따르지 않는다.
CPoint CRSpline(double t, CPoint p1, CPoint p2, CPoint p3, CPoint p4) {
double tt = t * t ;
double ttt = tt * t ;
double x = 0.5 * ((-p1.x + 3 * p2.x - 3 * p3.x + p4.x) * ttt
+ (2 * p1.x - 5 * p2.x + 4 * p3.x - p4.x) * tt
+ (-p1.x + p3.x) * t
+ 2 * p2.x);
double y = 0.5 * ((-p1.y + 3 * p2.y - 3 * p3.y + p4.y) * ttt
+ (2 * p1.y - 5 * p2.y + 4 * p3.y - p4.y) * tt
+ (-p1.y + p3.y) * t
+ 2 * p2.y);
return CPoint(int(x + .5), int(y + .5)) ;
}
//open spline의 drawing;
void DrawCatmullRom(std::vector<CPoint>& Q, CDC* pDC) {
#define STEPS (20)
if (Q.size() < 4) return ;
CPen red(PS_SOLID, 1, RGB(0xFF, 0, 0));
CPen *pOld = pDC->SelectObject(&red);
const int n = Q.size();
for (int i = 0; i < n - 1; i++) {
pDC->MoveTo(Q[i]);
// i = 0 인 경우에는 처음 점을 반복, i = n - 2인 경우에는 마지막 점을 반복..
int ip = max(i - 1, 0);
int inn = min(i + 2, n - 1);
for (int it = 1; it <= STEPS; it++)
pDC->LineTo(CRSpline(double(it)/STEPS, Q[ip], Q[i], Q[i + 1], Q[inn]));
};
pDC->SelectObject(pOld);
}



**네이버 블로그 이전;
'Computational Geometry' 카테고리의 다른 글
삼각형 외접원의 Inclusion Test (1) | 2020.12.30 |
---|---|
Point in Polygon (2) | 2020.12.14 |
Incremental Delaunay Triangulation (1) | 2020.12.01 |
Chain Hull (2) | 2012.09.16 |
Quick Hull (2) | 2012.09.16 |