【正文】 屬性和的 F∪ G是直徑小于 Δ。 圖 3:初級連接 (F,G):(a)ab連接 (b)aa連接 引理 5。當(dāng)我們擴展 aF (c) 和 aF (d)直到他們相遇 ，我們獲得一個錐 C(F),其中包含 U(F)。如果 F = F(c,d),線段連接 F(c)和F(d)稱為 F 基礎(chǔ)部分。隨后細分的 F， G 不 改變 Δ。對為 Bezier 曲線 F，我們必將 2 規(guī)范的約束在其控制多邊形， (p0, . . . , pm)。 讓曲線 A= 0 和 B=0 是 基本 相對。下面的結(jié)果依賴于一個多元根界 Yap[24]（ 定理 ）。讓 kA表示矢量 A 的 k范數(shù)的系數(shù)（我們使用 k= 1， 2 和 k=∞）。更一般地，我們的表面上的目標是 沒有 代數(shù) 操作的情況下 做精確的代數(shù)運算 。但它是不容易 ， 指定一個特定的分支曲線附近的一個置曲線自交點使用這種方法。這樣的 ―幾何算法 ‖往往不完整但廣泛在實踐中使用。此程序的正確性是不難看出。 檢查 L 和 F0 是否相交 （第 4節(jié)），如果是這樣，精致的表示是點 [L， F0]，否則它 是點 [L， F1]。當(dāng)這樣的標準 長浮點數(shù) 參數(shù) X， Y， A， B，C 等，我們稱他們?yōu)橹苯?對象，否則他們是間接對象。第 8 提出了整體的交叉算法。 7。雖然過濾器沒有被強調(diào)在本文中，它們會影響我們的基本設(shè)計算法。的邊界很容易該算法開始時計算。 細分意味著適應(yīng)性。但是沒有任何已知的驗收不交叉的 交點的 標準，我們將 在 第 3 節(jié)提供一 個 。這不是明顯的先驗我們可以只用這樣的操作實現(xiàn)我們精確的曲線相交的目標。zier 曲線是比較特殊的代數(shù)曲線，它們可以是單數(shù)（參見圖 5）。另外，我們可以根據(jù)曲線是否彼此交叉的在 p 或沒有 ， 把 P 作為一個交叉或不相交 叉 的 交點； 這相當(dāng)于 交叉點 p 的重數(shù)是奇數(shù)還是偶數(shù)。 該算法依賴于一個常數(shù) ε 0： （ F， G）對 的 直徑小于 ε被視為 相交 。讓 CH（ F）表示 P（ F）中，作為觀察的凸包封閉區(qū)域。zier 曲線 ,， 細分方法 ，有效 的數(shù)值算法 ， 精確的幾何計算 。zier曲線的交集的完整細分算法 1 Chee K. Yap 摘要 ： 我們給第一個完整的細分算法可能與 切線相交的兩個 B233。zier曲線 的 應(yīng)用 學(xué) 院 專 業(yè) 姓 名 班 級 學(xué) 號 指導(dǎo)教師 譯文一： B233。 關(guān)鍵詞 ： 計算幾何 ， 曲線相交 ， B233。 一條曲線 F 是一個有限的曲線段 ， 代表序列 P（ F） =（ P0， ...， PM）的控制點 [8,6]。 如果 F∪ G 的直徑小于 ε， 則 輸出該對 ； 否則它細分曲線具有較大的直徑， 來討論 F，把他分成代替曲線 F0， F1，并在 Q 上附加（ F0， G）和（ F1， G）。 這取決于 F 和 G 在 p 點的切線是否或重合。這 類曲線，她的地址和本文中提到的那些不具有直接可比性 ， 雖然 B233。否則，我們使用 長浮點數(shù) 和原始的幾 何操作進行純數(shù)字計算 ， 如計算凸殼并相交的用一條線的曲線。 Sederberg 和 Meyers[19]根據(jù)矢端曲線肯定存在的橫向交叉點給出了驗收 標準。zier 交點 設(shè)計一個確切的細分算法。 Δ 發(fā)展提供停止準則數(shù)值模擬和細分的程序。為簡單起見，我們描述我們的算法只使用凸船體過濾器（第 1 節(jié)）。兩個關(guān)鍵的子程序交叉的初等 貝塞爾 曲線用直線（第 4 部分 ）和用于評估的 ―α函數(shù) ‖的跡象（第 5 部分 ）。相反，第 7 顯示了如何 細分 與分離邊界可以檢測和隔離等關(guān)鍵點。首先，定義的 ―標準參數(shù)化 ‖點，線 和貝塞爾 曲線如下： 一個 點 p 的坐標由下式給出 P =（ X， Y） ，一條線 L 它是由給定系數(shù)的方程 AX + BY + C 確定 ，一條 貝塞爾 曲線 是 由給出 的控制點（依次給出的坐標） 確定 。 這表示可以 精確 如下：使用 De Casteljau 的算法的通用算法 ，把曲線 F 細分為兩個代替曲線（ F0， F1）。當(dāng) ）（）（ FCHGCH j ? 是空集時，我們丟棄 jG ；當(dāng)直徑 jG 2/? 時 我們也將停止細分 jG 最后， 我們的結(jié)論 P在 G 上，當(dāng)且僅當(dāng)凸包 CH（ F）， CH（ GJ）對于一些 j 相交。（ 二 ）幾何 的角度 更喜歡曲線和曲面的參數(shù)形 式，利用數(shù)值通常解決技術(shù)，例如同倫或 細分 。要指定補丁的代數(shù)集，可以用 半代數(shù) 的公式（即不 等式 ）。相反，我們的目標是讓算法下幾何完全健壯的觀點，同時保留其適應(yīng)性效率。假設(shè)一個 A(x,y)、 B(x,y)∈ Z(x,y)。這意味著是互質(zhì)（即 A， B，它們沒有共同的組件）。 接下來，我們給不同的路口之間的分離界限要點： 定理 2。以上的范圍對于一般的代數(shù)曲線。重要的是要注意，本 Δ 取決于僅在初始輸入曲線 F，G。 寫 ―F = F(c， d)‖， 以表明域 (圖或貝塞爾曲線 )參數(shù)化 (c， d)。 參見圖 2。注意 G可以是 A或 B初級； 因此，我們 稱 （ F， G） 為 AA或 AB連接 。 讓 (F,G)是一個初級的連接， G ? U(F)和 ɑ通過（ 1）給出。 使用符號 ―I → ( 10 II， )‖如果一個間隔 I分為兩個 子區(qū)間 10 II， （除非另有說明，否則承擔(dān)二分 I說明）。 在輸入（ F， q， v），其中F是最基本的，這個測試會產(chǎn)生三個輸出之一： 通過，如果 q ∈ F；在上方，如果射線（ q， v）與 F相交，但是 q?F；在下方，其他情況。 設(shè) F是一個基本的曲線貝塞爾曲線參數(shù)化 F（ t） =（ ? ? ? ?tFtF xx ， ），并且 l是一條參數(shù)化方程 L(t) = (ct + d, et + f)， c, d, e, f是常量。查看完整的紙張了解詳細信息。,FG ） ，其中 ‘F ?F， 39。 注意 ， 10 GG， 是間接的貝塞爾曲線。 這不是很難解決的輕微 復(fù)雜 的情況下 假設(shè) aF（ t）相交 G于兩個點 。定義 ）（ dG? 是角度的向上正常在 G（ d）作出與正 x軸（如前）。zier曲線這個問題。39。 ?ty ； (3) F(t) 是 一 個 拐 點 ， 即 ， ?）（ tHF 0 ， 0)(H)(H FF ??? tt 在)()(F)()(FtH 39。相反，如果 F是基本的，那么它沒有 X極值或拐點在其相對內(nèi)部。 在本節(jié)的其余部分 ， 假設(shè)控制多邊形 F， G是 P(F)=（ mpp,...,0 ）， P(G)=( nq,...,q0 )。 接下來，我們推廣定理 3為了處理 p是任何代數(shù)點： 定理 q=（ ， ），在那里 ， 2范 數(shù) ? c和 角 度 ? d。 tBpmtBppmt immi iimmi ii ?????? ? ?? ???? 這里我們定義 iii ppp ?? ?1: 。 定理 13 （固定點）。 定理 15（拐點）。 我們有兩個工作隊列 10 ， 。 0Q是空的 的時候， 這個階段結(jié)束 。 本文開辟了可能性，實現(xiàn)全面的 自適應(yīng)算法與其他計算的正確性保證涉及的曲線和曲面的問題。因此 ,對映假設(shè)并不是必不可少的。提高我們的分離范圍。 [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。 again, a bination of subdivision and algebraic methods are used. In contrast, the only algebraic information we use are algebraic zero bounds. Otherwise, we perform purely numerical putations using bigfloat numbers and primitive geometric operations such as puting convex hulls and intersecting curves with a line. It is not obvious a priori that we can achieve our exact curve intersection goals using only such operations. For instance, a purely adaptive/numerical version in the WolpertSeidel setting is not known. Current subdivistion algorithms deploy a variety of criteria for detecting intersection points. These are typically partial criteria: either a rejection criterion that affirms nonintersection or an acceptance criterion that affirms an intersection. A plete criterion is one that is both an acceptance and rejection criterion. The generic algorithm above uses only the convex hull criterion. Since this is a rejection criterion, the generic algorithm could never affirm intersections. Sederberg and Meyers [19] gave an acceptance criterion based on hodographs which affirms the presence of a transversal intersection. However there is no known acceptance criterion for noncrossing intersections。 [Numerical Analysis]: Roots of Nonlinear Equations—methods for polynomials。提供一個簡單的算法的情況下，只有橫向的交叉點。 在一般情況下，細分的算法的復(fù)雜性似乎知之甚少。顯然，如果 F 是一個 G 的 偏移量，反之亦然，正相反 假設(shè)將失敗。 備注。明顯的初始化后 10 ， ，該算法分為兩個階段 ： 宏階段 ： 這基本上是第 1節(jié) 0Q 上 操作 通用 交點 的算 法。 8 交叉點算法 我們現(xiàn)在目前全球任意兩個 B233。 讓直徑（ F） *? 。因此， F包含一個固定的點，當(dāng)且僅當(dāng) )(F39。 這 限制 來自定理 12中的 引理 10。首先，我們約束的程度和規(guī)范關(guān)鍵點： 引理 10. （ 1） 如果 F（ t） =（ ）（），（ tFtF yx ） 是一個固定或 x極值，那么 )(FtFx ty），（ 有角度 ? m1， 2標準最多 mmL m94 ）（ 。相反，我們將細分 B233。39。 ?? tFt yx ； （ 2） F（ t）是 x極限值，即， 0)(F)(F,0)(F 39。zier一個臨界點。 在這種情況下 ，讓))()((s ig ns dt GF ?? ?? ｝，｛ 110?? 。 定理 8.（半連接 NIC）。如果有是 交點 ，我們正在 處理 。 讓 F = F[0, 1]是一個 A初級， G就是前面提到的 G。如果他們相交，相切，我們最終必須至少是含蓄地減少他們 NIC。39。 我們終止當(dāng) q ? CH( 0F ) ∪ CH( 1F ),或者直徑（ F） 23? (定理 3)。我們注意到，在這個特殊的情況下，我們 在 沒有調(diào)用 NIC的情況下 可以檢測使用幾何分離邊界的 獨立的 切線交點 。 在接下來的三個部分中 ,我們將展示如何應(yīng)用在一個 交點 應(yīng)用 NIC算