【文章內(nèi)容簡介】 tGF,?????? （ 4） 圖 ：（ 1） ）（），（ 0adb FG 相交。（ 2） )1(dbG Fa），（ 相交。（ 3） Fd),(bG在點 F(t)相交 7 關(guān)鍵點 我們現(xiàn)在解決非基本 B233。zier曲線這個問題。貝塞爾曲線 F [0， 1]可以細(xì)分為有限多個 初級代替曲線 。點 F（ t）在該細(xì)分發(fā)生的 ―臨 界點 ‖。圖 5（ 1）表示三次 B233。zier一個臨界點。 圖 5 單一三次 B233。zier曲線：（ 1）控制多邊形（ 2） 矢端曲線 讓 ）（），（ tFtF yx 是 F = F[0, 1]的 坐標(biāo)函數(shù)，即， F（ t） =（ ）（），（ tFtF yx ），然后讓 ),(F 39。39。39。 yx FF? 表示相對于 t的衍生工具。 把 t ∈ (0, 1) 稱為一個臨界值， F（ t）是一個臨界點， 如果滿足下列條件之一（參見 Kim和 Lee[14]）： （ 1） F（ t）是固定值，即， 0)()(F 39。39。 ?? tFt yx ； （ 2） F（ t）是 x極限值，即， 0)(F)(F,0)(F 39。39。39。 ?? ?? ttt xxx ， 0)(F39。 ?ty ； (3) F(t) 是 一 個 拐 點 ， 即 ， ?）（ tHF 0 ， 0)(H)(H FF ??? tt 在)()(F)()(FtH 39。39。39。39。39。39。F tFttFt xyyx ??）：（ 。 引理 F其相對內(nèi)部沒有關(guān)鍵點， 那么 F是基本的。相反，如果 F是基本的，那么它沒有 X極值或拐點在其相對內(nèi)部。 臨界值是代數(shù)數(shù) 字 。因此，我們不建議細(xì)分 B233。zier曲線的基本部件細(xì)分的關(guān)鍵點。相反，我們將細(xì)分 B233。zier曲線在 長浮點數(shù) 以使所得 代替曲線 是 初級 或包含在最關(guān)鍵點。把 正好包含一個臨界點基本曲線 叫做 臨界曲線?，F(xiàn)在， 我們呼吁更多的分離由一個單一的數(shù)字總結(jié)的邊界 Δ*0進(jìn)行說明。 在本節(jié)的其余部分 ， 假設(shè)控制多邊形 F， G是 P(F)=（ mpp,...,0 ）， P(G)=( nq,...,q0 )。此外，坐標(biāo) sqs ji 39。39。 ,p 是 L位 長浮點數(shù) 。首先，我們約束的程度和規(guī)范關(guān)鍵點： 引理 10. （ 1） 如果 F（ t） =（ ）（），（ tFtF yx ） 是一個固定或 x極值，那么 )(FtFx ty），（ 有角度 ? m1， 2標(biāo)準(zhǔn)最多 mmL m94 ）（ 。 （ 2） 如果 F(t)是一個拐點 ，那么 F（ t）有角度 標(biāo)準(zhǔn)， 23m2? 最多（ mL8116m2 4 ）m 。 這給我們 ： 推論 p， q是 F的 兩個不同的關(guān)鍵點 。如果 nm2 ?? 那么 | |或 | |有一個比 m5m2L2m4 m8125616 ）（： ??? 大。 接下來，我們推廣定理 3為了處理 p是任何代數(shù)點： 定理 q=（ ， ），在那里 ， 2范 數(shù) ? c和 角 度 ? d。讓多項式 A（ X， Y） 有 2范數(shù) a和 m角度 。如果曲線 A（ X， Y） = 0不包含一個圓圈集中在 q點那么 q到 A=0的距離最少 ?? ），，（ dcLam5 22 dm12D23 2NK2 ）（ 其中的 ｝，，｛ cma413m a xK ? ）（ 5 d2m25N ??? ， ）（ d4m43dmD 22 ??? 。 讓 Δ6=Δ（ m， n， L） 是 曲線 G和 F中一個關(guān)鍵點 p的之間的最小 距離 ， 假設(shè) Gp? 。 這 限制 來自定理 12中的 引理 10。最后，選擇 在 1? （定理 1），所述 2? （定理 2）， 4? 和 6?中 范圍是最低的 *? 。如果直徑 *)( ??F ，我們可以稱 F為微曲線。 這是眾所周知的，相對于 t的導(dǎo)數(shù)是由下式給出 )()()()(F 1 111 11 139。 tBpmtBppmt immi iimmi ii ?????? ? ?? ???? 這里我們定義 iii ppp ?? ?1: 。并且讓)(PF? 表示（ mpp ?? ,...,1 ）。 因此，我們看到， m? P（ F）是曲線 )(F39。 t 的控制多邊形，稱為速度圖 F。因此， F包含一個固定的點，當(dāng)且僅當(dāng) )(F39。 t 通過 其原點 。例如，圖 5（ 2）的 ? P（ F） 是 為圖 5（ 1） 立方 B233。zier曲線 的給出的； 在這種情況下我們可以檢查速度面通過的原點。 定理 13 （固定點）。 讓直徑（ F） mma ）（ 2,1m3? 。 然后 F 包含一個固定的點當(dāng)且僅當(dāng) 凸包逼近 ? P（ F） 中包含的原點（ 0， 0）。 定理 14（ x 極端點 ）。 讓直徑（ F） *? 。然后 F 包含 X 極端點 當(dāng)且僅當(dāng) 0).().( 1 ??? xpxp m和 0).().( 1 ??? ypyp m 。 如果 p， q， r 是平面點 ，讓行列式（ p， q， r） 是 33矩陣 的決定因素 它的行是 hhh rqp , ，其 中的 )1,.,.( ypxpp h ? 。同樣也讓行列式（ p， q）表示 。 定理 15（拐點）。讓直徑（ F） *? 。 然后 F 包含了一個拐點，當(dāng)且僅當(dāng) 行列式（ 210 , ppp ）（ mmm ppp , 12 ?? ） 0。 前面的三個定理給我們的完 整條件檢查，如果一個微型的曲線是一個基本的臨界曲線。 8 交叉點算法 我們現(xiàn)在目前全球任意兩個 B233。zier 曲線相交算法。我們設(shè)計的算法，以便自然是通用的交叉算法（參見導(dǎo)言）嵌入式的第一階段，我們的算法。簡單而不是實際的效率是下列目的描述。 我們有兩個工作隊列 10 ， 。 每個隊列只是候選對的列表。 如果直徑CH(F)? CH(G)比 *? 小， 一個 候選對（ F， G）被稱為一個微對 ； 否則這是一個宏觀的對。 稱 10 ， 為 宏觀隊列和微隊列，因為它們分別含有宏對和微型雙。明顯的初始化后 10 ， ，該算法分為兩個階段 ： 宏階段 ： 這基本上是第 1節(jié) 0Q 上 操作 通用 交點 的算 法。關(guān)鍵的區(qū)別是分拆后一對（ F，G） 在 （ iF ， G）（ i = 0， 1） 中，如果 （ iF ， G）是一個候選對 ， 我們根據(jù)它是否是一個宏觀或微觀對 ， 把它變成 10 ， 。 如果我們沒有其他的 東西還是 宏觀 段 ，我們?nèi)匀皇钦_的。但在實踐中，我們執(zhí)行各種有效的部分標(biāo)準(zhǔn)（例如，測試橫向 交點 ）。 0Q是空的 的時候， 這個階段結(jié)束 。 微觀段： 現(xiàn)在，我們?yōu)槊繉Γ?F， G）提取 1Q ：我們檢查，如果 F 包含一個關(guān)鍵點（第7章）。如果是這樣，我們就可以對輸出。否則，我們采用的 連接 過程（第 6章）。 備注。宏觀相是 ―標(biāo)準(zhǔn) ‖，易于實現(xiàn)。微相對待退化和可能情況。宏觀相結(jié)束時，微隊列預(yù)計為 ―很好的 ‖輸入是小的或空的。 本文開辟了可能性，實現(xiàn)全面的 自適應(yīng)算法與其他計算的正確性保證涉及的曲線和曲面的問題。這個新的方向在本質(zhì)上依賴于使用的幾何分離邊界。最明顯的問題是開放的，所以我們只列出的 近期論文 有關(guān)的幾個問題： 我們的 F， G 交叉算法有這樣的雙極性假設(shè)： F， G 有有限 多正相反 對。如前所述，它概括了標(biāo)準(zhǔn)的假設(shè)， F， G 是互質(zhì)。顯然，如果 F 是一個 G 的 偏移量，反之亦然，正相反 假設(shè)將失敗。我們推測 它是相反的東西。 Sungwoo Choi 已經(jīng)證明了這個猜想。Choi 的定理意味著， 當(dāng) 雙極性假設(shè)失敗 的時候它是 一個 Δ 分離的 屬性 持有 者 。因此 ,對映假設(shè)并不是必不可少的。 不幸的是，我們不知道如何約束 Δ 沒有 正相反 的假設(shè)。 給我們的算法的復(fù)雜度分析，或一些的變 型。 在一般情況下，細(xì)分的算法的復(fù)雜性似乎知之甚少。 像我們這樣 實現(xiàn)一個自適應(yīng)算法 ， 比較非健壯的細(xì)分算法或代數(shù)算法。 提高我們的分離范圍。 我們已經(jīng)有所改善利用的事實是貝塞爾曲線的邊界，這些都為簡潔起見省略。 提供一個簡單的算法的情況下，只有橫向的交叉點。 鳴謝 特別感謝 MyungSoo Kim教授在 首爾國立大學(xué) 的熱情款待。在與 MyungSoo Kim, Gershon Elber, JoonKyung Seong 和 Iddo Hanniel的討論中我們受益匪淺。 王文平教授指出，有必要區(qū)分切向交叉和切向非交叉的情況。 [1] D. S. Arnon and S. McCullum. A polynomialtime algorithm for the topological type of a real algebraic curve. J. of Symbolic Computation, 5:213–236, 1988. [2] C. Bajaj and . Kim. Algorithms for planar geometric models. In Proc. 15th Int. Colloq. Automata, Languages and Programming, pages 67–81, 1988. Lecture Notes in Computer Science. [3] S. Basu, R. Pollack, and . Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2020. [4] E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, and E. Sch168。omer. A putational basis for conic arcs and boolean operations on conic polygons. In Proc. 10th European Symp. On Algorithms (ESA’02), pages 174–186. Springer, 2020. Lecture Notes in CS, No. 2461. [5] H. Br168。onnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for putational geometry. Discrete Applied Mathematics, 109(12):25–47, 2020. [6] E. Cohen, R. Riesenfeld, and G. Elber. Geometric Modeling with Splines: An Introduction. . Peters, Ltd, Wellesley, MA, 2020. [7] G. Elber and . Kim. Geometric constraint solver using multivariate rational spline functions. In Proc. 6th ACM Symp. on Solid Modeling and Applications, pages 1–10. ACM Press, 2020. [8] G. Farin. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Academic Press, Inc, second edition, 1990. [9] R. T. Farouki. Numerical stability in geometric algorithms and representation. In D. C. Handsb, editor, The Mathematics of Surfaces III, pages 83–114. Clarendon Press, Oxford, 1989. [10] N. Geismann, M. Hemmer, and E. Sch168。omer. Computing a 3dimensional cell in an arrangement of quadrics: Exactly and actually! In Proc. 17th ACM Symp. on Comp. Geometry, pages 264–273, 2020. [11] L. GonzalezVega and M. E. Kahoui. An improved upper plexity bound for the topology putation of a real algebraic plane curve. J. Complex., 12(4):527–544, 1996. [12] L. GonzalezVega and I. Necula. Efficient topology determination of implicitly defined algebraic plane curves. Compu