算法合集之《半平面交的新算法及其实用价值》课件

Allgreatideasarecontroversial,orhavebeenatonetime.伟大的理论都是有争议的，或者至少曾经是有争议的。

GilbertSeldes(1893-1970)U.S.theater,film,andradiocritic.理论的争议12/19/20221ZeyuanZhuAllgreatideasarecontroversAwisemanwillmakemoreopportunitiesthanhefinds.聪明人总是制造更多的机会，而不是去等待寻找。FrancisBacon(1561-1626)Englishphilosopher,statesman,andlawyer.制造机会12/19/20222ZeyuanZhuAwisemanwillmakemoreoppoAftertheleaveshavefallen,wereturntoaplainsenseofthings.Itisasifwehadcometoanendoftheimagination.叶落时分，我们回到一切的本来面目，这样就与创造与幻想的终点不远了。WallaceStevens(1879-1955)U.S.poet忘记过去，揭开本来面目12/19/20223ZeyuanZhuAftertheleaveshavefallen,Hello,LadiesandGentlemen.

女士们先生们大家好

Bonjour,MesdamesetMessieurs.

Witajcie,PanieiPanowie.

Hallo,DamenundHerren.

Bunaziua,DoamenelorsiDomnilor.

Ciao,signoreesignori.ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱泽园,高三,南京市外国语学校,江苏,中国12/19/20224ZeyuanZhuHello,LadiesandGentlemen.

NewalgorithmforHalf-planeIntersectionanditsPracticalValue

––ThesisforChineseTeamSelectingContest2006

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

––中国代表队2006年选拔赛论文ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱泽园,高三,南京市外国语学校,江苏,中国12/19/20225ZeyuanZhuNewalgorithmforHalf-planeIProjectOverview–全文总揽Aim:PresentanewO(nlogn)algorithmforhalf-planeintersection(abbr.HPI),whichisoneofthemostheatedlydiscussedproblemsincomputerscience;emphasizeitsadvantagesinpracticalapplication,andtosomeextent,reducethecomplexitytoO(n).However,thenewalgorithmwillbeextraordinarilyeasytobeimplemented.主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.12/19/20226ZeyuanZhuProjectOverview–全文总揽Aim:PrProjectOverview–全文总揽§1introduceswhatHalf-PlaneIntersection(HPI)is.什么是半平面交.§2preparesaconvexpolygonintersection(CPI).凸多边形交预备知识.§3brieflydiscussacommonsolutionforHPI–D&C.简要介绍旧D&C算法.§4mynewalgorithmS&Iemergesdetailedly.揭开我的新算法S&I神秘面纱.§5conclusionanddiscussiononfurtherpracticaluse.总结和实际运用.12/19/20227ZeyuanZhuProjectOverview–全文总揽§1intr1. StatementoftheProblem-问题概述12/19/20228ZeyuanZhu1. StatementoftheProblem-1.StatementoftheProblemAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by()crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.3x-2y=1x+2y1众所周知，直线常用ax+by=c表示，类似地半平面以ax+by()c为定义。12/19/20229ZeyuanZhu1.StatementoftheProblemA1.StatementoftheProblemGivennhalf-planes,aix+biyci(1in),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.给定n个形如aix+biyci的半平面，找到所有满足它们的点所组成的点集12/19/202210ZeyuanZhu1.StatementoftheProblemGi1.StatementoftheProblemFeasibleregionformsashapeofconvexhullpossiblyunbounded.

Addfourh-planesformingarectangle,tomaketheintersectionareafinite.合并后区域形如凸多边形，可能无界

此时增加4个半平面保证面积有限12/19/202211ZeyuanZhu1.StatementoftheProblemFe1.StatementoftheProblemEachh-planebuildsupatmostonesideoftheconvexpolygon.Hence,Theconvexregionwillbeboundedbyatmostnedges.每个半平面最多形成相交区域的一条边，因此相交区域不超过n条边。6h-planes

pentagon9h-planes

pentagon12/19/202212ZeyuanZhu1.StatementoftheProblemEa1.StatementoftheProblemPayattentionthatintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。linerayline-segmentpointemptyset12/19/202213ZeyuanZhu1.StatementoftheProblemPa2. ConvexPolygonIntersection–CPI

凸多边形交预备知识12/19/202214ZeyuanZhu2. ConvexPolygonIntersection2.ConvexPolygonIntersectionIntersectingtwoconvexpolygonsAandBintoasingleone.Wewillsketchoutanefficientway,namedplanesweepmethod.求两个凸多边形A和B的交（一个新凸多边形）。我们描绘一个平面扫描法。PolygonAPolygonB12/19/202215ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionMainidea:Regardintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Segmentsofinneredgesestablishtiestoeachother,andformapolygon.(inbold)主要思想:以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形（图中粗线条）PolygonAPolygonB12/19/202216ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionSupposethereisaverticalsweepline,performingleft-to-rightsweep.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon.假设有一个垂直的扫描线，从左向右扫描任何时刻，扫描线和两个多边形最多4个交点PolygonAPolygonBBuAuBlAlSweepline12/19/202217ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectiontheloweronebetweenAuandBu,andtheupperonebetweenAlandBl,formanintervalofthecurrentinnerregion–theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，组成了当前多边形的内部区域PolygonAPolygonBBuAuBlAlSweepline12/19/202218ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionLetuscallthex-coordinatestobesweptx-events.Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates!我们称被扫描线扫描到的x坐标叫做x事件。当然，我们不能扫描所有有理数！BuAuBlAl12/19/202219ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionCalltheedgeswhereAu,Al,BuandBlare:e1,e2,e3ande4respectively.Nextx-eventshouldbechosenamongfourendpointsofe1,e2,e3ande4,andfourpotentialintersections:e1∩e3,e1∩e4,e2∩e3ande2∩e4.称Au,Al,Bu,Bl所在的边叫做e1,e2,e3,e4下一个x事件将在这四条边的端点，以及两两交点中选出BuAuBlAlO(n)12/19/202220ZeyuanZhu2.ConvexPolygonIntersection3. Commonsolution:

Divide-and-ConquerAlgorithm–D&C

通常的分治解法12/19/202221ZeyuanZhu3. Commonsolution:

Divide-and3.Divide-and-ConquerAlgorithmDivide:Partitionthenh-planesintotwosetsofsizen/2.Conquer:Computefeasibleregionrecursivelyofbothtwosubsets.Combine:Computeintersectionoftwoconvexregion,byCPI§2分:将n个半平面分成两个n/2的集合.治:对两子集合递归求解半平面交.合:将前一步算出来的两个交(凸多边形)利用第2章的CPI求解.12/19/202222ZeyuanZhu3.Divide-and-ConquerAlgorit3.Divide-and-ConquerAlgorithmThetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation.总时间复杂度可以用递归分析法.CPI12/19/202223ZeyuanZhu3.Divide-and-ConquerAlgorit4. MyNewSolution:

Sort-and-IncrementalAlgorithm–S&I

我自创的排序增量算法12/19/202224ZeyuanZhu4. MyNewSolution:

Sort-and-4.Sort-and-IncrementalAlgorithmDefinitionofh-plane’spolarangle:

forh-planelikex-yconstant,wedefineitspolarangleto¼π.半平面的极角定义:比如x-y常数的半平面，定义它的极角为¼π.¼π-⅔π12/19/202225ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep1:Separatetheh-planesintotwosets.Onehaspolaranglesof(-½π,½π],theotherhasthoseof(-π,-½π]∪(½π,π].Step1:将半平面分成两部分，一部分极角范围(-½π,½π]，另一部分范围(-π,-½π]∪(½π,π]12/19/202226ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm考虑(-½π,½π]的半平面(另一个集合类似地做Step3/4)，将他们极角排序。对极角相同的半平面，根据常数项保留其中之一。Step2:Considerthesetofh-planesin(-½π,½π](theothersetshouldalsogothroughstep3and4similarly).Sortthembythepolarangle.Fortheh-planeswiththesamepolarangle,wecankeeponlyonedown(deleteallothers)accordingtotheconstantoftheseh-planes12/19/202227ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。Step3:Startingfromtwoh-planeswiththeleastpolarangle,computetheirintersection.Pushthemtwointoastack.12/19/202228ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。Step3:Eachtime,addonemoreh-planebyincreasingorderofpolarangles,andcalculatetheintersectionofitandthetoph-planeinstack.12/19/202229ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm如果当前的交点在栈顶两个半平面交点的右边，出栈（pop）。Step3:Ifthisintersectionistotherightoftheintersectionoftoptwoh-planesinstack,wepopthestackonce.12/19/202230ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep3:12/19/202231ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm前问我们说到出栈，出栈只需要一次么？Nie!我们要继续交点检查，如果还在右边我们要继续出栈，直到当前交点在栈顶交点的左边。Step3:…wepopthestackonce.Once?Isitenough?Nie!Dothisrepeatedlyuntilitistotheleftofthetopintersection.12/19/202232ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相邻半平面的交点组成半个凸多边形。我们有两个点集，(-½π,½π]给出上半个，(-π,-½π]∪(½π,π]给出下半个Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-½π,½π]givesanupperhulland

(-π,-½π]∪(½π,π]givesalowerhull.12/19/202233ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相邻半平面的交点组成半个凸多边形。我们有两个点集，(-½π,½π]给出上半个，(-π,-½π]∪(½π,π]给出下半个Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-½π,½π]givesanupperhulland

(-π,-½π]∪(½π,π]givesalowerhull.upperhull上壳lowerhull下壳12/19/202234ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm初始时候，四个指针p1,p2,p3andp4指向上/下凸壳的最左最右边p1,p3向右走，p2,p4向左走Step4:Atthebeginning,fourpointersp1,p2,p3andp4indicateleftmost/rightmostedgesofbothupperandlowerhulls.p1andp3moverightwards,whilep2andp4walksleftwards.p3p4p1p2upperhull上壳lowerhull下壳12/19/202235ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm任意时刻，如果最左边的交点不满足p1/p3所在半平面的限制，我们相信这个交点需要删除p1或p3走向它右边的相邻边Step4:Atanytime,iftheleftmostintersectionisagainstthefeasibleregionprovidedbyp1orp3,wearesuretheleftmostoneistoberemoved.Naturally,p1orp3walksrightwardstoitsadjacentedge.p3p4p1p212/19/202236ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm类似地我们处理最右边的交点Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p2p1p412/19/202237ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm类似地我们处理最右边的交点Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p4p2p112/19/202238ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm重复运作直到不再有更新出现——迭代Step4:Dotheaboveremovingrepeatedlyuntilthereisnomoreupdate.p3p4p2p112/19/202239ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmEverythingexceptsorting(Step2)inS&Ialgorithmremainlinear–O(n)runningtime.Usuallyweusequick-sort.ThetotalcomplexityisO(nlogn),withfairlysmallconstantfactorhidden.除了Step2中的排序以外，S&I算法的每一步都是线性的。通常我们用快速排序实现Step2，总的时间复杂度为O(nlogn)，隐蔽其中的常数因子很小12/19/202240ZeyuanZhu4.Sort-and-IncrementalAlgori5. ConclusionandPracticalUse

总结和实际应用12/19/202241ZeyuanZhu5. ConclusionandPracticalU5.ConclusionandPracticalUseGreatideasneedlandinggearaswellaswings.S&IalgorithmseemstoworkinthesametimecomplexityasD&Calgorithm,butsomeoverwhelmingadvantagesofimplementingS&Iholds.Greatideasneedlandinggearaswellaswings.S&I算法似乎和D&C算法时间复杂度相同，但是它有着压倒性(overwhelming)的优势。12/19/202242ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseItismucheasiertocodeS&IprogramthanD&Cone.TheprograminC++programminglanguagetakeslessthan3KB.新的S&I算法代码容易编写，相对于D&C大大简单化，C++程序语言实现S&I算法仅需3KB不到.12/19/202243ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseThecoefficienthiddenunderS&Ialgorithm’scomplexityisextraordinarilysmallerthanD&C,sincewenolongerneedO(nlogn)numberofintersectioncalculates.Ingeneralspeaking,S&IprogramrunsapproxfivetimesfasterthanD&Cone.S&I算法复杂度中的系数，远小于D&C，因为我们不再需要O(nlogn)次交点运算.通常意义上来讲，S&I程序比D&C快五倍。12/19/202244ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseIfthegivenh-planesareallin(-½π,½π](oranyspanofπ),S&Iprogramcanbeshortenremarkably(toapproximatelytwentylinesinC++),butD&Cprogrammaynot.AninformaticsproblemappearedinUSAInvitationalComputingOlympiadcontestwithsuchpurpose.如果给定半平面均在(-½π,½π]（或任意一个跨度为π的区间），S&I算法可被显著缩短，C++程序只需要约二十行。USAICO比赛中就出现了这样一题。12/19/202245ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUseThebottleneckofthisalgorithmissorting.PayattentionthesortingisNOTacomparisonsort(sortingbasedoncomparison)!Sincethen,wecanreplacetheO(nlogn)quick-sorttoO(n)radix-sorttodecreasethe

asymptoticaltimecomplexitytoO(n).本算法瓶颈是排序，这里的排序不是比较排序，因此可以将快速排序替换成基数排序，降低程序渐进时间复杂度到线性。AnywayO(n)approachusuallyrunsslowerthannlognonesforitsadditionalmemoryusage!12/19/202246ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUse<美丽心灵>诺贝尔奖得主JohnNash

原创的理论——originalidea创新与信息学竞赛创新与技术我心目中的创新——最重要的是思想创新，其次是行为创新，再其次是文章创新，再再其次才是语言创新思想实践Theprincipalmarkofgeniusisnotperfectionbutoriginality,theopeningofnewfrontiers.AuthurKoestler(1905-1983)Hungarian-bornBritishwriterandjounalist.12/19/202247ZeyuanZhu5.ConclusionandPracticalUs5.ConclusionandPracticalUse创新如高山山，

快马加鞭未下鞍。

惊回首，离天三尺三。山，

倒海翻江卷巨澜。

奔腾急，万马战犹酣。山，

刺破青天锷未残。

天欲堕，赖以拄其间。怅寥廓，问苍茫大地，谁主沉浮。俱往矣，数风流人物，还看今朝。12/19/202248ZeyuanZhu5.ConclusionandPracticalUsAllgreatideasarecontroversial,orhavebeenatonetime.伟大的理论都是有争议的，或者至少曾经是有争议的。

GilbertSeldes(1893-1970)U.S.theater,film,andradiocritic.理论的争议12/19/202249ZeyuanZhuAllgreatideasarecontroversAwisemanwillmakemoreopportunitiesthanhefinds.聪明人总是制造更多的机会，而不是去等待寻找。FrancisBacon(1561-1626)Englishphilosopher,statesman,andlawyer.制造机会12/19/202250ZeyuanZhuAwisemanwillmakemoreoppoAftertheleaveshavefallen,wereturntoaplainsenseofthings.Itisasifwehadcometoanendoftheimagination.叶落时分，我们回到一切的本来面目，这样就与创造与幻想的终点不远了。WallaceStevens(1879-1955)U.S.poet忘记过去，揭开本来面目12/19/202251ZeyuanZhuAftertheleaveshavefallen,Hello,LadiesandGentlemen.

女士们先生们大家好

Bonjour,MesdamesetMessieurs.

Witajcie,PanieiPanowie.

Hallo,DamenundHerren.

Bunaziua,DoamenelorsiDomnilor.

Ciao,signoreesignori.ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱泽园,高三,南京市外国语学校,江苏,中国12/19/202252ZeyuanZhuHello,LadiesandGentlemen.

NewalgorithmforHalf-planeIntersectionanditsPracticalValue

––ThesisforChineseTeamSelectingContest2006

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

––中国代表队2006年选拔赛论文ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.

朱泽园,高三,南京市外国语学校,江苏,中国12/19/202253ZeyuanZhuNewalgorithmforHalf-planeIProjectOverview–全文总揽Aim:PresentanewO(nlogn)algorithmforhalf-planeintersection(abbr.HPI),whichisoneofthemostheatedlydiscussedproblemsincomputerscience;emphasizeitsadvantagesinpracticalapplication,andtosomeextent,reducethecomplexitytoO(n).However,thenewalgorithmwillbeextraordinarilyeasytobeimplemented.主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.12/19/202254ZeyuanZhuProjectOverview–全文总揽Aim:PrProjectOverview–全文总揽§1introduceswhatHalf-PlaneIntersection(HPI)is.什么是半平面交.§2preparesaconvexpolygonintersection(CPI).凸多边形交预备知识.§3brieflydiscussacommonsolutionforHPI–D&C.简要介绍旧D&C算法.§4mynewalgorithmS&Iemergesdetailedly.揭开我的新算法S&I神秘面纱.§5conclusionanddiscussiononfurtherpracticaluse.总结和实际运用.12/19/202255ZeyuanZhuProjectOverview–全文总揽§1intr1. StatementoftheProblem-问题概述12/19/202256ZeyuanZhu1. StatementoftheProblem-1.StatementoftheProblemAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by()crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.3x-2y=1x+2y1众所周知，直线常用ax+by=c表示，类似地半平面以ax+by()c为定义。12/19/202257ZeyuanZhu1.StatementoftheProblemA1.StatementoftheProblemGivennhalf-planes,aix+biyci(1in),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.给定n个形如aix+biyci的半平面，找到所有满足它们的点所组成的点集12/19/202258ZeyuanZhu1.StatementoftheProblemGi1.StatementoftheProblemFeasibleregionformsashapeofconvexhullpossiblyunbounded.

Addfourh-planesformingarectangle,tomaketheintersectionareafinite.合并后区域形如凸多边形，可能无界

此时增加4个半平面保证面积有限12/19/202259ZeyuanZhu1.StatementoftheProblemFe1.StatementoftheProblemEachh-planebuildsupatmostonesideoftheconvexpolygon.Hence,Theconvexregionwillbeboundedbyatmostnedges.每个半平面最多形成相交区域的一条边，因此相交区域不超过n条边。6h-planes

pentagon9h-planes

pentagon12/19/202260ZeyuanZhu1.StatementoftheProblemEa1.StatementoftheProblemPayattentionthatintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。linerayline-segmentpointemptyset12/19/202261ZeyuanZhu1.StatementoftheProblemPa2. ConvexPolygonIntersection–CPI

凸多边形交预备知识12/19/202262ZeyuanZhu2. ConvexPolygonIntersection2.ConvexPolygonIntersectionIntersectingtwoconvexpolygonsAandBintoasingleone.Wewillsketchoutanefficientway,namedplanesweepmethod.求两个凸多边形A和B的交（一个新凸多边形）。我们描绘一个平面扫描法。PolygonAPolygonB12/19/202263ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionMainidea:Regardintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Segmentsofinneredgesestablishtiestoeachother,andformapolygon.(inbold)主要思想:以两凸边形边的交点为分界点，将边分为内、外两种。内边互相连接，成为所求多边形（图中粗线条）PolygonAPolygonB12/19/202264ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionSupposethereisaverticalsweepline,performingleft-to-rightsweep.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon.假设有一个垂直的扫描线，从左向右扫描任何时刻，扫描线和两个多边形最多4个交点PolygonAPolygonBBuAuBlAlSweepline12/19/202265ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectiontheloweronebetweenAuandBu,andtheupperonebetweenAlandBl,formanintervalofthecurrentinnerregion–theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，组成了当前多边形的内部区域PolygonAPolygonBBuAuBlAlSweepline12/19/202266ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionLetuscallthex-coordinatestobesweptx-events.Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates!我们称被扫描线扫描到的x坐标叫做x事件。当然，我们不能扫描所有有理数！BuAuBlAl12/19/202267ZeyuanZhu2.ConvexPolygonIntersection2.ConvexPolygonIntersectionCalltheedgeswhereAu,Al,BuandBlare:e1,e2,e3ande4respectively.Nextx-eventshouldbechosenamongfourendpointsofe1,e2,e3ande4,andfourpotentialintersections:e1∩e3,e1∩e4,e2∩e3ande2∩e4.称Au,Al,Bu,Bl所在的边叫做e1,e2,e3,e4下一个x事件将在这四条边的端点，以及两两交点中选出BuAuBlAlO(n)12/19/202268ZeyuanZhu2.ConvexPolygonIntersection3. Commonsolution:

Divide-and-ConquerAlgorithm–D&C

通常的分治解法12/19/202269ZeyuanZhu3. Commonsolution:

Divide-and3.Divide-and-ConquerAlgorithmDivide:Partitionthenh-planesintotwosetsofsizen/2.Conquer:Computefeasibleregionrecursivelyofbothtwosubsets.Combine:Computeintersectionoftwoconvexregion,byCPI§2分:将n个半平面分成两个n/2的集合.治:对两子集合递归求解半平面交.合:将前一步算出来的两个交(凸多边形)利用第2章的CPI求解.12/19/202270ZeyuanZhu3.Divide-and-ConquerAlgorit3.Divide-and-ConquerAlgorithmThetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation.总时间复杂度可以用递归分析法.CPI12/19/202271ZeyuanZhu3.Divide-and-ConquerAlgorit4. MyNewSolution:

Sort-and-IncrementalAlgorithm–S&I

我自创的排序增量算法12/19/202272ZeyuanZhu4. MyNewSolution:

Sort-and-4.Sort-and-IncrementalAlgorithmDefinitionofh-plane’spolarangle:

forh-planelikex-yconstant,wedefineitspolarangleto¼π.半平面的极角定义:比如x-y常数的半平面，定义它的极角为¼π.¼π-⅔π12/19/202273ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep1:Separatetheh-planesintotwosets.Onehaspolaranglesof(-½π,½π],theotherhasthoseof(-π,-½π]∪(½π,π].Step1:将半平面分成两部分，一部分极角范围(-½π,½π]，另一部分范围(-π,-½π]∪(½π,π]12/19/202274ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm考虑(-½π,½π]的半平面(另一个集合类似地做Step3/4)，将他们极角排序。对极角相同的半平面，根据常数项保留其中之一。Step2:Considerthesetofh-planesin(-½π,½π](theothersetshouldalsogothroughstep3and4similarly).Sortthembythepolarangle.Fortheh-planeswiththesamepolarangle,wecankeeponlyonedown(deleteallothers)accordingtotheconstantoftheseh-planes12/19/202275ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。Step3:Startingfromtwoh-planeswiththeleastpolarangle,computetheirintersection.Pushthemtwointoastack.12/19/202276ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。Step3:Eachtime,addonemoreh-planebyincreasingorderofpolarangles,andcalculatetheintersectionofitandthetoph-planeinstack.12/19/202277ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm如果当前的交点在栈顶两个半平面交点的右边，出栈（pop）。Step3:Ifthisintersectionistotherightoftheintersectionoftoptwoh-planesinstack,wepopthestackonce.12/19/202278ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmStep3:12/19/202279ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm前问我们说到出栈，出栈只需要一次么？Nie!我们要继续交点检查，如果还在右边我们要继续出栈，直到当前交点在栈顶交点的左边。Step3:…wepopthestackonce.Once?Isitenough?Nie!Dothisrepeatedlyuntilitistotheleftofthetopintersection.12/19/202280ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相邻半平面的交点组成半个凸多边形。我们有两个点集，(-½π,½π]给出上半个，(-π,-½π]∪(½π,π]给出下半个Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-½π,½π]givesanupperhulland

(-π,-½π]∪(½π,π]givesalowerhull.12/19/202281ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm相邻半平面的交点组成半个凸多边形。我们有两个点集，(-½π,½π]给出上半个，(-π,-½π]∪(½π,π]给出下半个Step4:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–

(-½π,½π]givesanupperhulland

(-π,-½π]∪(½π,π]givesalowerhull.upperhull上壳lowerhull下壳12/19/202282ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm初始时候，四个指针p1,p2,p3andp4指向上/下凸壳的最左最右边p1,p3向右走，p2,p4向左走Step4:Atthebeginning,fourpointersp1,p2,p3andp4indicateleftmost/rightmostedgesofbothupperandlowerhulls.p1andp3moverightwards,whilep2andp4walksleftwards.p3p4p1p2upperhull上壳lowerhull下壳12/19/202283ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm任意时刻，如果最左边的交点不满足p1/p3所在半平面的限制，我们相信这个交点需要删除p1或p3走向它右边的相邻边Step4:Atanytime,iftheleftmostintersectionisagainstthefeasibleregionprovidedbyp1orp3,wearesuretheleftmostoneistoberemoved.Naturally,p1orp3walksrightwardstoitsadjacentedge.p3p4p1p212/19/202284ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm类似地我们处理最右边的交点Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p2p1p412/19/202285ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm类似地我们处理最右边的交点Step4:Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.p3p4p2p112/19/202286ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithm重复运作直到不再有更新出现——迭代Step4:Dotheaboveremovingrepeatedlyuntilthereisnomoreupdate.p3p4p2p112/19/202287ZeyuanZhu4.Sort-and-IncrementalAlgori4.Sort-and-IncrementalAlgorithmEverythingexceptsorting(Step2)inS&Ialgorithmremainlinear–O(n)runningtime.Usuallyweusequick-sort.ThetotalcomplexityisO(nlogn),withfairlysmallconstantfactorhidden.除了Step2中的