算法合集之半平面交的新算法及其實用價值(存儲版)
【正文】 nd Bl, form an interval of the current inner region – the red segment in bold. Au、 Bu中靠下的，和 Al、 Bl中靠上的，組成了當(dāng)前多邊形的內(nèi)部區(qū)域 Polygon A Polygon B Bu Au Bl Al Sweep line November 12, 2021 Zeyuan Zhu 19 2. Convex Polygon Intersection Let us call the xcoordinates to be swept xevents. Obviously, the sweep line may not go through all the xevent with rational coordinates! 我們稱被掃描線掃描到的 x坐標(biāo)叫做 x事件。π, 189。π, 189。 ? Step 3: If this intersection is to the right of the intersection of top two hplanes in stack, we pop the stack once. November 12, 2021 Zeyuan Zhu 31 4. SortandIncremental Algorithm ? Step 3: November 12, 2021 Zeyuan Zhu 32 4. SortandIncremental Algorithm ?前問我們說到出棧，出棧只需要一次么？ Nie!我們要繼續(xù)交點檢查，如果還在右邊我們要繼續(xù)出棧，直到 當(dāng)前交點在棧頂交點的左邊 。π] gives an upper hull and (π, 189。π, 189。C algorithm, but some overwhelming advantages of implementing Samp。C大大簡單化 ， C++程序語言實現(xiàn)Samp。I程序比 Damp。π]（ 或任意一個跨度為 π的區(qū)間 ） ， Samp。 山， 刺破青天鍔未殘。 山， 倒海翻江卷巨瀾。C program may not. An informatics problem a p p e a r e d in U S A I n v i t a t i o n a l Computing Olympiad contest with such purpose. 如果給定半平面均在 (189。I算法復(fù)雜度中的系數(shù) ， 遠(yuǎn)小于Damp。C one. The program in C++ programming language takes less than 3KB. 新的 Samp。通常我們用快速排序?qū)崿F(xiàn) Step2，總的時間復(fù)雜度為O(nlogn)，隱蔽其中的 常數(shù)因子 很小 November 12, 2021 Zeyuan Zhu 41 5. Conclusion and Practical Use 總結(jié)和實際應(yīng)用 November 12, 2021 Zeyuan Zhu 42 5. Conclusion and Practical Use Great ideas need landing gear as well as wings. Samp。π]∪ (189。π, π]給出下半個 ? Step 4: Intersections of adjacent hplane pairs in stack form half a convex polygon. For the two sets, we have two halves – (189。 ? Step 3: Starting from two hplanes with the least polar angle, pute their intersection. Push them two into a stack. November 12, 2021 Zeyuan Zhu 29 4. SortandIncremental Algorithm ?每次按照極角從小到大順序增加一個半平面，算出它與棧頂半平面的交點。π]∪ (189。π. 188。 我們描繪一個平面掃描法 。C. 簡要介紹舊 Damp。 emphasize its advantages in practical application, and to some extent, reduce the plexity to O(n). However, the new algorithm will be extraordinarily easy to be implemented. 主旨 : 半平面的交是當(dāng)今學(xué)術(shù)界熱烈討論的問題之一，本文將介紹一個全新的 O(nlogn)半平面交算法，強調(diào)它在實際運用中的價值，并且在某種程度上將復(fù)雜度下降至 O(n)線性。I emerges detailedly. 揭開我的新算法 Samp。 當(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 intersect
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1