资源描述：
《半平面求交算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、•Step1:Separatetheh-planesintotwosets.Onehaspolaranglesof(-½π,½π],theotherhasthoseof(-π,-½π]∪(½π,π].•将半平面分成两部分，一部分极角范围(-½π,½π]，另一部分范围(-π,-½π]∪(½π,π]•Step2:Considerthesetofh-planesin(-½π,½π](theothersetshouldalsogothroughstep3and4similarly).Sortthembythepolarangle.Fortheh-planeswiththes
2、amepolarangle,wecankeeponlyonedown(deleteallothers)accordingtotheconstantoftheseh-planes•考虑(-½π,½π]的半平面(另一个集合类似地做Step3/4)，将他们极角排序。对极角相同的半平面，根据常数项保留其中之一。•Step3.1:Startingfromtwoh-planeswiththeleastpolarangle,computetheirintersection.Pushthemtwointoastack.•从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈
3、。•Step3.2:Eachtime,addonemoreh-planebyincreasingorderofpolarangles,andcalculatetheintersectionofitandthetoph-planeinstack.•每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。7•Step3.3:Ifthisintersectionistotherightoftheintersectionoftoptwoh-planesinstack,wepopthestackonce.•如果当前的交点在栈顶两个半平面交点的右边，出栈（pop）。u
4、pperhull上壳lowerhull下壳•Step4.1:Intersectionsofadjacenth-planepairsinstackformhalfaconvexpolygon.Forthetwosets,wehavetwohalves–(-½π,½π]givesanupperhulland(-π,-½π]∪(½π,π]givesalowerhull.•相邻半平面的交点组成半个凸多边形。我们有两个点集，(-½π,½π]给出上半个，(-π,-½π]∪(½π,π]给出下半个p4p3p1p2upperhull上壳lowerhull下壳•Step4.2:Atth
5、ebeginning,fourpointersp1,p2,p3andp4indicateleftmost/rightmostedgesofbothupperandlowerhulls.•p1andp3moverightwards,whilep2andp4walksleftwards.•初始时候，四个指针p1,p2,p3andp4指向上/下凸壳的最左最右边•p1,p3向右走，p2,p4向左走p3p4p1p2•Step4.3:Atanytime,iftheleftmostintersectionisagainstthefeasibleregionprovidedbyp1
6、orp3,wearesuretheleftmostoneistoberemoved.•Naturally,p1orp3walksrightwardstoitsadjacentedge.7•任意时刻，如果最左边的交点不满足p1/p3所在半平面的限制，我们相信这个交点需要删除•p1或p3走向它右边的相邻边p3p2p1p4p3p4p2p1•Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4.•类似地我们处理最右边的交点p3p4p2p1•Step4.4:Dotheaboveremovingrepeat
7、edlyuntilthereisnomoreupdate.•重复运作直到不再有更新出现——迭代•Everythingexceptsorting(Step2)inS&Ialgorithmremainlinear–O(n)runningtime.Usuallyweusequick-sort.ThetotalcomplexityisO(nlogn),withfairlysmallconstantfactorhidden.•除了Step2中的排序以外，S&I算法的每一步都是线性的。通常我们用快速排序实现Step2，总的时间复杂度为O(nlogn)，隐蔽其中的常数因子很小
