【正文】 院專 業(yè)姓 名班 級學 號指導教師 譯文一： B233。zier曲線F，G，交叉點。我們的算法是自適應的，僅根據(jù)精確的長浮點數(shù)計算。它被設計成與現(xiàn)有的算法競爭哪個是“好”的選擇。關鍵詞：計算幾何，曲線相交，B233。1 介紹 代數(shù)曲線和曲面的交叉分析在許多幾何模型領域是一個根本性的問題[16]。在本文中，我們考慮一類自由曲線，B233。目前所有的交叉貝塞爾曲線算法是不準確的，主要的就是不穩(wěn)定的問題。 一條曲線F是一個有限的曲線段，代表序列P（F）=（P0，...，PM）的控制點[8,6]。一對（F，G）貝塞爾曲線被稱為候選對CH（F）∩CH（G）的非空。首先，使用屬性，包含一條曲線F在CH(F)，該算法可以丟棄非候選對。通用交叉算法候選對維護一個隊列Q。如果F∪G的直徑小于ε，則輸出該對；否則它細分曲線具有較大的直徑，來討論F，把他分成代替曲線F0，F(xiàn)1，并在Q上附加（F0，G）和（F1，G）。為顯示的目的，這樣的常量是合理的。但通用的算法，輸出一對（F，G）沒有交集，或有多個交點。在標準假設，F(xiàn)，G有沒有共同的組件，然后，p是F∩G的一個孤立的點。這取決于F和G在p點的切線是否或重合。不相交的交點，必須相切的，橫向交叉點必須是橫切的。 （a）橫向的（交叉） （b）切向的（交叉） (C) 切線(不相交) 圖1：交點：（a）橫向（b）切向（c）切線 可以避免使用ε嗎？這似乎也合情合理，如果F和G只有交叉的交點，那么我們可以設計一個不使用任何ε來限制基于細分交叉算法。在任何情況下，關鍵的問題是如何檢測非交叉的交點。這類曲線，她的地址和本文中提到的那些不具有直接可比性，雖然B233。她介紹廣義Jacobi曲線的技術來檢測不相交非奇異的曲線的交點。但她的做法仍然使用有效的代數(shù)工具，如生成物和根隔離。一個最近的一篇論文中，Seidel和沃伯特[20]地址計算平面代數(shù)曲線的拓撲安排的；再次，細分和代數(shù)方法相結合的被使用。否則，我們使用長浮點數(shù)和原始的幾何操作進行純數(shù)字計算，如計算凸殼并相交的用一條線的曲線。比如，一個在沃伯特 賽德爾設定中是不知道純粹的自適應/數(shù)值版本。這些部分都是典型的標準：要么拒絕標準，確認非交叉或驗收標準，確認交點。上面的泛型算法僅使用凸殼準則。Sederberg和Meyers[19]根據(jù)矢端曲線肯定存在的橫向交叉點給出了驗收標準。在一般情況下，部分的標準是有數(shù)字濾波器組成的概念幾何模擬[5]。但最終，一個正確的算法必須使用一些完整的標準或其他一些全球保證其完整性。1。zier交點設計一個確切的細分算法。形成鮮明對比的方法,結合代數(shù)用數(shù)值的方法[2220]，我們是“完全自適應”。我們介紹的是主要的分析工具幾何分離的范圍內。請參閱第2和第7。Δ發(fā)展提供停止準則數(shù)值模擬和細分的程序。的邏輯中算法是無視這些Δ值。4?！昂玫妮斎搿?，一個迭代終止很久以前綁定的迭代是到達。為簡單起見，我們描述我們的算法只使用凸船體過濾器（第1節(jié)）。我們預計，大多數(shù)過濾器可以很容易地注冊成立到我們的算法有輕微的變化。第3條規(guī)定的第一個完整的檢測標準非交叉路口（NIC）的基本貝塞爾曲線。6。兩個關鍵的子程序交叉的初等貝塞爾曲線用直線（第4部分）和用于評估的“α函數(shù)”的跡象（第5部分）。Δ界需要小心應用程序（它不只是一個問題的取代一些開往εΔ通用交叉算法）。8。有一般方法，打破了代數(shù)曲線的關鍵點（例如，[14]）。相反，第7顯示了如何細分與分離邊界可以檢測和隔離等關鍵點。9。為了提高效率，我們不操縱代數(shù)甚至是一般合理的數(shù)字。10。首先，定義的“標準參數(shù)化”點，線和貝塞爾曲線如下：一個點p的坐標由下式給出P =（X，Y），一條線L它是由給定系數(shù)的方程AX + BY + C確定，一條貝塞爾曲線是由給出的控制點（依次給出的坐標）確定。例如，相交的“直通線”和“直接曲線”F產(chǎn)生的坐標是代數(shù)數(shù)點P *。然后，我們必須提供的替代方法通過直接代表（近似）間接物體對象。例如，如果p是L和F的唯一的交集，我們可能會用“點[L，F(xiàn)]”表示p*。這表示可以精確如下：使用De Casteljau的算法的通用算法，把曲線F細分為兩個代替曲線（F0，F(xiàn)1）。這個過程可以重復，當每次我們經(jīng)常想得到越來越近似的P*。舉例說明，假設我們希望測試是否P*=點[L，F(xiàn)]坐落在一個標準的貝塞爾曲線G上。然后，我們細化點[L，F(xiàn)]如上文所述，直到直徑（F）Δ/ 2。當是空集時，我們丟棄；當直徑時我們也將停止細分最后，我們的結論P在G上，當且僅當凸包CH（F），CH（GJ）對于一些j相交。11。我們的全論文可從。曲線和曲面的代數(shù)計算文獻是非常大的和多樣的。這種“代數(shù)算法“是準確的，并且（或可以完成）完整的。這樣的“幾何算法”往往不完整但廣泛在實踐中使用。然而，許多代數(shù)算法不考慮實用。幾何算法直接操作這些補丁。這個事實可以減少算法的代數(shù)適用性。但它是不容易，指定一個特定的分支曲線附近的一個置曲線自交點使用這種方法。這種算法不考慮實際[9]。近日，計算幾何學已開始處理曲線和曲面[4，10，21]。更一般地，它們的目標是使算法的代數(shù)觀點下更有效的和完整的；這些問題都往往被掩蓋了更多的理論文章。更一般地，我們的表面上的目標是沒有代數(shù)操作的情況下做精確的代數(shù)運算。這項工作最直接與我們可比的是Wolpert的和賽德爾的[23，22，20]，如上所述。他們的細分基礎的方法是幾何的，全面的自適應；但是它是目前未知是否它可以擴展處理的奇點。2 代數(shù)曲線的幾何分離邊界我們的主要數(shù)學工具是分離邊界的想法。讓表示矢量A的k范數(shù)的系數(shù)（我們使用k= 1，2和k=∞）。我們省略下標k時指2 范數(shù)，即歐氏距離。一對(p,q)，p∈F 和q∈G 這樣線通過p，q是正常的，p在F上和q在G上叫做（F，G）正相反的對。在下文中，我們假設只有限多對（F，G）正相反對。下面的結果依賴于一個多元根界Yap[24]（）。定理1。假設F,G有有限多個正相反的對。如果（p，q）是（F，G）正相反對并且pq那么其中的K=max｛｝，N=，D=。讓曲線A= 0和B=0是基本相對。如果p不再曲線上，那么p點能離曲線有多近？通過（L，l）浮點數(shù)，我們平均數(shù)字的形式在，m，k∈ Z。我們簡單地說“L位浮點”為（L，L）位浮點。讓q =（u，v）是一個坐標（L，）位浮點數(shù)的點，A(u, v) = = 0不包含在q為中心的圓的曲線，且p是曲線A =0上一個點，則其中的 必要條件即A = 0不包含圓集中在q不影響我們的應用程序貝塞爾曲線，因為圓弧非貝塞爾。對為Bezier曲線F，我們必將2規(guī)范的約束在其控制多邊形，(p0, . . . , pm)。設F是一個度為m貝塞爾曲線，控制點是Lbit浮點數(shù)字。Δ分離的屬性。上述定理給我們一個明確的綁定為Δ。隨后細分的F，G不改變Δ。的主要結果是一個完整的標準非過交集基本的曲線。它的圖形是參數(shù)化的曲線 F = {F(t) : t ∈ [c, d]}，其中F(t) = (t, f(t)) ∈ 。調用F(t)的圖形參數(shù)化的F，相比之下貝塞爾曲線的參數(shù)化法是后面介紹。如果F = F(c,d),線段連接F(c)和F(d)稱為F基礎部分。如果F在于高于（或低于）其基地段，我們把它稱為A初級（相應地，B初級）。把nF (c) 和 nF (d)叫做F =F[c, d]的最后的法線。成為一個A初級F，定義它的上層波及區(qū)U(F)限制在aF (c)和 aF (d) 和F。當我們擴展aF (c) 和aF (d)直到他們相遇，我們獲得一個錐C(F),其中包含U(F)。 圖2:上層波及區(qū)U(F)初級連接。讓G ∈ G[c, d]是另一個初等曲線。參見圖3?！? 圖3:初級連接(F,G):(a)ab連接　　(b)aa連接引理5。如果G ? U(F)然后有一個獨特的連續(xù)函數(shù)s : [0, 1] → [c, d]使得對所有t∈[0，t]，G（s（t））位于上半部分正常的自動對焦aF（t）。與(F,G)與前面的引理,如果G?U(F)然后角函數(shù)α : [0, 1] → (?π, π) （1）被給α(t) = θF (t) ? θG(s(t))是明確的和持續(xù)的。我們的主要結果測試不相交交點如下：定理7(非交叉交點準則(NIC))。假設F，GΔ分離的屬性和的F∪G是直徑小于Δ。（2） 如果α(0)α(1) 0，那么F和G是不相交的。4 交叉點與線與一條貝塞爾曲線F相交的特殊情況直線l處理在標準教科書[8]。當F代表了其控制多邊形P(F) =(p0, . . . , pm),然后它有貝塞爾曲線參數(shù)化和雖然默認的曲線是F = F[0，1]，我們也可以指定一個任意的間隔I = [c, d]定義曲線F[I] = F[c, d]。同樣,我們寫“”意味著F = F[I]在被細分為。相對簡單的算法，省略在該擴展抽象的。這條線相交算法中使用的一般算法的幾個中的子程序。至于qv，讓射線（q，v）表示射線原始點在q并且通過v。我們首先計算線F與通過q，v線的交點。另外，我們多次細分F并且如果CH（）包涵q就用代替F。在終止，如果q在CH()∪CH()外，我們可以很容易地確定在下方或者在上方；否則我們得到通過，因為（F）。我們開發(fā)這個符號確定的自適應過程。我們可以假設e （）。我們認為該α（t）的符號是等于S（t）：=c的符號?，F(xiàn)在，我們可以自適應地通過近似和估計誤差進行計算的符號。6 連接過程 在本節(jié)中，假設F，G是滿足Δ形分離特性的初等貝塞爾曲線，并且使得F∪G的直徑小于Δ。我們的目標是，以確定它們是否相交。此過程被稱為連接的過程。這似乎一般很難達到。讓F = F[0, 1]是一個A初級，G就是前面提到的G。假設我們發(fā)現(xiàn)一個 半正態(tài)分布 aF（t）與G相較于一個特殊的點。注意，是間接的貝塞爾曲線。概括地說，連接過程有三個步驟：。如果有是交點，我們正在處理。都有對稱性，我們可以假設F = F[0,1]是A初級，G是上述F。這不是很難解決的輕微復雜的情況下假設aF（t）相交G于兩個點。這三種情況圖4中可見的半連接。假設(F[0, 1], G[c, d])是一個半連接aF（0）通過G（c）并且aF（1）不與G相交。讓表示G（d）低一半標準。我們有三種可能性：（1） 相交。（3） 在點F(t)相交。然后我們擁有：（4） ：（1）相交。（3）在點F(t)相交7 關鍵點我們現(xiàn)在解決非基本B233。貝塞爾曲線F [0，1]可以細分為有限多個初級代替曲線。圖5（1）表示三次B233。圖5 單一三次B233。把t ∈ (0, 1) 稱為一個臨界值，F(xiàn)（t）是一個臨界點，如果滿足下列條件之一（參見Kim和Lee[14]）： （1）F（t）是固定值，即，； （2）F（t）是x極限值，即，； (3) F(t)是一個拐點，即，0，在。相反，如果F是基本的，那么它沒有X極值或拐點在其相對內部。因此，我們不建議細分B233。相反，我們將細分B233。把正好包含一個臨界點基本曲線叫做臨界曲線。在本節(jié)的其余部分，假設控制多邊形F，G是P(F)=（），P(G)=()。首先，我們約束的程度和規(guī)范關鍵點：引理10.（1） 如果F（t）=（ ）是一個固定或x極值，那么有角度m1，2標準最多。這給我們：，q是F的兩個不同的關鍵點。接下來，我們推廣定理3為了處理p是任何代數(shù)點：=（，）。如果曲線A（X，Y）= 0不包含一個圓圈集中在q點那么q到A=0的距離最少 其中的。這限制來自定理12中的引理10。如果直徑，我們可以稱F為微曲線。并且讓表示（）。因此，F(xiàn)包含一個固定的點，當且僅當通過其原點。zier曲線的給出的；在這種情況下我們可以檢查速度面通過的原點。 讓直徑（F）。定理14（x極端點）。然后F包含X極端點當且僅當和。同樣也讓行列式（p，q）。讓直徑（F）。前面的三個定理給我們的完整條件檢查，如果一個微型的曲線是一個基本的臨界曲線。zier曲線相交算法。簡單而不是實際的效率是下列目的描述。每個隊列只是候選對的列表。稱為宏觀隊列和微隊列，因為它們分別含有宏對和微型雙。關鍵的區(qū)別是分拆后一對（F，G）在（，G）（i = 0，1）中，如果（，G）是一個候選對，我們根據(jù)它是否是一個宏觀或微觀對，把它變成。但在實踐中，我們執(zhí)行各種有效的部分標準（例如，測試橫向交點）。微觀段： 現(xiàn)在，我們?yōu)槊繉Γ‵，G）提取：我們檢查，如果F包含一個關鍵點（第7章）。否則，我們采用的連接過程（第6章）。宏觀相是“標準”，易于實現(xiàn)。宏觀相結束時，微隊列預計為“很好的”輸入是小的或空的。這個新的方向在本質上依賴于使用的幾何分離邊界。如前所述，它概括了標準的假設，F(xiàn)，G是互質。我們推測它是相反的東西。Choi的定理意味著，當雙極性假設失敗的時候它是一個Δ分離的屬性持有者。 不幸的是，我們不知道如何約束Δ沒有正相反的假設。給我們的算法的復雜度分析，或一些的變型。 鳴謝特別感謝MyungSoo Kim教授在首爾國立大學的熱情款待。王文平教授指出，有必要區(qū)分切向交叉和切向非交叉的情況。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, 2002. Lecture Notes in CS, No. 246