算法合集之《半平面交的新算法及其實(shí)用價(jià)值》

1、All great ideas are controversial, or have been at one time.偉大的理論都是有爭議的，或者至少曾經(jīng)是有爭議的。 Gilbert Seldes (1893-1970)U.S. theater, film, and radio critic.理論的爭議9/26/20221A wise man will make more opportunities than he finds.聰明人總是制造更多的機(jī)會，而不是去等待尋找。Francis Bacon (1561-1626)English philosopher, statesman, and

2、lawyer.制造機(jī)會9/26/20222After the leaves have fallen, we return to a plain sense of things. It is as if we had come to an end of the imagination.葉落時(shí)分，我們回到一切的本來面目，這樣就與創(chuàng)造與幻想的終點(diǎn)不遠(yuǎn)了。Wallace Stevens (1879-1955)U.S. poet忘記過去，揭開本來面目9/26/20223Hello, Ladies and Gentlemen. 女士們先生們大家好Bonjour, Mesdames et Messieurs

3、.Witajcie, Panie i Panowie.Hallo, Damen und Herren.Buna ziua, Doamenelor si Domnilor.Ciao, signore e signori.Zeyuan Zhu, Grade 12, Nanjing Foreign Language School, Jiangsu, China. 朱澤園, 高三, 南京市外國語學(xué)校, 江蘇, 中國9/26/20224New algorithm for Half-plane Intersection and its Practical Value Thesis for Chinese

4、Team Selecting Contest 2006 半平面交的新算法及其實(shí)用價(jià)值 中國代表隊(duì)2006年選拔賽論文Zeyuan Zhu, Grade 12, Nanjing Foreign Language School, Jiangsu, China. 朱澤園, 高三, 南京市外國語學(xué)校, 江蘇, 中國9/26/20225Project Overview 全文總攬Aim: Present a new O(nlogn) algorithm for half-plane intersection (abbr. HPI), which is one of the most heatedly di

5、scussed problems in computer science; emphasize its advantages in practical application, and to some extent, reduce the complexity to O(n). However, the new algorithm will be extraordinarily easy to be implemented.yes主旨: 半平面的交是當(dāng)今學(xué)術(shù)界熱烈討論的問題之一，本文將介紹一個(gè)全新的O(nlogn)半平面交算法，強(qiáng)調(diào)它在實(shí)際運(yùn)用中的價(jià)值，并且在某種程度上將復(fù)雜度下降至O(n)線

6、性。最重要的是，我將介紹的算法非常便于實(shí)現(xiàn).9/26/20226Project Overview 全文總攬1 introduces what Half-Plane Intersection (HPI) is. 什么是半平面交.2 prepares a convex polygon intersection (CPI). 凸多邊形交預(yù)備知識.3 briefly discuss a common solution for HPI D&C. 簡要介紹舊D&C算法.4 my new algorithm S&I emerges detailedly. 揭開我的新算法S&I神秘面紗.5 conclusio

7、n and discussion on further practical use. 總結(jié)和實(shí)際運(yùn)用.9/26/202271.Statement of the Problem - 問題概述9/26/202281. Statement of the Problem A line in plane is usually represented as ax+by=c. Similarly, its inequality form ax+by () c represents a half-plane (also named h-plane for short) as one side of this

8、line. 3x-2y=1x+2y1眾所周知，直線常用ax+by=c表示，類似地半平面以ax+by ()c為定義。9/26/202291. Statement of the Problem Given n half-planes, aix+biyci (1in), you are to determine the set of all points that satisfying all the n inequations. 給定n個(gè)形如aix+biyci的半平面，找到所有滿足它們的點(diǎn)所組成的點(diǎn)集9/26/2022101. Statement of the Problem Feasible r

9、egion forms a shape of convex hull possibly unbounded.Add four h-planes forming a rectangle, to make the intersection area finite.合并后區(qū)域形如凸多邊形，可能無界此時(shí)增加4個(gè)半平面保證面積有限9/26/2022111. Statement of the Problem Each h-plane builds up at most one side of the convex polygon. Hence, The convex region will be boun

10、ded by at most n edges.每個(gè)半平面最多形成相交區(qū)域的一條邊，因此相交區(qū)域不超過n條邊。6 h-planespentagon9 h-planespentagon9/26/2022121. Statement of the Problem Pay attention that intersection sometimes yields a line, a ray, a line-segment, a point or an empty region. 注意相交后的區(qū)域，有可能是一個(gè)直線、射線、線段或者點(diǎn)，當(dāng)然也可能是空集。linerayline-segmentpointemp

11、ty set9/26/2022132.Convex Polygon Intersection CPI凸多邊形交預(yù)備知識9/26/2022142. Convex Polygon IntersectionIntersecting two convex polygons A and B into a single one.We will sketch out an efficient way, named plane sweep method. 求兩個(gè)凸多邊形A和B的交（一個(gè)新凸多邊形）。我們描繪一個(gè)平面掃描法。Polygon APolygon B9/26/2022152. Convex Polyg

12、on IntersectionMain idea: Regard intersections of edges as cutting points, and break boundaries of A and B, into outer edges and inner edges.Segments of inner edges establish ties to each other, and form a polygon. (in bold)主要思想: 以兩凸邊形邊的交點(diǎn)為分界點(diǎn)，將邊分為內(nèi)、外兩種。內(nèi)邊互相連接，成為所求多邊形（圖中粗線條）Polygon APolygon B9/26/20

13、22162. Convex Polygon IntersectionSuppose there is a vertical sweep line, performing left-to-right sweep. At anytime, there are at most four intersections from sweep line to either given polygon.假設(shè)有一個(gè)垂直的掃描線，從左向右掃描任何時(shí)刻，掃描線和兩個(gè)多邊形最多4個(gè)交點(diǎn)Polygon APolygon BBuAuBlAlSweep line9/26/2022172. Convex Polygon In

14、tersectionthe lower one between Au and Bu, and the upper one between Al and Bl, form an interval of the current inner region the red segment in bold.Au、Bu中靠下的，和Al、Bl中靠上的，組成了當(dāng)前多邊形的內(nèi)部區(qū)域Polygon APolygon BBuAuBlAlSweep line9/26/2022182. Convex Polygon IntersectionLet us call the x-coordinates to be swep

15、t x-events.Obviously, the sweep line may not go through all the x-event with rational coordinates!我們稱被掃描線掃描到的x坐標(biāo)叫做x事件。當(dāng)然，我們不能掃描所有有理數(shù)！BuAuBlAl9/26/2022192. Convex Polygon IntersectionCall the edges where Au, Al, Bu and Bl are: e1, e2, e3 and e4 respectively.Next x-event should be chosen among four en

16、dpoints of e1, e2, e3 and e4, and four potential intersections: e1e3, e1e4, e2e3 and e2e4. 稱Au, Al, Bu, Bl所在的邊叫做e1,e2,e3,e4下一個(gè)x事件將在這四條邊的端點(diǎn)，以及兩兩交點(diǎn)中選出BuAuBlAlO(n)9/26/2022203.Common solution:Divide-and-Conquer Algorithm D&C通常的分治解法9/26/2022213. Divide-and-Conquer Algorithm Divide: Partition the n h-pla

17、nes into two sets of size n/2.Conquer: Compute feasible region recursively of both two subsets.Combine: Compute intersection of two convex region, by CPI2分: 將n個(gè)半平面分成兩個(gè)n/2的集合.治: 對兩子集合遞歸求解半平面交.合: 將前一步算出來的兩個(gè)交(凸多邊形)利用第2章的CPI求解.9/26/2022223. Divide-and-Conquer Algorithm The total time complexity of the s

18、olution can be calculated via recursive equation.總時(shí)間復(fù)雜度可以用遞歸分析法.CPI9/26/2022234.My New Solution: Sort-and-Incremental Algorithm S&I我自創(chuàng)的排序增量算法9/26/2022244. Sort-and-Incremental AlgorithmDefinition of h-planes polar angle:for h-plane like x-yconstant, we define its polar angle to . 半平面的極角定義: 比如x-y常數(shù)的半

19、平面，定義它的極角為.-9/26/2022254. Sort-and-Incremental AlgorithmStep 1: Separate the h-planes into two sets. One has polar angles of (-, , the other has those of (-, -(, .Step 1: 將半平面分成兩部分，一部分極角范圍(-, ，另一部分范圍(-, -(, 9/26/2022264. Sort-and-Incremental Algorithm考慮(-, 的半平面(另一個(gè)集合類似地做Step3/4)，將他們極角排序。對極角相同的半平面，根據(jù)

20、常數(shù)項(xiàng)保留其中之一。Step 2: Consider the set of h-planes in (-, (the other set should also go through step 3 and 4 similarly). Sort them by the polar angle. For the h-planes with the same polar angle, we can keep only one down (delete all others) according to the constant of these h-planes9/26/2022274. Sort-a

21、nd-Incremental Algorithm從排序后極角最小兩個(gè)半平面開始，求出它們的交點(diǎn)并且將他們押入棧。Step 3: Starting from two h-planes with the least polar angle, compute their intersection. Push them two into a stack. 9/26/2022284. Sort-and-Incremental Algorithm每次按照極角從小到大順序增加一個(gè)半平面，算出它與棧頂半平面的交點(diǎn)。Step 3: Each time, add one more h-plane by incre

22、asing order of polar angles, and calculate the intersection of it and the top h-plane in stack. 9/26/2022294. Sort-and-Incremental Algorithm如果當(dāng)前的交點(diǎn)在棧頂兩個(gè)半平面交點(diǎn)的右邊，出棧（pop）。Step 3: If this intersection is to the right of the intersection of top two h-planes in stack, we pop the stack once. 9/26/2022304.

23、 Sort-and-Incremental AlgorithmStep 3:9/26/2022314. Sort-and-Incremental Algorithm前問我們說到出棧，出棧只需要一次么？Nie!我們要繼續(xù)交點(diǎn)檢查，如果還在右邊我們要繼續(xù)出棧，直到當(dāng)前交點(diǎn)在棧頂交點(diǎn)的左邊。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. 9/26/2022324. Sort-and-Incrementa

24、l Algorithm相鄰半平面的交點(diǎn)組成半個(gè)凸多邊形。我們有兩個(gè)點(diǎn)集，(-, 給出上半個(gè)，(-, -(, 給出下半個(gè) Step 4: Intersections of adjacent h-plane pairs in stack form half a convex polygon. For the two sets, we have two halves (-, gives an upper hull and (-, -(, gives a lower hull.9/26/2022334. Sort-and-Incremental Algorithm相鄰半平面的交點(diǎn)組成半個(gè)凸多邊形。我們

25、有兩個(gè)點(diǎn)集，(-, 給出上半個(gè)，(-, -(, 給出下半個(gè) Step 4: Intersections of adjacent h-plane pairs in stack form half a convex polygon. For the two sets, we have two halves (-, gives an upper hull and (-, -(, gives a lower hull.upper hull上殼lower hull下殼9/26/2022344. Sort-and-Incremental Algorithm初始時(shí)候，四個(gè)指針p1, p2, p3 and p

26、4 指向上/下凸殼的最左最右邊p1, p3向右走，p2, p4向左走Step 4: At the beginning, four pointers p1, p2, p3 and p4 indicate leftmost/rightmost edges of both upper and lower hulls.p1 and p3 move rightwards, while p2 and p4 walks leftwards. p3p4p1p2upper hull上殼lower hull下殼9/26/2022354. Sort-and-Incremental Algorithm任意時(shí)刻，如果最

27、左邊的交點(diǎn)不滿足p1/p3所在半平面的限制，我們相信這個(gè)交點(diǎn)需要刪除p1或p3走向它右邊的相鄰邊Step 4: At anytime, if the leftmost intersection is against the feasible region provided by p1 or p3, we are sure the leftmost one is to be removed.Naturally, p1 or p3 walks rightwards to its adjacent edge. p3p4p1p29/26/2022364. Sort-and-Incremental Al

28、gorithm類似地我們處理最右邊的交點(diǎn)Step 4: The judgment holds analogously for rightmost intersection with p2 and p4. p3p2p1p49/26/2022374. Sort-and-Incremental Algorithm類似地我們處理最右邊的交點(diǎn)Step 4: The judgment holds analogously for rightmost intersection with p2 and p4. p3p4p2p19/26/2022384. Sort-and-Incremental Algorith

29、m重復(fù)運(yùn)作直到不再有更新出現(xiàn)迭代Step 4: Do the above removing repeatedly until there is no more update. p3p4p2p19/26/2022394. Sort-and-Incremental AlgorithmEverything except sorting (Step 2) in S&I algorithm remain linear O(n) running time. Usually we use quick-sort. The total complexity is O(nlogn), with fairly sm

30、all constant factor hidden. 除了Step2中的排序以外，S&I算法的每一步都是線性的。通常我們用快速排序?qū)崿F(xiàn)Step2，總的時(shí)間復(fù)雜度為O(nlogn)，隱蔽其中的常數(shù)因子很小9/26/2022405.Conclusion and Practical Use總結(jié)和實(shí)際應(yīng)用9/26/2022415. Conclusion and Practical UseGreat ideas need landing gear as well as wings. S&I algorithm seems to work in the same time complexity as D

31、&C algorithm, but some overwhelming advantages of implementing S&I holds.Great ideas need landing gear as well as wings. S&I算法似乎和D&C算法時(shí)間復(fù)雜度相同，但是它有著壓倒性(overwhelming)的優(yōu)勢。9/26/2022425. Conclusion and Practical UseIt is much easier to code S&I program than D&C one. The program in C+ programming language

32、 takes less than 3KB.新的S&I算法代碼容易編寫，相對于D&C大大簡單化，C+程序語言實(shí)現(xiàn)S&I算法僅需3KB不到.9/26/2022435. Conclusion and Practical UseThe coefficient hidden under S&I algorithms complexity is extraordinarily smaller than D&C, since we no longer need O(nlogn) number of intersection calculates. In general speaking, S&I program runs approx five times faster than D&C one.S&I算法復(fù)雜度中的系數(shù)，遠(yuǎn)小于D&C，因?yàn)槲覀儾辉傩枰狾(nlogn)次交點(diǎn)運(yùn)算. 通常意義上來講，S&I程序比D&C快五倍。9/26/2022445. Conclusion and Practical UseIf the given h-planes are all in (-, (or any span of ), S&I program can be shorten remarkably (to approximately