半平面交的新算法及其实用价值VIP

1、平平面交的新算法及其实用价值Keywords:Half-plane,Intersection,FeasibleRegion,Algorithm,Polygon,PracticalAbstract主旨：半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.§1introduceswhathalf-planeintersectionis§2preparesalinearalgorithmforconvexpolygoninterse

2、ction(abbr.CPI).Equippedwithsuchknowledge,acommonsolutionforHPIisbrieflydiscussedin§3.Then,mynewalgorithmemergesin4detailedly.Notonlyasaconclusionofthewholepaper,§5alsodiscussitsfurtherusagepracticallyandcomparesitwiththeolderalgorithmdescribedin3.§1什么是半平面交.§2凸多边形交预备知识.§3简要介

3、绍旧D&C算法.§4揭开我的新算法S&I神秘面纱.§5总结和实际运用.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:合并后区域形如凸多边形，可能无界。此时增加4个半平面保证面积有限(a)(b)?!?Eachh-planebuildsupatmostonesideoftheconvexpolygon,henc

7、e,theconvexregionwillbeboundedbyatmostnedges.Payattentiontheintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion5个半平面最多形成相交区域的条边，因此相交区域不超过n条边。注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。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.主要思想：以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形。Supposethereisaverticalsweepline,performingleft-to-rightsweep.Thex-coordinatestobesw

10、eptarecalleck-eventsAtanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon:假设有一个垂直的扫描线，从左向右才3描。我们称被扫描线扫描到的x坐标叫做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中靠上的，组成了当前多边形的内部区域。Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates.CalltheedgeswherAu,Al,BuandBlare:e1,e2,e3ande4respectively.Thenextx-eventshouldbechosenamongf

13、ourendpointsof1,e2,e3ande4,andfourpotentialintersections:elCe3elAe4,e2ce3ande2ce4.当然,我们不能扫描所有有理数！称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寸问复杂度可以用递归分析法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）,将他们极角排序。对极角相同的平平面，根据常数项保留其中之一。?! ? ?! ? ?! ? ?! ? ?! ? ?! ? ?!?Step3:从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。如果当前的交点在栈顶两个半平面交点的右边，出栈（p

18、op）。前问我们说到出栈，出栈只需要一次么？Nie!我们要继续交点检查，如果还在右边我们要继续出栈，直到当前交点在栈顶交点的左边。Step4:相邻半平面的交点组成半个凸多边形。我们有两个点集，（-?,?M给出上半个，（-K-?4U（?砥建给出下半个初始时候，四个指针p1, p2, p3 and p4指向上/下凸壳的最左最右边p1, p3向右走，p2,p4向左走。任意时刻，如果最左边的交点不满足p1/p3所在半平面的限制,我们相信这个交点需要删除pl或p3走向它右边的相邻边。类似地我们处理最右边的交点。重复运作直到不再有更新出现一一迭代。?! ? ?除了Step2中的排序以外，S&I算法

19、的每一步都是线性的。通常我们用快速排序实现Step?总的时间复杂度为O(nlogn),隐蔽其中的常数因子很小7. PracticalValueandLinearapproachGreatideasneedlandinggearaswellaswings.S&法似乎和D&C算法时间复杂度相同，但是它有着压倒性(overwhelming)勺优势。华新的S&I算法代码容易编写，相对于D&C大大简单化，C+程序语言实现S&I算法仅需3KB不到.SS&I算法复杂度中的系数，远小于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.份如果给定半平面均在(-?砥？可(或任意一个跨度为冗的区间)，S&I算法可被显着缩短，C+程序只需要约二十行。USAICO比赛中就出现了这样一题。AsymptoticalOptimizationtolinear:Thebottleneckofthisalgorithmissorting.PayattentionthesortingisNOTacomparisonsort(sortingbasedoncomparison)!Thekeywordsforelementstobesortedarep

22、olarangles,whichcanbecertainlydeterminedbygradient-adecimalfraction.Sincethen,wecanreplacethO(nlogn)quick-sorttoO(n)radix-sortTheasymptoticalcomplexityofalgorithmcandecreasetoO(n).AnywayO(n)approachusuallyrunsslowerthanlognonesforitsadditionalmemoryusage!本算法瓶颈是排序，这里的排序不是比较排序，因此可以将快速排序替换成基数排序，降低程序渐进时间复杂度到线性。ThesentimentofmycreationAninventiondoesnotattributetosomeonewhocomesupwithideas.Mostpeoplehaveideas.Thedifference