【正文】 為系統(tǒng)的代數(shù)方程來解決的，　　通常使用符號或代數(shù)技術(shù)。代數(shù)算法把完整的代數(shù)套，往往被認為是束縛。這些文件提供高效，完整的代數(shù)算法低度曲面和曲線。細分方法,為解決多變量多項式系統(tǒng)最近被Gershon 和 Kim[7]和Mourrain和Pavone[15]重視。特別地，如果F和G相交相切于P，那么（P，P）是（F，G正相反的對。讓m=deg（A），n=deg（B），=a，=b。定理3。對于任何Δ 0，我們說F，GΔ分離的屬性，如果對所有p=q，如果（p，q）是（F，G）正相反對，或者如果p，q∈F∩G，那么。讓G [c，d]表示所有這些集圖。把正常的線nF(t)分成兩半法線：一個上部aF (t)和下部aF (t)和F(t)作為半線共同的終點。我們稱（F，G）是初級連接如果(1)G(c) ∈ aF (0)和G(d) ∈ aF (1),（2）整條曲線G躺在圓錐C(F)中。為了表示依賴于F，G，為這些功能我們可以寫出α =αF,G and s = sF,G?，F(xiàn)在，我們給出一個完整的情況下，F(xiàn)是基本的算法。正下方超越算法的用處：這是一種形式的“射線拍攝”中使用的以下的連接過程。5 角的自適應(yīng)標志NIC準則(定理7)需要的角度的標志α（0）和α（1）。查看完整的紙張了解詳細信息。相反，我們建議擴展NIC來處理“半連接”。這是很容易減少到最多四個下方超越測試。定理8.（半連接NIC）。在這種情況下，讓。zier一個臨界點。zier曲線的基本部件細分的關(guān)鍵點。（2） 如果F(t)是一個拐點，那么F（t）有角度最多（）。最后，選擇在（定理1），所述（定理2），和中范圍是最低的。定理13 （固定點）。定理15（拐點）。我們有兩個工作隊列。是空的的時候，這個階段結(jié)束。8. 開放性問題 本文開辟了可能性，實現(xiàn)全面的自適應(yīng)算法與其他計算的正確性保證涉及的曲線和曲面的問題。因此,對映假設(shè)并不是必不可少的。提高我們的分離范圍。9. 參考文獻[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, 2003.[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。 the algebraic algorithms treat plete algebraic sets, often assumed to be irreducible. This fact reduces the applicability of algebraic algorithms. To specify patches of an algebraic set, one could use semialgebraic formulas (., introduce inequalities). But it is not easy, say, to specify a particular branch of a curve in the neighborhood of a selfintersection using this method. The putation and topological analysis of real plane curves is a well studied problem [1, 18], but the worst case plexity is prohibitive。 otherwise it subdivides the curve with the larger diameter, say F, into subcurves F0, F1, and appends (F0,G) and (F1,G) to Q. This algorithm depends on a constant ε 0: pairs (F,G) with diameter less than ε are treated as intersecting. For display purposes, such constants are justifiable. But for topological analysis of curve arrangements, we want output pairs (F,G) that represent unique intersections. But the generic algorithm might output a pair (F,G) that has no intersection, or has multiple intersections. Let p be an intersection point of F and G. Under the standard assumption that F,G have no mon ponent, then p is an isolated point of F ∩G. The intersection at p can be tangential or transversal, depending on whether the tangents of F and G at p are coincident or not. Alternatively, we can classify p as a crossing or noncrossing intersection, depending on whether the curves cross each other at p or not。在與MyungSoo Kim, Gershon Elber, JoonKyung Seong 和 Iddo Hanniel的討論中我們受益匪淺。像我們這樣實現(xiàn)一個自適應(yīng)算法，比較非健壯的細分算法或代數(shù)算法。Sungwoo Choi已經(jīng)證明了這個猜想。微相對待退化和可能情況。如果我們沒有其他的東西還是宏觀段，我們?nèi)匀皇钦_的。我們設(shè)計的算法，以便自然是通用的交叉算法（參見導(dǎo)言）嵌入式的第一階段，我們的算法。如果p，q，r是平面點，讓行列式（p，q，r）是33矩陣的決定因素它的行是，其中的。例如，圖5（2）的?P（F）是為圖5（1）立方B233。讓Δ6=Δ（m，n，L）是曲線G和F中一個關(guān)鍵點p的之間的最小距離，假設(shè)。此外，坐標是L位長浮點數(shù)。臨界值是代數(shù)數(shù)字。點F（t）在該細分發(fā)生的“臨界點”。（2） 相交。在任何情況下，我們已經(jīng)減少了兩個半連接的搜索。原來我們可以為半連接改編NIC（定理7）。通過研究的動力，注意，要應(yīng)用NIC，必須細分F，G直到我們看到一個基本的連接（），其中 ?F， ?G。從式（2），我們可以為S（）開發(fā)一個下界：如果控制多邊形的F具有m +1個點L位浮點的坐標，和假設(shè)c,d,e,f是L位浮點數(shù)，那么意味著。我們終止當q CH() ∪ CH(),或者直徑（F）(定理3)。我們注意到，在這個特殊的情況下，我們在沒有調(diào)用NIC的情況下可以檢測使用幾何分離邊界的獨立的切線交點。在接下來的三個部分中,我們將展示如何應(yīng)用在一個交點應(yīng)用NIC算法。推論6。修復(fù)一個一個初等曲線F；為簡單起見，假定F ∈ G[0, 1]。讓nF(t)表示正常線通過F(t)，讓θF (t) ∈ [0, π)表示nF（d）與X軸的夾角。設(shè)f是有界的，連續(xù)可微的函數(shù)定義在區(qū)間[c，d〕cd。然后F滿足一個整數(shù)，度為m多項式方程A（X，Y）=0，其中。注意L（其中l(wèi)g是）。分別設(shè)f和g是定義的公式A = 0和B= 0時。分別考慮定義的公式A = 0的曲線F和G和B= 0。最近，普蘭廷卡Vegter[17]給出了同位素的近似隱式非奇異的表面的拓撲正確的算法。當代數(shù)算法與數(shù)字技術(shù)相結(jié)合，更實用的算法實現(xiàn)[13，12]。曲線和應(yīng)用程序中的表面通常有界子集（“修補程序”）的代數(shù)集。相關(guān)工作。假設(shè)我們可以計算一定范圍內(nèi)Δ 0，如果p*不在G上，那么它的距離G至少是Δ（第2部分）。我們在直接對象的上面使用“表達式”。我們也不會操縱多項式或執(zhí)行在當前子結(jié)式的計算，如被發(fā)現(xiàn)確切的交集算法。非基本貝塞爾曲線呢？一般的貝塞爾曲線的臨界點，基本的曲線沒有關(guān)鍵點。由一個“基本曲線”，我們指的是一個曲線圖凸部或凹函數(shù)。適應(yīng)性是指這些Δ界限僅在最壞的情況下被調(diào)用。他們回答這樣的問題：如果它們不相交，什么是最接近的兩個曲線段之間的距離？或如果q是不在曲線上的之間的最近距離是什么點q和曲線？這些界限，表示為功能度和高度的的相關(guān)多項式和代數(shù)數(shù)，表示通過各種Δ在本文中。我們的方法概述。一個完整的標準是，既接受和排斥的標準。這樣代數(shù)技術(shù)在其他部分的算法是花費很大的和減少的有效性的適應(yīng)性的。這不是顯而易見，但它是隱含了本文交集算法。讓p是F和G的一個交點。其次，算法的操作主要是細分，曲線F分割成兩個代替曲線F0，F(xiàn)1采用De Casteljau的算法。zier曲線。特別是，我們避免操縱代數(shù)數(shù)字和合成計算。畢業(yè)設(shè)計（論文）外文文獻翻譯畢業(yè)設(shè)計（論文）題目B233。我們的算法是自適應(yīng)的，僅根據(jù)精確的長浮點數(shù)計算。在本文中，我們考慮一類自由曲線，B233。首先，使用屬性，包含一條曲線F在CH(F)，該算法可以丟棄非候選對。但通用的算法，輸出一對（F，G）沒有交集，或有多個交點。 （a）橫向的（交叉） （b）切向的（交叉） (C) 切線(不相交) 圖1：交點：（a）橫向（b）切向（c）切線 可以避免使用ε嗎？這似乎也合情合理，如果F和G只有交叉的交點，那么我們可以設(shè)計一個不使用任何ε來限制基于細分交叉算法。但她的做法仍然使用有效的代數(shù)工具，如生成物和根隔離。這些部分都是典型的標準：要么拒絕標準，確認非交叉或驗收標準，確認交點。但最終，一個正確的算法必須使用一些完整的標準或其他一些全球保證其完整性。我們介紹的是主要的分析工具幾何分離的范圍內(nèi)。4。第3條規(guī)定的第一個完整的檢測標準非交叉路口