드보어의 알고리즘

수치해석 de Boor 알고리즘의^[1] 수학적 하위분야에서 B-spline 형태의 스플라인 곡선을 평가하기 위한 다항 시간 및 수적으로 안정된 알고리즘이다.베지에 커브에 대한 데 카스텔자의 알고리즘을 일반화한 것이다.알고리즘은 칼 R. 드 보어가 고안했다.단순하고 잠재적으로 빠른 de Boor 알고리즘 변형이 만들어졌지만 비교적 낮은 안정성으로 어려움을 겪고 있다.^[2][3]

소개

B-스플라인에 대한 일반적인 소개가 본문에 실려 있다.여기서는 위치 $x{\displaystyle }$ ${\displaystyle x}$에서 스플라인 곡선 $S{\displaystyle \mathbf{}(x}$) ${\displaystyle \mathbf {S}(x)}$을(를) 평가하기 위한 효율적이고 수치적으로 안정적인 체계인 de Boor 알고리즘에 대해 논한다$.$곡선은 B-spline 함수 $B{\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle p{}_{}}$( ${\displaystyle x_{}}$) ${\displaystyle B_{i,p}(x)}$에 잠재적으로 벡터 값 상수 $c{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$를 곱한 총합에서 생성되며$,$ 이를 제어점이라고 한다.

${\displaystyle \mathbf {S}=\sum _{i}\mathbf {c} _{i}B_{i,p}(x)}$

순서 $p{\displaystyle }$+ ${\displaystyle 1}$의 B-스플라인(B-splines of$$order$$p + 1 {\$displaystyle$ p+$$1$})$은 ${\displaystyle {매듭\mathrm{}}_{}}$t 0${\displaystyle ,}$ …, ${\displaystyle t_{}{}_{},}$ …, t ${\displaystyle m_{}}${$t_{0},\dots, t_{m}}($우리는 항상 다음에서$$ $0{\displaystyle }$기반 $인덱스$를 사용한다.De Boor의 알고리즘은 O(p²) + O(p) 연산을 사용하여 스플라인 곡선을 평가한다.참고: B-스플라인과 고전 출판물에^[1] 대한 주요 기사는 다른 표기법을 사용한다: B-스플라인(B-spline)은 b-spline(B-spline)은 ${\displaystyle {b-i,}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {}_{}x}$ ${\displaystyle )}$ ${\displaystyle B_{i,n(x)}$과 n${\displaystyle }$= ${\displaystyle \mathrm{p}}$+ 1 ${\displaystystyle n=p+1}$로 색인화된다$.$

현지 지원

B-분할은 국부적인 지지를 가지고 있는데, 이는 다항식이 유한한 영역에서만 양이고 다른 영역에서는 0이라는 것을 의미한다.Cox-de Boor 재귀 공식은^[4] 다음을 보여준다.

${\displaystyle B_{i,0}(x):={\cHB{case}1&{\text}{}}}\req x<t_{i+1}\0&{\text}}\end{case}}}}$

${\displaystyle B_{i,p}(x):={\frac {x-t_{i}}{t_{i+p}-t_{i}B_{i-1}{i-1}(x)+{\frac {t_{i+p+1}-x}{t_{i+p+1}-{i+1}-1}B_{i+1}.}$

Let the index ${\displaystyle k}$ define the knot interval that contains the position, ${\displaystyle x\in [t_{k},t_{k+1})}$. We can see in the recursion formula that only B-splines with ${\displaystyle i=k-p,\dots ,k}$ are non-zero for this knot interval.따라서 총액은 다음과 같이 감소한다.

${\displaystyle \mathbf {S}=\sum _{i=k-p}^{k}\mathbf {c} _{i}B_{i,p}(x)}$

${\displaystyle k}$${\displaystyle 0}$ ${\displaystyle i\geq$ 0$}$에서 k$$ ${\displaystyle \ge }$ p ${\displaystyle k\geq$ p$}$을(를) 따르며$,$ 마찬가지로, 재귀에서 쿼리된 가장 높은 매듭 위치가 $인덱스{\displaystyle }$k +${\displaystyle 1}$ + ${\displaystyle p}$ ${\displaysty k+1+p}$임을 알 수 있다$.$즉, 실제로 사용되는 매듭$$ 간격${\displaystyle }$[${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle t_{}}$ k${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$) ${\displaystyle [t_{k},t_{k+1}}}$은(는) 전후에 최소한 $p{\displaystyle }$ ${\displaystyle p}$개의$$ 추가 노트가 있어야 함을 의미한다.컴퓨터 프로그램에서 이는 일반적으로 처음 사용한 매듭 위치 $p{\displaystyle }$ ${\displaystyle p}$번$$ 반복함으로써 달성된다.예를 들어, ${\displaystyle \mathrm{p}}$= 3 ${\displaystyle p=3}$ 및$$ 실제 매듭 위치$({\displaystyle 0}$${\displaystyle ,}$ ${\displaystyle 1}$,$$) ${\$$displaystyle$$$($0,$0,0$,0$2,$2)$에 매듭 벡터를 패딩한다$.$

알고리즘

이러한 정의로 우리는 이제 드 보어의 알고리즘을 설명할 수 있다.알고리즘은 B-spline 함수 $B{\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle p{}_{}}$( x${\displaystyle }$) ${\displaystyle B_{i,p}(x)}$을(를) 직접$$ 계산하지 않는다.대신 등가 ${\displaystyle \mathrm{반복}}$ 공식을 통해$$ $S{\displaystyle \mathbf{}}$( x${\displaystyle }$) ${\displaystyle \mathbf {S}(x)}$을(를) 평가한다.

Let ${\displaystyle \mathbf {d} _{i,r}}$ be new control points with ${\displaystyle \mathbf {d} _{i,0}:=\mathbf {c} _{i}}$ for ${\displaystyle i=k-p,\dots ,k}$. For ${\displaystyle r=1,\dots ,p}$ the following recursion is applied:

${\daystyle \mathbf {d} _{i,r}=(1-\mathbf _{i,r}\mathbf {d} _{i-1}+\i,r-1}\mathbf {d} _{i,r-1};\mathbf i=k-p+r,\k}$

${\displaystyle \cHB_{i,r}={\frac {x-t_{i}{t_{i+1+p-r}-t_{i}}}}.}$

반복이 완료되면 $S{\displaystyle \mathbf{}(}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle d_{}}$ ${\displaystyle {\mathbf{}}_{}}$, p ${\$ $\$$mathbf {S}(x)=\$$mathbf$${d}$$_{k,p$$\},$ ${\displaystyle {,}_{}}$p$}$가 원하는$$ 결과임을 의미한다.

De Boor의 알고리즘은 Cox-de Boor 재귀 공식으로$$ B-splines $B{\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle p{}_{}}$( x${\displaystyle }$) ${\displaystyle B_{i,p}(x)}$을 명시적으로 계산하는 것보다 더 효율적이다. 왜냐하면 그것은 0으로 곱할 것을 보장되는 항을 계산하지 않기 때문이다.

최적화

위의 알고리즘은 컴퓨터에서의 구현에 최적화되어 있지 않다.$({\displaystyle p}$+ ${\displaystyle 1}$)${\displaystyle }$+ p +${\displaystyle \cdots }$+ ${\displaystyle 1}$=${\displaystyle }$( ${\displaystyle p}$+ ${\displaystyle 1}$) (${\displaystyle p\mathrm{}}$+ 2${\displaystyle }$)${\displaystyle }$/ 2 ${\displaystyle (p+1)+p+++\dots +1=(p+1)/$2} 임시 $제어 지점$ ${\displaystyle {}_{}}$ i , r${\$ . 각 임시 제어 지점은 정확히 한 번 읽고 두 번 기록된다$.$$i{\displaystyle }$ ${\displaystyle i}$에 대한 반복을 반대로 하여($$위로가 아니라 카운트다운됨) $p{\displaystyle }$ +${\displaystyle 1}${\$displaystyle p+1$} 임시$$ 제어 지점에 대한 메모리로 알고리즘을 실행할 수 $있으며{\displaystyle {\mathbf{}}_{}}$${\displaystyle {,}_{}}$ ${\displaystyle {}_{}}$${\displaystyle i_{}}$${\displaystyle {,}_{}}$ r ${\$${\$ \$mathbf {d} _$$i,$$r-1$$}$에 대한 메모리를 재사용할$$ 수 있다.마찬가지로 각 단계에서 사용되는$$ $\alpha {\displaystyle }$ ${\displaystyle \alpha }$의 값만 있으므로 메모리도 재사용할 수 있다.

또한 임시 제어 지점에는$$ ${\displaystyle 0}$ 기반 $인덱스{\displaystyle }$ j${\displaystyle }$= ${\displaystyle 0}$,${\displaystyle }$…${\displaystyle }$, p ${\displaystyle j=0,\dots ,p}$을(를) 사용하는 것이 더 편리하다.이전 지수와의 관계는 $i{\displaystyle }$= j${\displaystyle }$+ ${\displaystyle k}$ -${\displaystyle p}$ ${\displaystyle i=j+k-p}$이다$.$ 따라서 향상된 알고리즘을 얻는다.

$d{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle :=}$ ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle k_{}}$ -${\displaystyle p_{}}$ ${\$$=\mathbf {c} _{j+k-p}$ for$$ $j{\displaystyle }$= ${\displaystyle 0,}$ ${\displaystyle \dots ,}$ ${\displaystyle p}$ ${\displaystyle j=0,\dots,p$ $r{\displaystyle }$= ${\displaystyle 1,}$…,$$ {\$displaystyle r=1,\dots,p}$에 대해 반복한다$.$

${\displaystyle \mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad }$ (${\displaystyle j}$ must be counted down)

${\displaystyle \filename _{j={\frac {x-t_{j+k-p}{t_{j+1+k-r}-t_{j+k-p}}}.}$

반복이 완료되면 결과는 $S{\displaystyle \mathbf{}}$ (${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {}_{}}$ p ${\$ 입니다$.$

구현 예

파이톤 프로그래밍 언어의 다음 코드는 최적화된 알고리즘의 순진한 구현이다.

반항하다 드보어(k: 인트로, x: 인트로, t, c, p: 인트로):     """"S(x)를 평가한다.  논쟁들 --------- k: x를 포함하는 매듭 간격의 색인. x: 위치. t: 매듭 위치 배열, 위에서 설명한 대로 패딩해야 한다. c: 제어점의 배열. p: B-분할 정도. """     d = [c[j + k - p] 을 위해 j 에 범위(0, p + 1)]      을 위해 r 에 범위(1, p + 1):         을 위해 j 에 범위(p, r - 1, -1):             알파의 = (x - t[j + k - p]) / (t[j + 1 + k - r] - t[j + k - p])             d[j] = (1.0 - 알파의) * d[j - 1] + 알파의 * d[j]      돌아오다 d[p] 

참고 항목

• 드 카스텔자의 알고리즘
• 베지에 곡선
• NURBS

외부 링크

• 드보어의 알고리즘
• DeBoor-Cox 계산

컴퓨터 코드

• PPPACK: Fortran의 많은 스플라인 알고리즘 포함
• GNU 과학 라이브러리: C-도서관, PPPACK에서 포팅된 스플라인용 하위 도서관이 있음
• SciPy: Python-library, 서브라이브러리 scipy를 포함하고 있다.FITPACK을 기반으로 스플라인 함수로 보간
• TinySpline: C++ 래퍼가 있는 스플라인용 C-library와 C#, Java, Lua, PHP, Python, Ruby용 바인딩
• 아인스플라인: 포트란 포장지로 1, 2, 3차원의 스플라인용 C-도서관

참조

인용된 작품

• Carl de Boor (2003). A Practical Guide to Splines, Revised Edition. Springer-Verlag. ISBN 0-387-95366-3.