算法合集之半平面交的新算法及其實(shí)用價值-在線瀏覽
2024-12-03 20:30本頁面
【正文】 形邊的交點(diǎn)為分界點(diǎn)，將邊分為內(nèi)、外兩種。 當(dāng)然，我們不能掃描所有有理數(shù)！ Bu Au Bl Al November 12, 2021 Zeyuan Zhu 20 2. Convex Polygon Intersection Call the edges where Au, Al, Bu and Bl are: e1, e2, e3 and e4 respectively. Next xevent should be chosen among four endpoints of e1, e2, e3 and e4, and four potential intersections: e1∩e3, e1∩e4, e2∩e3 and e2∩e4. 稱 Au, Al, Bu, Bl所在的邊叫做 e1,e2,e3,e4 下一個 x事件將在這四條邊的端點(diǎn)，以及兩兩交點(diǎn)中選出 Bu Au Bl Al O(n) November 12, 2021 Zeyuan Zhu 21 3. Common solution: DivideandConquer Algorithm – Damp。 2 分 : 將 n個半平面分成兩個 n/2的集合 . 治 : 對兩子集合遞歸求解半平面交 . 合 : 將前一步算出來的兩個交 (凸多邊形 )利用第 2章的 CPI求解 . November 12, 2021 Zeyuan Zhu 23 3. DivideandConquer Algorithm The total time plexity of the solution can be calculated via recursive equation. 總時間復(fù)雜度可以用遞歸分析法 . 2( ) 2 ( ) ( )( ) ( l o g )nT n T O nT n O n n???CPI November 12, 2021 Zeyuan Zhu 24 4. My New Solution: SortandIncremental Algorithm – Samp。π. ? 半平面的極角定義 : 比如 xy?常數(shù)的半平面，定義它的極角為 188。π ?π November 12, 2021 Zeyuan Zhu 26 4. SortandIncremental Algorithm ? Step 1: Separate the hplanes into two sets. One has polar angles of (189。π], the other has those of (π, 189。π, π]. ? Step 1: 將半平面分成兩部分，一部分極角范圍 (189。π]，另一部分范圍 (π, 189。π, π] November 12, 2021 Zeyuan Zhu 27 4. SortandIncremental Algorithm ?考慮 (189。π]的半平面 (另一個集合類似地做Step3/4)，將他們極角排序 。 ? Step 2: Consider the set of hplanes in (189。π] (the other set should also go through step 3 and 4 similarly). Sort them by the polar angle. For the hplanes with the same polar angle, we can keep only one down (delete all others) according to the constant of these hplanes November 12, 2021 Zeyuan Zhu 28 4. SortandIncremental Algorithm ?從排序后極角最小兩個半平面開始，求出它們的交點(diǎn)并且將他們押入棧。 ? Step 3: Each time, add one more hplane by increasing order of polar angles, and calculate the intersection of it and the top hplane in stack. November 12, 2021 Zeyuan Zhu 30 4. SortandIncremental Algorithm ?如果當(dāng)前的交點(diǎn)在棧頂兩個半平面交點(diǎn)的右邊，出棧（ pop）。 ? Step 3: …we pop the stack once. Once? Is it enough? Nie! Do this repeatedly until it is to the left of the top intersection. November 12, 2021 Zeyuan Zhu 33 4. SortandIncremental Algorithm ?相鄰半平面的交點(diǎn)組成半個凸多邊形。π, 189。π]∪ (189。π, 189。π]∪ (189。我們有兩個點(diǎn)集， (189。π]給出上半個， (π, 189。π, π]給出下半個 ? Step 4: Intersections of adjacent hplane pairs in stack form half a convex polygon. For the two sets, we have two halves – (189。π] gives an upper hull and (π, 189。π, π] gives a lower h
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1