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

半平面交的新算法及其实用价值1Keywords:Half-plane,Intersection,FeasibleRegion,Algorithm,Polygon,PracticalAbstract主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.§1introduceswhathalf-planeintersectionis.§2preparesalinearalgorithmforconvexpolygonintersection(abbr.CPI).Equippedwithsuchknowledge,acommonsolutionforHPIisbrieflydiscussedin§3.Then,mynewalgorithmemergesin§4detailedly.Notonlyasaconclusionofthewholepaper,§5alsodiscussitsfurtherusagepracticallyandcomparesitwiththeolderalgorithmdescribedin§3.§1什么是半平面交.§2凸多边形交预备知识.§3简要介绍旧D&C算法.§4揭开我的新算法S&I神秘面纱.§5总结和实际运用.Timestamps:CameupwithitinApril2005;implementedpartlyinJune20051;problemsetinJuly20052;publicizedasapostinUSENET,November6,20053.1.IntroductionAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by≤crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.Noticethatax+by≤cand-ax-by≤-cshowoppositeh-planesunlikeax+by=cand-ax-by=-c.Half-PlaneIntersection(abbr.HPI)considersthefollowingproblem:众所周知，直线常用ax+by=c表示，类似地半平面以ax+by≤(≥)c为定义。Givennhalf-planes,aix+biy≤ci(1≤i≤n),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.给定n个形如aix+biy≤ci的半平面，找到所有满足它们的点所组成的点集As오류!연결이잘못되었습니다.describes,thefeasibleregion,whichistheintersection,formsashapeofconvexhullbutpossiblyunbounded.However,weshalladdfourh-planesformingarectangle,whichislargeenoughtomakesuretheareaafterintersectionsfinite.Inthefollowingsections,wesupposethefeasibleregionisboundedwithafinitearea.1Thesub-problemofHPIappearedinUSAInvitationalComputingOlympiadcontest.2SetanHPIprobleminPekingUniversityOnlineJudge,withbriefintroductionaboutthealgorithm.3URL:合并后区域形如凸多边形，可能无界。此时增加4个半平面保证面积有限Eachh-planebuildsupatmostonesideoftheconvexpolygon,hence,theconvexregionwillbeboundedbyatmostnedges.Payattentiontheintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.每个半平面最多形成相交区域的一条边，因此相交区域不超过n条边。注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。2.ConvexPolygonIntersection(abbr.CPI)IntersectingtwoconvexpolygonsAandBintoasingleone,canbeproperlysolvedviaLineSegmentIntersectioninO(nlogn)time,whenthereareO(n)edges.Wewillsketchoutaneasierandmoreefficientway,namedplanesweepmethod.求两个凸多边形A和B的交（一个新凸多边形）。我们描绘一个平面扫描法。Themainideaistocalculateintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Thesegmentsofinneredgesestablishtiestoeachother,andformtheshapeofapolygon,whichistheexpectedpolygonafterintersection.In오류!연결이잘못되었습니다.,inneredgesareindicatedbythicksegments,whichformaboldoutlineoftheintersection.主要思想:以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形。오류!연결이잘못되었습니다.(a)(b)3Supposethereisaverticalsweepline,performingleft-to-rightsweep.Thex-coordinatestobesweptarecalledx-events.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon4:假设有一个垂直的扫描线，从左向右扫描。我们称被扫描线扫描到的x坐标叫做x事件。任何时刻，扫描线和两个多边形最多4个交点totheupperhullofA(namethatintersectionAuforshort)tothelowerhullofA(namethatintersectionAlforshort)totheupperhullofB(namethatintersectionBuforshort)tothelowerhullofB(namethatintersectionBlforshort)Lookat오류!연결이잘못되었습니다.,theloweronebetweenintersectionsAuandBu,andtheupperonebetweenintersectionsAlandBl,formanintervalofthecurrentinnerregion–theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，组成了当前多边形的内部区域。Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates.CalltheedgeswhereAu,Al,BuandBlare:e1,e2,e3ande4respectively.Thenextx-eventshouldbechosenamongfourendpointsofe1,e2,e3ande4,andfourpotentialintersections:e1∩e3,e1∩e4,e2∩e3ande2∩e4.当然，我们不能扫描所有有理数！称Au,Al,Bu,Bl所在的边叫做e1,e2,e3,e4，下一个x事件将在这四条边的端点，以及两两交点中选出。TheaboveoperationcouldbeimplementedwithO(n)runningtime,sincethereareO(n)x-events,andthemaintenanceofAu,Al,BuandBltakesonlyO(1).4Assumethereisnoedgeinpolygonsparalleltothesweepline.Ifsuchsituationhappens,wecouldrotatetheplaneinproperangle,orelse,weneedgoodsensetojudgeagreatmanyspecialcases.BuAuBlAlSweeplinePolygonAPolygonB오류!연결이잘못되었습니다.43.Commonsolution:Divide-and-ConquerAlgorithm(abbr.D&Q)Thebasicapproachissimple,dependsondivide-and-conqueridea.DIVIDE:Partitionthenh-planesintotwosetsofsize2nand2n.CONQUER:Computethefeasibleregion(intersection)recursivelyofbothtwosub-sets.COMBINE:Computetheintersectionoftwoconvexpolygons,bylinearCPIalgorithmdescribedin§2.分:将n个半平面分成两个n/2的集合.治:对两子集合递归求解半平面交.合:将前一步算出来的两个交(凸多边形)利用第2章的CPI求解.Thetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation:总时间复杂度可以用递归分析法.2()2()()()(log)nTnTOnTnOnn4.MyNewSolution:Sort-and-IncrementalAlgorithm(abbr.S&I)Definitionofh-plane’spolarangle:fortheh-planelikex-y≥constant,wedefineitspolarangleto¼π.fortheh-planelikex+y≤constant,wedefineitspolarangleto¾π.fortheh-planelikex+y≥constant,wedefineitspolarangleto-¼π.fortheh-planelikex-y≤constant,wedefineitspolarangleto-¾π.半平面的极角定义:比如x-常数的半平面，定义它的极角为¼π.¼π-⅔π오류!연결이잘못되었습니다.5Definitionofh-plane’sconstant:fortheh-planelikeax+by≤c,wesayitsconstantisc.MynewSort-and-IncrementalAlgorithmseemslengthysinceIamgoingtointroduceitindetails:Step1:将半平面分成