半平面交的新算法及其實用價值

1、平平面交的新算法及其實用價值Keywords:Half-plane,Intersection,FeasibleRegion,Algorithm,Polygon,PracticalAbstract主旨：半平面的交是當(dāng)今學(xué)術(shù)界熱烈討論的問題之一，本文將介紹一個全新的O(nlogn)半平面交算法，強(qiáng)調(diào)它在實際運用中的價值，并且在某種程度上將復(fù)雜度下降至O(n)線性。最重要的是，我將介紹的算法非常便于實現(xiàn).§1introduceswhathalf-planeintersectionis§2preparesalinearalgorithmforconvexpolygoninterse

2、ction(abbr.CPI).Equippedwithsuchknowledge,acommonsolutionforHPIisbrieflydiscussedin§3.Then,mynewalgorithmemergesin4detailedly.Notonlyasaconclusionofthewholepaper,§5alsodiscussitsfurtherusagepracticallyandcomparesitwiththeolderalgorithmdescribedin3.§1什么是半平面交.§2凸多邊形交預(yù)備知識.§3簡要介

3、紹舊D&C算法.§4揭開我的新算法S&I神秘面紗.§5總結(jié)和實際運用.TimestampsCameupwithitinApril2005;implementedpartlyinJune200g;problemsetinJuly2005;publicizedasapostinUSENET,November6,203151Thesub-problemofHPIappearedinUSAInvitationalComputingOlympiadcontest.1. IntroductionAlineinplaneisusuallyrepresentedasax+b

4、y=c.Similarly,itsinequalityformax+by<crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.Noticethatax+by<cand-ax-by<-cshowoppositeh-planesunlikeax+by=cand-ax-by=-c.HalfPlaneIntersectionabbr.HPI)considersthefollowingproblem:眾所周知，直線常用ax+by=c表示，類似地平平面以ax+byw()c為定義。Givennhalf-pl

5、anes,ax+biy<q(1<i<n),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.給定n個形如ax+biy&ci的平平面，找到所有滿足它們的點所組成的點集Asdescribes,thefeasibleregion,whichistheintersection,formsashapeofconvexhullbutpossiblyunbounded.However,weshalladdfourh-planesformingarectangle,whichislargeenough

6、tomakesuretheareaafterintersectionsfinitenthefollowingsections,wesupposethefeasibleregionboundedwithafinitearea.2 SetanHPIprobleminPekingUniversityOnlineJudge,withbriefintroductionaboutthealgorithm.3 URL:合并后區(qū)域形如凸多邊形，可能無界。此時增加4個半平面保證面積有限(a)(b)?!?Eachh-planebuildsupatmostonesideoftheconvexpolygon,henc

7、e,theconvexregionwillbeboundedbyatmostnedges.Payattentiontheintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion5個半平面最多形成相交區(qū)域的條邊，因此相交區(qū)域不超過n條邊。注意相交后的區(qū)域，有可能是一個直線、射線、線段或者點，當(dāng)然也可能是空集。2. ConvexPolygonIntersectior(abbr.CPI)IntersectingtwoconvexpolygonsAandBintoasingleone,canbeproperlys

8、olvedviaLineSegmentIntersectioninO(nlogn)time,whenthereareO(n)edges.Wewillsketchoutaneasierandmoreefficientway,namedbnesweepmethod求兩個凸多邊形A和B的交（一個新凸多邊形）。我們描繪一個平面掃描法Themainideaistocalculateintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredgesThesegmentsofnneredgeses

9、tablishtiestoeachother,andformtheshapeofapolygon,whichistheexpectedpolygonafterintersection.In,inneredgesareindicatedbythicksegments,whichformaboldoutlineoftheintersection.主要思想：以兩凸邊形邊的交點為分界點，將邊分為內(nèi)、外兩種。內(nèi)邊互相連接，成為所求多邊形。Supposethereisaverticalsweepline,performingleft-to-rightsweep.Thex-coordinatestobesw

10、eptarecalleck-eventsAtanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon:假設(shè)有一個垂直的掃描線，從左向右才3描。我們稱被掃描線掃描到的x坐標(biāo)叫做x事件。任何時刻，掃描線和兩個多邊形最多4個交點totheupperhullofA(namethatintersectiorAuforshort)4Assumethereisnoedgeinpolygonsparalleltothesweepline.Ifsuchsituationhappens,wecouldrotatetheplan

11、einproperangle,orelse,weneedgoodsensetojudgeagreatmanyspecialcases.夕tothelowerhullofA(namethatintersectionforshort)totheupperhullofB(namethatintersectiorBuforshort)uPolygon AX)IAl,S-tothelowerhullofB(namethatintersectionBlforshort)PolygonBSweep line?!?Lookat,theloweronebetweenintersectionsAuandBu,an

12、dtheupperonebetweenintersectionsAlandBl,formanintervalofthecurrentinnerregion-theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，組成了當(dāng)前多邊形的內(nèi)部區(qū)域。Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates.CalltheedgeswherAu,Al,BuandBlare:e1,e2,e3ande4respectively.Thenextx-eventshouldbechosenamongf

13、ourendpointsof1,e2,e3ande4,andfourpotentialintersections:elCe3elAe4,e2ce3ande2ce4.當(dāng)然,我們不能掃描所有有理數(shù)！稱Au,Al,Bu,Bl所在的邊叫做e1,e2,e3,e4下一個x事件將在這四條邊的端點，以及兩兩交點中選出。TheaboveoperationcouldbeimplementedwitO(n)runningtime,sincethereareO(n)x-events,andthemaintenanceAfj,Al,BuandBltakesonlyO(1).3. Commonsolution:4. Di

14、vide-and-ConquerAlgorithm(abbr.D&Q)Thebasicapproachissimple,dependsondivide-and-conqueridea.0-Divide:Partitionthenh-planesintotwosetsofsiz%and4n.C'Conquer:Computethefeasibleregion(intersection)recursivelyofbothtwosubsets.(土Combine:Computetheintersectionoftwoconvexpolygons,bylinearCPIalgorith

15、mdescribedin§2.事分:將n個半平面分成兩個n/2的集合.華治:對兩子集合遞歸求解半平面交.華合:將前一步算出來的兩個交(凸多邊形)利用第2章的CPI求解.Thetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation寸問復(fù)雜度可以用遞歸分析法5. MyNewSolution:6. Sort-and-IncrementalAlgorithm(abbr.S&I)Definitionofh-planespolarangle:fortheh-planelikex-y>constantwe

16、defineitspolarangleto?冗.fortheh-planelikex+y<constantwedefineitspolarangleto?冗.fortheh-planelikex+y>constantwedefineitspolarangleto?冗.fortheh-planelikex-y<constantwedefineitspolarangleto?-冗.?!?Definitionofh-planesconstant0fortheh-planelikeax+by<qwesayitsconstantis.MynewSort-and-Increment

17、alAlgorithmseemslengthysinceIamgoingtointroduceitindetails:Step1:將半平面分成兩部分，一部分極角范圍（-?砥？也另一部分范圍（-砥-?句U（?%iStep2考慮（-?為？用的半平面（另一個集合類似地做Step3/4）,將他們極角排序。對極角相同的平平面，根據(jù)常數(shù)項保留其中之一。?! ? ?! ? ?! ? ?! ? ?! ? ?! ? ?!?Step3:從排序后極角最小兩個半平面開始，求出它們的交點并且將他們押入棧。每次按照極角從小到大順序增加一個半平面，算出它與棧頂半平面的交點。如果當(dāng)前的交點在棧頂兩個半平面交點的右邊，出棧（p

18、op）。前問我們說到出棧，出棧只需要一次么？Nie!我們要繼續(xù)交點檢查，如果還在右邊我們要繼續(xù)出棧，直到當(dāng)前交點在棧頂交點的左邊。Step4:相鄰半平面的交點組成半個凸多邊形。我們有兩個點集，（-?,?M給出上半個，（-K-?4U（?砥建給出下半個初始時候，四個指針p1, p2, p3 and p4指向上/下凸殼的最左最右邊p1, p3向右走，p2,p4向左走。任意時刻，如果最左邊的交點不滿足p1/p3所在半平面的限制,我們相信這個交點需要刪除pl或p3走向它右邊的相鄰邊。類似地我們處理最右邊的交點。重復(fù)運作直到不再有更新出現(xiàn)一一迭代。?! ? ?除了Step2中的排序以外，S&I算法

19、的每一步都是線性的。通常我們用快速排序?qū)崿F(xiàn)Step?總的時間復(fù)雜度為O(nlogn),隱蔽其中的常數(shù)因子很小7. PracticalValueandLinearapproachGreatideasneedlandinggearaswellaswings.S&法似乎和D&C算法時間復(fù)雜度相同，但是它有著壓倒性(overwhelming)勺優(yōu)勢。華新的S&I算法代碼容易編寫，相對于D&C大大簡單化，C+程序語言實現(xiàn)S&I算法僅需3KB不到.SS&I算法復(fù)雜度中的系數(shù)，遠(yuǎn)小于D&C,因為我們不再需要O(nlogn)次交點運算.通常意義上來講，S

20、&I程序比D&C快五倍。Remark:intersectioncalculationsplaythemostimportantroleinbothalgorithmsduetoitsoperationalspeed(soslow,equivalenttohundredsofadditionoperations).CPI,thepreparativealgorithmwhichwillbecalledseveraltimesfromD&C,requiresO(n)numberofcalculations,whereforeitrisesthetotalrunningtim

21、eup.Besides,S&Icalculates(n)timesinanycase.份如果給定半平面均在(-?砥？可(或任意一個跨度為冗的區(qū)間)，S&I算法可被顯著縮短，C+程序只需要約二十行。USAICO比賽中就出現(xiàn)了這樣一題。AsymptoticalOptimizationtolinear:Thebottleneckofthisalgorithmissorting.PayattentionthesortingisNOTacomparisonsort(sortingbasedoncomparison)!Thekeywordsforelementstobesortedarep

22、olarangles,whichcanbecertainlydeterminedbygradient-adecimalfraction.Sincethen,wecanreplacethO(nlogn)quick-sorttoO(n)radix-sortTheasymptoticalcomplexityofalgorithmcandecreasetoO(n).AnywayO(n)approachusuallyrunsslowerthanlognonesforitsadditionalmemoryusage!本算法瓶頸是排序，這里的排序不是比較排序，因此可以將快速排序替換成基數(shù)排序，降低程序漸進(jìn)時間復(fù)雜度到線性。ThesentimentofmycreationAninventiondoesnotattributetosomeonewhocomesupwithideas.Mostpeoplehaveideas.Thedifference