算法合集之《半平面交的新算法及其實用價值》-文庫吧
2025-09-17 20:30 本頁面
【正文】 on sometimes yields a line, a ray, a linesegment, a point or an empty region. 注意相交后的區(qū)域，有可能是一個直線、射線、線段或者點，當然也可能是空集。 line ray linesegment point empty set November 12, 2021 Zeyuan Zhu 14 2. Convex Polygon Intersection – CPI 凸多邊形交預備知識 November 12, 2021 Zeyuan Zhu 15 2. Convex Polygon Intersection Intersecting two convex polygons A and B into a single one. We will sketch out an efficient way, named plane sweep method. 求兩個凸多邊形 A和 B的交（一個新凸多邊形）。 我們描繪一個平面掃描法 。 Polygon A Polygon B November 12, 2021 Zeyuan Zhu 16 2. Convex Polygon Intersection Main 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) 主要思想 : 以兩凸邊形邊的交點為分界點，將邊分為內(nèi)、外兩種。 內(nèi)邊互相連接，成為所求多邊形（圖中粗線條） Polygon A Polygon B November 12, 2021 Zeyuan Zhu 17 2. Convex Polygon Intersection Suppose there is a vertical sweep line, performing lefttoright sweep. At anytime, there are at most four intersections from sweep line to either given polygon. 假設有一個垂直的掃描線，從左向右掃描 任何時刻，掃描線和兩個多邊形最多 4個交點 Polygon A Polygon B Bu Au Bl Al Sweep line November 12, 2021 Zeyuan Zhu 18 2. Convex Polygon Intersection the 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中靠上的，組成了當前多邊形的內(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坐標叫做 x事件。 當然，我們不能掃描所有有理數(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事件將在這四條邊的端點，以及兩兩交點中選出 Bu Au Bl Al O(n) November 12, 2021 Zeyuan Zhu 21 3. Common solution: DivideandConquer Algorithm – Damp。C 通常的分治解法 November 12, 2021 Zeyuan Zhu 22 3. DivideandConquer Algorithm Divide: Partition the n hplanes into two sets of size n/2. Conquer: Compute feasible region recursively of both two subsets. Combine: Compute inters
教學課件相關推薦
鄂ICP備17016276號-1