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

Allgreatideasarecontroversial,orhavebeenatonetime.偉大的理論都是有爭議的，或者至少曾經(jīng)是有爭議的。

GilbertSeldes(1893-1970)U.S.theater,film,andradiocritic.理論的爭議12/19/20221ZeyuanZhuAllgreatideasarecontroversAwisemanwillmakemoreopportunitiesthanhefinds.聰明人總是制造更多的機(jī)會，而不是去等待尋找。FrancisBacon(1561-1626)Englishphilosopher,statesman,andlawyer.制造機(jī)會12/19/20222ZeyuanZhuAwisemanwillmakemoreoppoAftertheleaveshavefallen,wereturntoaplainsenseofthings.Itisasifwehadcometoanendoftheimagination.葉落時分，我們回到一切的本來面目，這樣就與創(chuàng)造與幻想的終點(diǎn)不遠(yuǎn)了。WallaceStevens(1879-1955)U.S.poet忘記過去，揭開本來面目12/19/20223ZeyuanZhuAftertheleaveshavefallen,Hello,LadiesandGentlemen.

女士們先生們大家好

Bonjour,MesdamesetMessieurs.

Witajcie,PanieiPanowie.

Hallo,DamenundHerren.

Bunaziua,DoamenelorsiDomnilor.

Ciao,signoreesignori.ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱澤園,高三,南京市外國語學(xué)校,江蘇,中國12/19/20224ZeyuanZhuHello,LadiesandGentlemen.

NewalgorithmforHalf-planeIntersectionanditsPracticalValue

––ThesisforChineseTeamSelectingContest2006

半平面交的新算法及其實(shí)用價值

––中國代表隊2006年選拔賽論文ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱澤園,高三,南京市外國語學(xué)校,江蘇,中國12/19/20225ZeyuanZhuNewalgorithmforHalf-planeIProjectOverview–全文總攬Aim:PresentanewO(nlogn)algorithmforhalf-planeintersection(abbr.HPI),whichisoneofthemostheatedlydiscussedproblemsincomputerscience;emphasizeitsadvantagesinpracticalapplication,andtosomeextent,reducethecomplexitytoO(n).However,thenewalgorithmwillbeextraordinarilyeasytobeimplemented.主旨:半平面的交是當(dāng)今學(xué)術(shù)界熱烈討論的問題之一，本文將介紹一個全新的O(nlogn)半平面交算法，強(qiáng)調(diào)它在實(shí)際運(yùn)用中的價值，并且在某種程度上將復(fù)雜度下降至O(n)線性。最重要的是，我將介紹的算法非常便于實(shí)現(xiàn).12/19/20226ZeyuanZhuProjectOverview–全文總攬Aim:PrProjectOverview–全文總攬§1introduceswhatHalf-PlaneIntersection(HPI)is.什么是半平面交.§2preparesaconvexpolygonintersection(CPI).凸多邊形交預(yù)備知識.§3brieflydiscussacommonsolutionforHPI–D&C.簡要介紹舊D&C算法.§4mynewalgorithmS&Iemergesdetailedly.揭開我的新算法S&I神秘面紗.§5conclusionanddiscussiononfurtherpracticaluse.總結(jié)和實(shí)際運(yùn)用.12/19/20227ZeyuanZhuProjectOverview–全文總攬§1intr1. StatementoftheProblem-問題概述12/19/20228ZeyuanZhu1. StatementoftheProblem-1.StatementoftheProblemAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by()crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.3x-2y=1x+2y1眾所周知，直線常用ax+by=c表示，類似地半平面以ax+by()c為定義。12/19/20229ZeyuanZhu1.StatementoftheProblemA1.StatementoftheProblemGivennhalf-planes,aix+biyci(1in),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.給定n個形如aix+biyci的半平面，找到所有滿足它們的點(diǎn)所組成的點(diǎn)集12/19/202210ZeyuanZhu1.StatementoftheProblemGi1.StatementoftheProblemFeasibleregionformsashapeofconvexhullpossiblyunbounded.

Addfourh-planesformingarectangle,tomaketheintersectionareafinite.合并后區(qū)域形如凸多邊形，可能無界

此時增加4個半平面保證面積有限12/19/202211ZeyuanZhu1.StatementoftheProblemFe1.StatementoftheProblemEachh-planebuildsupatmostonesideoftheconvexpolygon.Hence,Theconvexregionwillbeboundedbyatmostnedges.每個半平面最多形成相交區(qū)域的一條邊，因此相交區(qū)域不超過n條邊。6h-planes

pentagon9h-planes

pentagon12/19/202212ZeyuanZhu1.StatementoftheProblemEa1.StatementoftheProblemPayattentionthatintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.注意相交后的區(qū)域，有可能是一個直線、射線、線段或者點(diǎn)，當(dāng)然也可能是空集。linerayline-segmentpointemptyset12/19/202213ZeyuanZhu1.StatementoftheProblemPa2. ConvexPolygonIntersection–CPI

凸多邊形交預(yù)備知識12/19/202214ZeyuanZhu2. ConvexPolygonIntersection2.ConvexPolygonIntersectionIntersectingtwoconvexpolygonsAandBintoasingleone.Wewillsketchoutanefficientway,namedplanesweepmethod.求兩個凸多邊形A和B的交（一個新凸多邊形）。我們描繪一個平面掃描法。PolygonAPolygonB12/19/202215ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionMainidea:Regardintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Segmentsofinneredgesestablishtiestoeachother,andformapolygon.(inbold)主要思想:以兩凸邊形邊的交點(diǎn)為分界點(diǎn)，將邊分為內(nèi)、外兩種。內(nèi)邊互相連接，成為所求多邊形（圖中粗線條）PolygonAPolygonB12/19/202216ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionSupposethereisaverticalsweepline,performingleft-to-rightsweep.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon.假設(shè)有一個垂直的掃描線，從左向右掃描任何時刻，掃描線和兩個多邊形最多4個交點(diǎn)PolygonAPolygonBBuAuBlAlSweepline12/19/202217ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectiontheloweronebetweenAuandBu,andtheupperonebetweenAlandBl,formanintervalofthecurrentinnerregion–theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，組成了當(dāng)前多邊形的內(nèi)部區(qū)域PolygonAPolygonBBuAuBlAlSweepline12/19/202218ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionLetuscallthex-coordinatestobesweptx-events.Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates!我們稱被掃描線掃描到的x坐標(biāo)叫做x事件。當(dāng)然，我們不能掃描所有有理數(shù)！BuAuBlAl12/19/202219ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionCalltheedgeswhereAu,Al,BuandBlare:e1,e2,e3ande4respectively.Nextx-eventshouldbechosenamongfourendpointsofe1,e2,e3ande4,andfourpotentialintersections:e1∩e3,e1∩e4,e2∩e3ande2∩e4.稱Au,Al,Bu,Bl所在的邊叫做e1,e2,e3,e4下一個x事件將在這四條邊的端點(diǎn)，以及兩兩交點(diǎn)中選出BuAuBlAlO(n)12/19/202220ZeyuanZhu2.ConvexPolygonIntersection3. Commonsolution:

Divide-and-ConquerAlgorithm–D&C

通常的分治解法12/19/202221ZeyuanZhu3. Commonsolution:

Divide-and3.Divide-and-ConquerAlgorithmDivide:Partitionthenh-planesintotwosetsofsizen/2.Conquer:Computefeasibleregionrecursivelyofbothtwosubsets.Combine:Computeintersectionoftwoconvexregion,byCPI§2分:將n個半平面分成兩個n/2的集合.治:對兩子集合遞歸求解半平面交.合:將前一步算出來的兩個交(凸多邊形)利用第2章的CPI求解.12/19/202222ZeyuanZhu3.Divide-and-ConquerAlgorit3.Divide-and-ConquerAlgorithmThetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation.總時間復(fù)雜度可以用遞歸分析法.CPI12/19/202223ZeyuanZhu3.Divide-and-ConquerAlgorit4. MyNewSolution:

Sort-and-IncrementalAlgorithm–S&I

我自創(chuàng)的排序增量算法12/19/202224ZeyuanZhu4. MyNewSolution:

Sort-and-4.Sort-and-IncrementalAlgorithmDefinitionofh-plane’spolarangle:

forh-planelikex-yconstant,wedefineitspolarangleto?π.半平面的極角定義:比如x-y常數(shù)的半平面，定義它的極角為?π.?π-?π12/19/202225ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep1:Separatetheh-planesintotwosets.Onehaspolaranglesof(-?π,?π],theotherhasthoseof(-π,-?π]∪(?π,π].Step1:將半平面分成兩部分，一部分極角范圍(-?π,?π]，另一部分范圍(-π,-?π]∪(?π,π]12/19/202226ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm考慮(-?π,?π]的半平面(另一個集合類似地做Step3/4)，將他們極角排序。對極角相同的半平面，根據(jù)常數(shù)項保留其中之一。Step2:Considerthesetofh-planesin(-?π,?π](theothersetshouldalsogothroughstep3and4similarly).Sortthembythepolarangle.Fortheh-planeswiththesamepolarangle,wecankeeponlyonedown(deleteallothers)accordingtotheconstantoftheseh-planes12/19/202227ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm從排序后極角最小兩個半平面開始，求出它們的交點(diǎn)并且將他們押入棧。Step3:Startingfromtwoh-planeswiththeleastpolarangle,computetheirintersection.Pushthemtwointoastack.12/19/202228ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm每次按照極角從小到大順序增加一個半平面，算出它與棧頂半平面的交點(diǎn)。Step3:Eachtime,addonemoreh-planebyincreasingorderofpolarangles,andcalculatetheintersectionofitandthetoph-planeinstack.12/19/202229ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm如果當(dāng)前的交點(diǎn)在棧頂兩個半平面交點(diǎn)的右邊，出棧（pop）。Step3:Ifthisintersectionistotherightoftheintersectionoftoptwoh-planesinstack,wepopthestackonce.12/19/202230ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep3:12/19/202231ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm前問我們說到出棧，出棧只需要一次么？Nie!我們要繼續(xù)交點(diǎn)檢查，如果還在右邊我們要繼續(xù)出棧，直到當(dāng)前交點(diǎn)在棧頂交點(diǎn)的左邊。Step3:…wepopthestackonce.Once?Isitenough?Nie!Dothisrepeatedlyuntilitistotheleftofthetopintersection.12/19/202232ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相鄰半平面的交點(diǎn)組成半個凸多邊形。我們有兩個點(diǎn)集，(-?π,?π]給出上半個，(-π,-?π]∪(?π,π]給出下半個Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-?π,?π]givesanupperhulland

(-π,-?π]∪(?π,π]givesalowerhull.12/19/202233ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相鄰半平面的交點(diǎn)組成半個凸多邊形。我們有兩個點(diǎn)集，(-?π,?π]給出上半個，(-π,-?π]∪(?π,π]給出下半個Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-?π,?π]givesanupperhulland

(-π,-?π]∪(?π,π]givesalowerhull.upperhull上殼lowerhull下殼12/19/202234ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm初始時候，四個指針p1,p2,p3andp4指向上/下凸殼的最左最右邊p1,p3向右走，p2,p4向左走Step4:Atthebeginning,fourpointersp1,p2,p3andp4indicateleftmost/rightmostedgesofbothupperandlowerhulls.p1andp3moverightwards,whilep2andp4walksleftwards.p3p4p1p2upperhull上殼lowerhull下殼12/19/202235ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm任意時刻，如果最左邊的交點(diǎn)不滿足p1/p3所在半平面的限制，我們相信這個交點(diǎn)需要刪除p1或p3走向它右邊的相鄰邊Step4:Atanytime,iftheleftmostintersectionisagainstthefeasibleregionprovidedbyp1orp3,wearesuretheleftmostoneistoberemoved.Naturally,p1orp3walksrightwardstoitsadjacentedge.p3p4p1p212/19/202236ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm類似地我們處理最右邊的交點(diǎn)Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p2p1p412/19/202237ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm類似地我們處理最右邊的交點(diǎn)Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p4p2p112/19/202238ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm重復(fù)運(yùn)作直到不再有更新出現(xiàn)——迭代Step4:Dotheaboveremovingrepeatedlyuntilthereisnomoreupdate.p3p4p2p112/19/202239ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmEverythingexceptsorting(Step2)inS&Ialgorithmremainlinear–O(n)runningtime.Usuallyweusequick-sort.ThetotalcomplexityisO(nlogn),withfairlysmallconstantfactorhidden.除了Step2中的排序以外，S&I算法的每一步都是線性的。通常我們用快速排序?qū)崿F(xiàn)Step2，總的時間復(fù)雜度為O(nlogn)，隱蔽其中的常數(shù)因子很小12/19/202240ZeyuanZhu4.Sort-and-IncrementalAlgori5. ConclusionandPracticalUse

總結(jié)和實(shí)際應(yīng)用12/19/202241ZeyuanZhu5. ConclusionandPracticalU5.ConclusionandPracticalUseGreatideasneedlandinggearaswellaswings.S&IalgorithmseemstoworkinthesametimecomplexityasD&Calgorithm,butsomeoverwhelmingadvantagesofimplementingS&Iholds.Greatideasneedlandinggearaswellaswings.S&I算法似乎和D&C算法時間復(fù)雜度相同，但是它有著壓倒性(overwhelming)的優(yōu)勢。12/19/202242ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseItismucheasiertocodeS&IprogramthanD&Cone.TheprograminC++programminglanguagetakeslessthan3KB.新的S&I算法代碼容易編寫，相對于D&C大大簡單化，C++程序語言實(shí)現(xiàn)S&I算法僅需3KB不到.12/19/202243ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseThecoefficienthiddenunderS&Ialgorithm’scomplexityisextraordinarilysmallerthanD&C,sincewenolongerneedO(nlogn)numberofintersectioncalculates.Ingeneralspeaking,S&IprogramrunsapproxfivetimesfasterthanD&Cone.S&I算法復(fù)雜度中的系數(shù)，遠(yuǎn)小于D&C，因?yàn)槲覀儾辉傩枰狾(nlogn)次交點(diǎn)運(yùn)算.通常意義上來講，S&I程序比D&C快五倍。12/19/202244ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseIfthegivenh-planesareallin(-?π,?π](oranyspanofπ),S&Iprogramcanbeshortenremarkably(toapproximatelytwentylinesinC++),butD&Cprogrammaynot.AninformaticsproblemappearedinUSAInvitationalComputingOlympiadcontestwithsuchpurpose.如果給定半平面均在(-?π,?π]（或任意一個跨度為π的區(qū)間），S&I算法可被顯著縮短，C++程序只需要約二十行。USAICO比賽中就出現(xiàn)了這樣一題。12/19/202245ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseThebottleneckofthisalgorithmissorting.PayattentionthesortingisNOTacomparisonsort(sortingbasedoncomparison)!Sincethen,wecanreplacetheO(nlogn)quick-sorttoO(n)radix-sorttodecreasethe

asymptoticaltimecomplexitytoO(n).本算法瓶頸是排序，這里的排序不是比較排序，因此可以將快速排序替換成基數(shù)排序，降低程序漸進(jìn)時間復(fù)雜度到線性。AnywayO(n)approachusuallyrunsslowerthannlognonesforitsadditionalmemoryusage!12/19/202246ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUse<美麗心靈>諾貝爾獎得主JohnNash

原創(chuàng)的理論——originalidea創(chuàng)新與信息學(xué)競賽創(chuàng)新與技術(shù)我心目中的創(chuàng)新——最重要的是思想創(chuàng)新，其次是行為創(chuàng)新，再其次是文章創(chuàng)新，再再其次才是語言創(chuàng)新思想實(shí)踐Theprincipalmarkofgeniusisnotperfectionbutoriginality,theopeningofnewfrontiers.AuthurKoestler(1905-1983)Hungarian-bornBritishwriterandjounalist.12/19/202247ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUse創(chuàng)新如高山山，

快馬加鞭未下鞍。

驚回首，離天三尺三。山，

倒海翻江卷巨瀾。

奔騰急，萬馬戰(zhàn)猶酣。山，

刺破青天鍔未殘。

天欲墮，賴以拄其間。悵寥廓，問蒼茫大地，誰主沉浮。俱往矣，數(shù)風(fēng)流人物，還看今朝。12/19/202248ZeyuanZhu5.ConclusionandPracticalUsAllgreatideasarecontroversial,orhavebeenatonetime.偉大的理論都是有爭議的，或者至少曾經(jīng)是有爭議的。

GilbertSeldes(1893-1970)U.S.theater,film,andradiocritic.理論的爭議12/19/202249ZeyuanZhuAllgreatideasarecontroversAwisemanwillmakemoreopportunitiesthanhefinds.聰明人總是制造更多的機(jī)會，而不是去等待尋找。FrancisBacon(1561-1626)Englishphilosopher,statesman,andlawyer.制造機(jī)會12/19/202250ZeyuanZhuAwisemanwillmakemoreoppoAftertheleaveshavefallen,wereturntoaplainsenseofthings.Itisasifwehadcometoanendoftheimagination.葉落時分，我們回到一切的本來面目，這樣就與創(chuàng)造與幻想的終點(diǎn)不遠(yuǎn)了。WallaceStevens(1879-1955)U.S.poet忘記過去，揭開本來面目12/19/202251ZeyuanZhuAftertheleaveshavefallen,Hello,LadiesandGentlemen.

女士們先生們大家好

Bonjour,MesdamesetMessieurs.

Witajcie,PanieiPanowie.

Hallo,DamenundHerren.

Bunaziua,DoamenelorsiDomnilor.

Ciao,signoreesignori.ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱澤園,高三,南京市外國語學(xué)校,江蘇,中國12/19/202252ZeyuanZhuHello,LadiesandGentlemen.

NewalgorithmforHalf-planeIntersectionanditsPracticalValue

––ThesisforChineseTeamSelectingContest2006

半平面交的新算法及其實(shí)用價值

––中國代表隊2006年選拔賽論文ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱澤園,高三,南京市外國語學(xué)校,江蘇,中國12/19/202253ZeyuanZhuNewalgorithmforHalf-planeIProjectOverview–全文總攬Aim:PresentanewO(nlogn)algorithmforhalf-planeintersection(abbr.HPI),whichisoneofthemostheatedlydiscussedproblemsincomputerscience;emphasizeitsadvantagesinpracticalapplication,andtosomeextent,reducethecomplexitytoO(n).However,thenewalgorithmwillbeextraordinarilyeasytobeimplemented.主旨:半平面的交是當(dāng)今學(xué)術(shù)界熱烈討論的問題之一，本文將介紹一個全新的O(nlogn)半平面交算法，強(qiáng)調(diào)它在實(shí)際運(yùn)用中的價值，并且在某種程度上將復(fù)雜度下降至O(n)線性。最重要的是，我將介紹的算法非常便于實(shí)現(xiàn).12/19/202254ZeyuanZhuProjectOverview–全文總攬Aim:PrProjectOverview–全文總攬§1introduceswhatHalf-PlaneIntersection(HPI)is.什么是半平面交.§2preparesaconvexpolygonintersection(CPI).凸多邊形交預(yù)備知識.§3brieflydiscussacommonsolutionforHPI–D&C.簡要介紹舊D&C算法.§4mynewalgorithmS&Iemergesdetailedly.揭開我的新算法S&I神秘面紗.§5conclusionanddiscussiononfurtherpracticaluse.總結(jié)和實(shí)際運(yùn)用.12/19/202255ZeyuanZhuProjectOverview–全文總攬§1intr1. StatementoftheProblem-問題概述12/19/202256ZeyuanZhu1. StatementoftheProblem-1.StatementoftheProblemAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by()crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.3x-2y=1x+2y1眾所周知，直線常用ax+by=c表示，類似地半平面以ax+by()c為定義。12/19/202257ZeyuanZhu1.StatementoftheProblemA1.StatementoftheProblemGivennhalf-planes,aix+biyci(1in),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.給定n個形如aix+biyci的半平面，找到所有滿足它們的點(diǎn)所組成的點(diǎn)集12/19/202258ZeyuanZhu1.StatementoftheProblemGi1.StatementoftheProblemFeasibleregionformsashapeofconvexhullpossiblyunbounded.

Addfourh-planesformingarectangle,tomaketheintersectionareafinite.合并后區(qū)域形如凸多邊形，可能無界

此時增加4個半平面保證面積有限12/19/202259ZeyuanZhu1.StatementoftheProblemFe1.StatementoftheProblemEachh-planebuildsupatmostonesideoftheconvexpolygon.Hence,Theconvexregionwillbeboundedbyatmostnedges.每個半平面最多形成相交區(qū)域的一條邊，因此相交區(qū)域不超過n條邊。6h-planes

pentagon9h-planes

pentagon12/19/202260ZeyuanZhu1.StatementoftheProblemEa1.StatementoftheProblemPayattentionthatintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.注意相交后的區(qū)域，有可能是一個直線、射線、線段或者點(diǎn)，當(dāng)然也可能是空集。linerayline-segmentpointemptyset12/19/202261ZeyuanZhu1.StatementoftheProblemPa2. ConvexPolygonIntersection–CPI

凸多邊形交預(yù)備知識12/19/202262ZeyuanZhu2. ConvexPolygonIntersection2.ConvexPolygonIntersectionIntersectingtwoconvexpolygonsAandBintoasingleone.Wewillsketchoutanefficientway,namedplanesweepmethod.求兩個凸多邊形A和B的交（一個新凸多邊形）。我們描繪一個平面掃描法。PolygonAPolygonB12/19/202263ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionMainidea:Regardintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Segmentsofinneredgesestablishtiestoeachother,andformapolygon.(inbold)主要思想:以兩凸邊形邊的交點(diǎn)為分界點(diǎn)，將邊分為內(nèi)、外兩種。內(nèi)邊互相連接，成為所求多邊形（圖中粗線條）PolygonAPolygonB12/19/202264ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionSupposethereisaverticalsweepline,performingleft-to-rightsweep.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon.假設(shè)有一個垂直的掃描線，從左向右掃描任何時刻，掃描線和兩個多邊形最多4個交點(diǎn)PolygonAPolygonBBuAuBlAlSweepline12/19/202265ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectiontheloweronebetweenAuandBu,andtheupperonebetweenAlandBl,formanintervalofthecurrentinnerregion–theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，組成了當(dāng)前多邊形的內(nèi)部區(qū)域PolygonAPolygonBBuAuBlAlSweepline12/19/202266ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionLetuscallthex-coordinatestobesweptx-events.Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates!我們稱被掃描線掃描到的x坐標(biāo)叫做x事件。當(dāng)然，我們不能掃描所有有理數(shù)！BuAuBlAl12/19/202267ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionCalltheedgeswhereAu,Al,BuandBlare:e1,e2,e3ande4respectively.Nextx-eventshouldbechosenamongfourendpointsofe1,e2,e3ande4,andfourpotentialintersections:e1∩e3,e1∩e4,e2∩e3ande2∩e4.稱Au,Al,Bu,Bl所在的邊叫做e1,e2,e3,e4下一個x事件將在這四條邊的端點(diǎn)，以及兩兩交點(diǎn)中選出BuAuBlAlO(n)12/19/202268ZeyuanZhu2.ConvexPolygonIntersection3. Commonsolution:

Divide-and-ConquerAlgorithm–D&C

通常的分治解法12/19/202269ZeyuanZhu3. Commonsolution:

Divide-and3.Divide-and-ConquerAlgorithmDivide:Partitionthenh-planesintotwosetsofsizen/2.Conquer:Computefeasibleregionrecursivelyofbothtwosubsets.Combine:Computeintersectionoftwoconvexregion,byCPI§2分:將n個半平面分成兩個n/2的集合.治:對兩子集合遞歸求解半平面交.合:將前一步算出來的兩個交(凸多邊形)利用第2章的CPI求解.12/19/202270ZeyuanZhu3.Divide-and-ConquerAlgorit3.Divide-and-ConquerAlgorithmThetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation.總時間復(fù)雜度可以用遞歸分析法.CPI12/19/202271ZeyuanZhu3.Divide-and-ConquerAlgorit4. MyNewSolution:

Sort-and-IncrementalAlgorithm–S&I

我自創(chuàng)的排序增量算法12/19/202272ZeyuanZhu4. MyNewSolution:

Sort-and-4.Sort-and-IncrementalAlgorithmDefinitionofh-plane’spolarangle:

forh-planelikex-yconstant,wedefineitspolarangleto?π.半平面的極角定義:比如x-y常數(shù)的半平面，定義它的極角為?π.?π-?π12/19/202273ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep1:Separatetheh-planesintotwosets.Onehaspolaranglesof(-?π,?π],theotherhasthoseof(-π,-?π]∪(?π,π].Step1:將半平面分成兩部分，一部分極角范圍(-?π,?π]，另一部分范圍(-π,-?π]∪(?π,π]12/19/202274ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm考慮(-?π,?π]的半平面(另一個集合類似地做Step3/4)，將他們極角排序。對極角相同的半平面，根據(jù)常數(shù)項保留其中之一。Step2:Considerthesetofh-planesin(-?π,?π](theothersetshouldalsogothroughstep3and4similarly).Sortthembythepolarangle.Fortheh-planeswiththesamepolarangle,wecankeeponlyonedown(deleteallothers)accordingtotheconstantoftheseh-planes12/19/202275ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm從排序后極角最小兩個半平面開始，求出它們的交點(diǎn)并且將他們押入棧。Step3:Startingfromtwoh-planeswiththeleastpolarangle,computetheirintersection.Pushthemtwointoastack.12/19/202276ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm每次按照極角從小到大順序增加一個半平面，算出它與棧頂半平面的交點(diǎn)。Step3:Eachtime,addonemoreh-planebyincreasingorderofpolarangles,andcalculatetheintersectionofitandthetoph-planeinstack.12/19/202277ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm如果當(dāng)前的交點(diǎn)在棧頂兩個半平面交點(diǎn)的右邊，出棧（pop）。Step3:Ifthisintersectionistotherightoftheintersectionoftoptwoh-planesinstack,wepopthestackonce.12/19/202278ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep3:12/19/202279ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm前問我們說到出棧，出棧只需要一次么？Nie!我們要繼續(xù)交點(diǎn)檢查，如果還在右邊我們要繼續(xù)出棧，直到當(dāng)前交點(diǎn)在棧頂交點(diǎn)的左邊。Step3:…wepopthestackonce.Once?Isitenough?Nie!Dothisrepeatedlyuntilitistotheleftofthetopintersection.12/19/202280ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相鄰半平面的交點(diǎn)組成半個凸多邊形。我們有兩個點(diǎn)集，(-?π,?π]給出上半個，(-π,-?π]∪(?π,π]給出下半個Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-?π,?π]givesanupperhulland

(-π,-?π]∪(?π,π]givesalowerhull.12/19/202281ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相鄰半平面的交點(diǎn)組成半個凸多邊形。我們有兩個點(diǎn)集，(-?π,?π]給出上半個，(-π,-?π]∪(?π,π]給出下半個Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-?π,?π]givesanupperhulland

(-π,-?π]∪(?π,π]givesalowerhull.upperhull上殼lowerhull下殼12/19/202282ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm初始時候，四個指針p1,p2,p3andp4指向上/下凸殼的最左最右邊p1,p3向右走，p2,p4向左走Step4:Atthebeginning,fourpointersp1,p2,p3andp4indicateleftmost/rightmostedgesofbothupperandlowerhulls.p1andp3moverightwards,whilep2andp4walksleftwards.p3p4p1p2upperhull上殼lowerhull下殼12/19/202283ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm任意時刻，如果最左邊的交點(diǎn)不滿足p1/p3所在半平面的限制，我們相信這個交點(diǎn)需要刪除p1或p3走向它右邊的相鄰邊Step4:Atanytime,iftheleftmostintersectionisagainstthefeasibleregionprovidedbyp1orp3,wearesuretheleftmostoneistoberemoved.Naturally,p1orp3walksrightwardstoitsadjacentedge.p3p4p1p212/19/202284ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm類似地我們處理最右邊的交點(diǎn)Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p2p1p412/19/202285ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm類似地我們處理最右邊的交點(diǎn)Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p4p2p112/19/202286ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm重復(fù)運(yùn)作直到不再有更新出現(xiàn)——迭代Step4:Dotheaboveremovingrepeatedlyuntilthereisnomoreupdate.p3p4p2p112/19/202287ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmEverythingexceptsorting(Step2)inS&Ialgorithmremainlinear–O(n)runningtime.Usuallyweusequick-sort.ThetotalcomplexityisO(nlogn),withfairlysmallconstantfactorhidden.除了Step2中的