ベジエクリッピング法の仕組み ― 有理曲線と非有理曲線で次数はなぜ変わるのか

「有理ベジエ曲線同士の最短点」ツールの中で解いている (3n−1) 次 という次数は、どこから出てきたのか。本稿ではベジエクリッピング法そのものの原理と、非有理（多項式）ベジエ曲線と有理ベジエ曲線とで判定関数の次数がどう変わるのかを、順を追って説明する。

解きたい問題：曲線上の「垂直に落ちる点」を探す

2 つの曲線の最短点を求める問題は、最終的には次のような1変数（または2変数）の方程式の根を求める問題に帰着する。

g(t) = 0　　（例：距離関数の微分、あるいは接線とのなす角がゼロになる条件）

ニュートン法で解く方法は昔からあるが、初期値の与え方によって局所解に落ちたり、発散したりする問題がある。ベジエクリッピング法（Sederberg & Nishita, 1990）は、 g(t) がベジエ関数として表現できるという前提のもと、初期値を必要とせず、ロバストに根を求められる幾何学的な手法である。

凸包性質（convex hull property）

ベジエ関数の最大の特徴は、その関数のグラフが、制御点を頂点とする 制御多角形の凸包の内側に必ず収まるという性質である。したがって、制御多角形の凸包が横軸（y=0）と交わらなければ、その区間には根が存在しないと即座に判定できる。逆に交わる場合は、交わる範囲の中にしか根はあり得ない。

黒線が g(t)、オレンジの点と破線が制御多角形、青く塗った領域がその凸包。凸包が y=0 と交わる区間（オレンジの帯）の外側には根が存在しない。この帯の左右端を新しい端点として曲線を分割し直し（部分ベジエへの変換）、同じ判定を繰り返すことで区間はどんどん狭まり、最終的に根 1 点に収束する。

「制御多角形の削り」を1回行うごとに、区間の縮小率は関数の形状によって変わるが、経験的にはニュートン法よりずっと少ない反復回数（1桁程度）で収束する。また、区間があまり縮まらない場合（凸包内に複数の根がある可能性が高い場合）は、区間を半分に分割して両方を独立に処理すれば、複数の根も取りこぼさず検出できる。「有理ベジエ曲線同士の最短点」ツールの右側パネルで見えている入れ子状の矩形は、まさにこの絞り込みが (t, s) の2変数空間で繰り返される様子である。

非有理ベジエと有理ベジエで、なぜ次数が変わるのか

ベジエクリッピング法自体はどんな次数の g(t) にも使える。問題は「距離判定に使う g(t) が何次のベジエ関数になるか」であり、これは曲線が 非有理（多項式）か有理かで大きく変わる。

非有理 n 次ベジエ曲線の場合

非有理の n 次ベジエ曲線は制御点 P_i を使って

P(t) = Σ P_i · B_i^n(t)　　// B_i^n はバーンスタイン基底、n次

と表され、微分 P'(t) は次数 n−1 のベジエ関数になる（次数が1つ下がるだけ）。点 Q と曲線上の点 P(t) を結ぶ線分が接線と直交する条件は

g(t) = P'(t) · (P(t) − Q) = 0

であり、これは「次数 n−1 の関数」と「次数 n の関数」の内積（各成分の積の和）なので、 次数は (n−1) + n = 2n−1 になる。積を取ると次数は足し算になる、というベジエ関数どうしの積の性質がそのまま次数に反映される。

有理 n 次ベジエ曲線の場合

有理ベジエ曲線は、重み w_i を使って分数の形で表される。

P(t) = X(t) / W(t)　　// X(t)=Σ w_i P_i B_i^n(t)（分子, n次）, W(t)=Σ w_i B_i^n(t)（分母, n次）

ここからが本質的な違いで、有理関数の微分には商の微分公式が必要になる。

P'(t) = [ X'(t)W(t) − X(t)W'(t) ] / W(t)²

分子 Z(t) = X'(t)W(t) − X(t)W'(t) は、次数 (n−1) の関数と次数 n の関数の積どうしの差なので、次数は 2n−1 になる（非有理のときの P'(t) の次数 n−1 より、まるまる n だけ高くなる）。これが「有理曲線は次数が上がる」最大の理由である。

さらに (P(t) − Q) の側も、分母 W(t) を払って

Y(t) = X(t) − Q·W(t)　　// 次数 n

という次数 n の関数にしておくと（分母 W(t) は重みが正である限り常に正なので、符号判定には分子だけ見れば十分）、判定関数は

N(t) = Z(t) · Y(t)　　// 次数 (2n−1) + n = 3n−1

という次数 3n−1 のベジエ関数になる。非有理の場合の 2n−1 に対して、有理の場合はちょうど n だけ次数が上乗せされる。これは「分母を1回払う」操作（商の微分でできる W(t) の因子を消すために、両辺に W(t)² を掛ける）が次数 n の因子を追加することに対応している。

判定内容	非有理 n次曲線	有理 n次曲線
直線・平面と曲線の距離関数そのもの	n	n
直線・平面と曲線の最短点（距離関数の微分）	n−1	2n−1
点と曲線の最短点（本解説の g(t), N(t)）	2n−1	3n−1
曲線と曲線の最短点（相手曲線を制御点で代表）	2n−1	3n−1
曲線間の距離関数そのもの（2変数）	2n	2n

西田(2021)「分割法を用いた有理ベジエ曲線・曲面の間隙計算」の表１を、本ツールの実装に合わせて整理したもの。網掛けの2行が「有理ベジエ曲線同士の最短点」ツールで実際に使われている次数（有理: 3n−1 ／非有理: 2n−1）である。

ポイントは、「有理になると常に次数が n 上乗せされる」という規則性で、分母を払うたびに（＝商の微分公式を1回使うたびに）その分母と同じ次数 n の因子が掛け算として増えるからである。曲面（2変数）の場合も同じ理屈がそのまま u, v それぞれの方向に適用される。

曲線どうしの最短点への拡張：相手を制御点で代表させる

上で導いた N(t) はあくまで「固定された1点 Q」と曲線 P(t) の関係式である。曲線どうしの最短点を求めるには、曲線 Q(s) 側にも同じ条件が必要になる。

q_t(s,t) = P'(t) · (P(t) − Q(s)) = 0 q_s(s,t) = Q'(s) · (P(t) − Q(s)) = 0

この 2 式を同時に満たす (t, s) が最短点である。ここで論文が採る工夫は、 q_t を厳密に s の関数として解くのではなく、Q(s) をその制御点で代表させて q_t の t 方向の存在範囲を求めるという点にある。つまり Q の制御点それぞれを固定点とみなして N(t) を計算し、それぞれの制御点について凸包クリッピングで t の候補区間を求め、それらをすべて包含する区間（和集合）で曲線 P をクリップする。

曲線 Q のすべての制御点 Q_j について、固定点として N(t) を計算し、ベジエクリッピングの凸包判定を1段階だけ行って区間 [t_lo, t_hi] を得る。すべての j についての和集合を取り、その区間で曲線 P を部分分割する（P が縮む）。
今度は逆に、縮んだ P の制御点それぞれを固定点として、曲線 Q に対して同じ判定を行い、 s の存在区間を求めて曲線 Q を部分分割する（Q が縮む）。
1と2を交互に繰り返す。どちらの絞り込みも「凸包が y=0 と交わる範囲」でしか次の区間を作らないため、繰り返すたびに両曲線は単調に縮んでいく。
区間の縮小が一定以上（目安80%以上残る）鈍い場合は、その曲線を中点で2分割し、両方の枝を独立に再帰処理する。これにより複数の局所最短点（極値）も取りこぼさず検出できる。
両曲線の区間幅が許容誤差以下になった時点（あるいは微小線分がほぼ平行になった時点）で収束とみなし、その中点を (t*, s*) とする。

P 側のクリップと Q 側のクリップを交互に行うたびに、根が存在しうる範囲（帯）が両曲線上で狭まっていき、最終的に P(t*) と Q(s*) を結ぶ垂線に収束する。「有理ベジエ曲線同士の最短点」ツールの右パネルの矩形群は、この収束を (t, s) の2次元パラメータ空間上で表示したものにあたる。

重要なのは、曲線どうしの最短点問題であっても、実際に解いている g(t) の次数は「点と曲線の最短点」のときと同じ 非有理 2n−1 ／有理 3n−1 だという点である。 2変数の連立方程式に見える問題を、片方を制御点で代表させることで「1変数のベジエクリッピングの繰り返し」に落とし込んでいるのが、この手法の最大の工夫といえる。

ベジエクリッピング法の利点（まとめ）

初期値が不要：ニュートン法と違い、収束の初期値を推測する必要がない。
ロバスト：凸包性質に基づく幾何学的な判定なので、局所解に迷い込みにくい。
解なしを高速に判定できる：制御多角形の凸包が y=0 と交わらなければ、その時点で「この区間に根はない」と即断できる。
高次関数でも1次式の反復で解ける：内部で使う操作は制御点の線形結合（デカステリョ法による分割）だけであり、関数の次数自体は反復のたびに形を変えずに縮小されていく。
非有理・有理のどちらにも同じ枠組みが使える：次数が変わるだけで、アルゴリズムの手順（凸包でクリップ → 部分分割 → 繰り返す）自体は共通している。

参考：
T. Sederberg, T. Nishita, "Curve Intersection using Bezier Clipping," Computer-Aided Design, Vol.22, No.9, 1990. 西田友是，「分割法を用いた有理ベジエ曲線・曲面の間隙計算」，Visual Computing／グラフィクスとCAD合同シンポジウム, 2021.