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

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

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

3、紹舊D&C算法.§4揭開我的新算法S&I神秘面紗.§5總結(jié)和實(shí)際運(yùn)用.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個(gè)形如ax+biy&ci的平平面，找到所有滿足它們的點(diǎn)所組成的點(diǎn)集Asdescribes,thefeasibleregion,whichistheintersection,formsashapeofconvexhullbutpossiblyunbounded.However,weshalladdfourh-planesformingarectangle,whichislargeenough

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

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

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

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

10、eptarecalleck-eventsAtanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon:假設(shè)有一個(gè)垂直的掃描線，從左向右才3描。我們稱被掃描線掃描到的x坐標(biāo)叫做x事件。任何時(shí)刻，掃描線和兩個(gè)多邊形最多4個(gè)交點(diǎn)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下一個(gè)x事件將在這四條邊的端點(diǎn)，以及兩兩交點(diǎn)中選出。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個(gè)半平面分成兩個(gè)n/2的集合.華治:對(duì)兩子集合遞歸求解半平面交.華合:將前一步算出來的兩個(gè)交(凸多邊形)利用第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考慮（-?為？用的半平面（另一個(gè)集合類似地做Step3/4）,將他們極角排序。對(duì)極角相同的平平面，根據(jù)常數(shù)項(xiàng)保留其中之一。?! ? ?! ? ?! ? ?! ? ?! ? ?! ? ?!?Step3:從排序后極角最小兩個(gè)半平面開始，求出它們的交點(diǎn)并且將他們押入棧。每次按照極角從小到大順序增加一個(gè)半平面，算出它與棧頂半平面的交點(diǎn)。如果當(dāng)前的交點(diǎn)在棧頂兩個(gè)半平面交點(diǎn)的右邊，出棧（p

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

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

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

21、eup.Besides,S&Icalculates(n)timesinanycase.份如果給定半平面均在(-?砥？可(或任意一個(gè)跨度為冗的區(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)時(shí)間復(fù)雜度到線性。ThesentimentofmycreationAninventiondoesnotattributetosomeonewhocomesupwithideas.Mostpeoplehaveideas.Thedifference