드 카스텔자의 알고리즘

수치해석의 수학적 분야에서 데 카스텔자의 알고리즘은 번스타인 형태나 베지에 곡선으로 다항식을 평가하는 재귀적 방법으로, 발명가 폴 드 카스텔자의 이름을 따서 명명했다.드 카스텔자의 알고리즘은 또한 임의 파라미터 값에서 하나의 베지어 곡선을 두 개의 베지어 곡선으로 분할하는 데 사용될 수 있다.

알고리즘은 대부분의 아키텍처에서 직접 접근에 비해 느리지만, 수치적으로 더 안정적이다.

정의

Bézier 곡선 $B{\displaystyle }$ ${\displaystyle$ $B}($제어점 ${\displaystyle {\beta \mathrm{}}_{}}$ 0${\displaystyle {}_{}}$,${\displaystyle }$… ,${\displaystyle <img\; alt="n"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b"\; style="vertical-align:\; -0.338ex;\; width:1.395ex;\; height:1.676ex;"\; papago-attr-id="34">{}_{}}$ ${\displaystyle n_{}}$ ${\$는 다음과 같이 번스타인 형태로 작성할 수 있다$.$

${\displaystyle B(t)=\sum _{i=0}^{n}\베타 _{i}b_{i,n}(t),}$

여기서 $b{\displaystyle }$ ${\displaystyle b}$은(는) 번스타인 기반 다항식이다.

${\displaystyle b_{i,n}(t)={n \선택 i}(1-t)^{n-i}t^{i}.}$

점 $t{\displaystyle {}_{}}$ ${\$의 곡선은 반복 관계를 사용하여 평가할 수 있다$$.

${\displaystyle \property_{i}^{(0)}:=\properties _{i}\\ i=0,\ldots,n}$

${\displaystyle \property_{i}^{(j)}=\i}^{{i-1)}}+++++++_{i+1}^{i+1}^{i-1}{0}\ \i=0,\ldots,\j=1,\ldots,n}$

${\displaystyle 그런\genfrac{}{}{0ex}{}{}{}}$ 다음${\displaystyle }$지점 $t{\displaystyle {}_{}}$ ${\displaystyle 0_{}}$에서 $B{\displaystyle }$${\$의 평가는 (${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ 2) {\$displaystyle {\binom{n}{2$}}회$$ 작동에서 평가할 수 있다$$${\displaystyle .}$결과 $B{\displaystyle }$( ${\displaystyle {t\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$) ${\displaystyle B(t_{0})$는 다음에 의해 제공됨$$

${\displaystyle B(t_{0}}=\beta _{0}^{n}}}}$

또한 Bézier 곡선 $B{\displaystyle }$ ${\displaystyle B}$은(는) 지점 ${\displaystyle {t\mathrm{}}_{}}$ 0 ${\$에서 두 개의 곡선으로 분할할$$ 수 있으며$$, 각 제어점은 다음과 같다.

${\displaystyle \property_{0}^{0}^{0}},\ldots,\ldots,\ldots _{0}^{n}}}}}}$

${\displaystyle \property_{0}^{{0}^{(n)},\ldots,\ldots,\ldots _{n}^{n}^{0)}}}}$

구현 예

하스켈에서 De Casteljau 알고리즘의 구현 예는 다음과 같다.

데카스텔자우 :: 더블 -> [(더블, 더블)] -> (더블, 더블) 데카스텔자우 t [b] = b 데카스텔자우 t 코에프스 = 데카스텔자우 t 감소된   어디에     감소된 = zipWith (LerP t) 코에프스 (꼬리를 치다 코에프스)     LerP t (x0, y0) (x1, y1) = (리퍼프 t x0 x1, 리퍼프 t y0 y1)     리퍼프 t a b = t * b + (1 - t) * a 

Python에서 De Casteljau 알고리즘의 구현 예:

반항하다 de_casteljau(t, 코에프스):     베타. = [c 을 위해 c 에 코에프스] # 이 목록의 값이 재정의됨     n = 렌(베타.)     을 위해 j 에 범위(1, n):         을 위해 k 에 범위(n - j):             베타.[k] = 베타.[k] * (1 - t) + 베타.[k + 1] * t     돌아오다 베타.[0] 

JavaScript에서 De Casteljau 알고리즘의 구현 예:

인접 지점에 선형 보간법을 재귀적으로 적용하여 얻은 중간 선 세그먼트.

// 예: lerp(0.5, 0.0, 1.0) == 0.5 하게 하다 리퍼프 = (t, p1, p2) => (1 - t) * p1 + t * p2;  // 예: 감소(0.5, ...)[0.0, 1.0, 2.0, 3.0]) == [0.5, 1.5, 2.5] 하게 하다 줄이다 = (t, p1, p2, ...ps) => ps.길이 > 0     ? [리퍼프(t, p1, p2), ...줄이다(t, p2, ...ps)]     : [리퍼프(t, p1, p2)];  // 예: deCasteljau(0.5, [0.0, 1.0, 2.0, 3.0]) == 1.5 하게 하다 데카스텔자우 = (t, ps) => ps.길이 > 1     ? 데카스텔자우(t, 줄이다(t, ...ps))     : ps[0]; 

메모들

손으로 계산을 할 때 계수를 삼각형 구조로 다음과 같이 적는 것이 유용하다.

${\displaystyle{\begin{행렬}\beta _{0}&,=\beta _{0}^{(0)}&,&&\\&, &, \beta _{0}^{(1)}&, &, \\\beta _{1}&,=\beta _{1}^{(0)}&,&&\\&,&&\ddots, \\\vdots & &,&\vdots &,&\beta _{0}^{(n)}\\&,&&&\\\beta _{n-1}&,=\beta _{n-1}^{(0)}&,&&\\&, &,\beta _{n-1}^{(1)}.&&\\\beta _{n}&,=\beta _{n}^{(0)}&,&&\\\end{매트릭스}}}$

번스타인 다항식을 평가하기 위해 점 t를₀ 선택할 때, 우리는 삼각형 구조의 두 대각선을 사용하여 다항식의 분열을 구성할 수 있다.

${\displaystyle B(t)=\sum _{i=0}^{n}\b}b_{i,n}(t),\quad t\in [0,1]}$

로

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}\b_{i,n}\left({t}{0}}\right)\!,\quad t\in [0,t_{0}}}}}}$

그리고

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}\b_{i,n}\{i,n}\좌측({\frac {t-t_{0}}{0}}\오른쪽)\!,\\quad t\in [t_{0},1]}$

예

우리는 번스타인의 다항식 2를 번스타인의 계수로 평가하고자 한다.

${\displaystyle \cHB_{0}^{0}=\cHB_{0}}}$

${\displaystyle \cHB_{1}^{{1}=\cHB_{1}}$

${\displaystyle \property_{2}^{0}=\properties _{2}}:$

t₀ 지점에서

재귀는 다음과 같이 시작한다.

${\displaystyle \property_{0}^{0}=\properties _{0}}{0}}++{0}{1}^{0}{1}^{0}=\property_{1}{1}t_{0}+}}{1}t_{0}}}}}}}}.$

${\displaystyle \property_{1}^{1}^{(1)=\propert_{0}+_{1}^{1}^{0}}+_{2}^{{0}}=\propert_{1}(1-t_{0}})+\pair _{2}$

그리고 두 번째 반복과 함께 반복은

${\displaystyle {\begin{aligned}\beta _{0}^{(2)}&=\beta _{0}^{(1)}(1-t_{0})+\beta _{1}^{(1)}t_{0}\\\ &=\beta _{0}(1-t_{0})(1-t_{0})+\beta _{1}t_{0}(1-t_{0})+\beta _{1}(1-t_{0})t_{0}+\beta _{2}t_{0}t_{0}\\\ &=\beta _{0}(1-t_{0})^{2}+\beta _{1}2t_{0}(1-t_{0})+\beta _{2}t_{0}^{2}\end{aligned}}}$

2등급의 번스타인의 예상 다항식이다.

베지에 곡선

A 베지에 곡선

n + 1 제어점을 갖는_i 3차원 공간에서 n 도 n의 베지어 곡선을 평가할 때

${\displaystyle \mathbf {B}=\sum _{i=0}^{n}}\mathbf {P} _{i}b_{i,n(t),\ t\in [0,1]}$

와 함께

${\displaystyle \mathbf {P} _{i}:={\pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix},}$

우리는 베지어 곡선을 세 개의 개별 방정식으로 나누었다.

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t),\ t\in [0,1]}$

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t),\ t\in [0,1]}$

${\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t),\ t\in [0,1]}$

드 카스텔자의 알고리즘을 사용하여 개별적으로 평가한다.

기하학적 해석

De Casteljau의 알고리즘의 기하학적 해석은 간단하다.

• 제어점 $P{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$. .${\displaystyle }$, P ${\displaystyle n_{}}$ ${\$}, $...,P_{n}}}$을(를) 가진 베지어 곡선을 고려하십시오$.$ 연속된 점들을 연결하면 곡선의 제어 폴리곤이 생성된다.
• 이 폴리곤의 각 선 세그먼트를 비율 $t{\displaystyle }$:${\displaystyle }$( (${\displaystyle 1}$ -${\displaystyle }$t ) ${\displaystyle t:(1-t)}$과(와)로 세분화하고 얻은 점을$$ 연결하십시오.이렇게 하면 세그먼트가 한 개 줄어든 새로운 다각형에 도달할 수 있다.
• 단일 지점에 도달할 때까지 프로세스를 반복하십시오. 이 점이 파라미터 $t{\displaystyle }$ ${\displaystyle t}$에 해당하는 곡선의 지점입니다$.$

다음 그림은 큐빅 베지어 곡선에 대한 이 과정을 보여준다.

생성된 중간 지점은 사실 두 개의 새로운 베지어 곡선에 대한 제어 지점이며, 둘 다 이전 지점과 정확히 일치한다는 점에 유의하십시오.이 알고리즘은 $t{\displaystyle }$ ${\displaystyle t$에서 곡선을 평가할 뿐만 아니라 $t{\displaystyle }$ ${\displaystyle t$에서 곡선을 두 조각으로 나누고, 베지어 형태로 두 개의 하위곡선의 방정식을 제공한다.

위에 주어진 해석은 비합리적 베지어 곡선에 유효하다.To evaluate a rational Bézier curve in ${\displaystyle \mathbf {R} ^{n}}$, we may project the point into ${\displaystyle \mathbf {R} ^{n+1}}$; for example, a curve in three dimensions may have its control points ${\displaystyle \{(x_{i},y_{i},z_{i})\}}$ and weights ${\displaystyle \{}$${\displaystyle \{w_{i}\}}$ projected to the weighted control points ${\displaystyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}}$. The algorithm then proceeds as usual, interpolating in ${\displaystyle \mathbf {R} ^{4}}$.그 결과로 나온 4차원 점들은 원근분할로 다시 3공간으로 투영될 수 있다.

일반적으로 합리적 곡선(또는 표면)에서의 연산은 투영 공간에서 비합리적 곡선에서의 연산과 동일하다.이러한 표현은 "가중 조정점"과 가중치로 표현하면 합리적인 곡선을 평가할 때 편리할 때가 많다.

참고 항목

• 베지어 곡선
• 드보어의 알고리즘
• 다항식을 단항식으로 평가하기 위한 호너 계획
• 체비셰프 형태의 다항식 평가를 위한 Clenshaw 알고리즘

참조

• 패린, 제럴드 & 한스포드, 다이앤(2000년)CAGD의 필수품.Natic, MA: A K Peters, Ltd. ISBN1-56881-123-3

외부 링크

• Bézier 곡선의 조각 선형 근사치 – 리큐^{[check spelling]} 정지 시점을 결정하는 기준을 포함하여 De Casteljau의 알고리즘에 대한 설명
• 베지어 커브와 피카소 — 큐빅 베지어 커브에 적용된 드 카스텔자의 알고리즘에 대한 설명과 삽화.
• [ 대수적 미적분 및 dCB 곡선 ] — YouTube - Polynumber and de Casteljau Bezier 곡선 N J Wildberger
• de Casteljau의 알고리즘 - 구현 도움말과 알고리즘의 대화형 시연.