半平面交的新算法及其实用价值第1页共11页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共11页Keywords: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的半平面，找到所有满足它们的点所组成的点集AsError:Referencesourcenotfounddescribes,thefeasibleregion,whichistheintersection,formsashapeofconvexhullbutpossiblyunbounded.However,weshalladdfourh-planesformingarectangle,whichislargeenoughtomakesuretheareaafterintersectionsfinite.Inthefollowingsections,wesupposethefeasibleregionisboundedwithafinitearea.1Thesub-problemofHPIappearedinUSAInvitationalComputingOlympiadcontest.2SetanHPIprobleminPekingUniversityOnlineJudge,withbriefintroductionaboutthealgorithm.3URL:http://groups.google.com/group/sci.math/msg/68e9d9fc634f0d92第2页共11页第1页共11页오오!오오오오오오오오오오.(a)(b)编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共11页合并后区域形如凸多边形，可能无界。此时增加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.InError:Referencesourcenotfound,inneredgesareindicatedbythicksegments,whichformaboldoutlineoftheintersection.主要思想:以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形。第3页共11页第2页共11页BuAuBlAlSweeplinePolygonAPolygonB오오!오오오...
