注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【算法】【半平面交】  

2014-04-22 19:35:52|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    0.0...一直不会半平面交...
    所以就得学会额...
    首先什么是半平面就不用讲了把0.0...
    然后最简单的想法自然就是 求出O(n^2)个交点,然后对每一个交点判断所有半平面是否包含它,如果有一个不包含则删除这个点,然后最后剩下的点组成的多边形肯定就是半平面交,复杂度O(n^3)。
    
    然后第二个想法就是...优化这个...也就是剪枝,咱们考虑逐一加入半平面然后维护这个半平面交。一开始构造一个正方形的大半平面,然后咱们每次插入一个半平面,可以扫描当前的所有点,将在外面的点删除掉,然后插入这个半平面的时候计算出其与已经存在的半平面的交点,插入进去。这个是O(n)每一次【最多n个节点扫描,最多n个半平面供扫描】,然后插入n次就是O(n^2)的。【插入具体来说,考虑半平面的每一条边的两个点,如果两个都在外部,则把这个半平面删掉,然后一个在外部一个在内部,则求出交点,把外部的那个点替换成交点,然后这个半平面的一端为交点,然后这样就是O(n)的了】

    但是现在流行的都应该是O(nlogn)的算法了吧... 戳><

    先来复制一下算法过程【附一些这么做的原因的说明】:

    1)对所有的半平面极角排序。如果极角相同的,两个中选择一个在另一个内部的。【这个可以用叉积叉出来,用其中一个半平面和另一个半平面的一个端点来叉积,这里设是左边把,那么如果>0的话显然选择另一个半平面,否则选择这个。
    2)使用一个双端队列,加入一开始的两个半平面。它们的交点也可以求出来。
    3)按顺序枚举半平面,咱们来维护前i个半平面的半平面交。

    首先咱们枚举第i个半平面的时候,已经球出了前i-1个半平面的半平面交了,咱们来看看此时的半平面交的性质。此时的半平面交的表示实际上就是将某个点拆成两个,将这个半平面交变成一条链【就是那个双端队列】【对于一开始两个半平面的无穷区域可以理解成交点在无穷远处的封闭多边形】然后咱们可以发现,每一次插入,要删去的半平面,必然是在链头部和链尾部一端,【这个性质的关键在于咱们是极角排序的,假设在中间出现了一部分需要删除的,那么中间那部分必然比这个半平面更加凸【怎么形容额..】,所以其中的任意一个的左边必然有这个半平面,也就是这个半平面应该排到它们的前面!这就矛盾了】,所以咱们只需要检验双端队列的顶部的半平面和底部的即可,

   即插入一个新的半平面,while 顶部两个半平面的交点在这个半平面的外部,则删去顶部的一个半平面。
                                      while 底部两个半平面的交点在这个半平面的外部,则删除底部的一个半平面。
                                      把当前的半平面插入到队头。
    4)注意到上面实际上有一个bug...那就是假设某一个半平面在很远处包含了所有的,它就会被插入,但是它又因为太远了应该被删除,注意到咱们实际上只关心了链状态,咱们在枚举完所有的把这个链合起来。即这样:
    while 顶部的两个半平面的交点在底部半平面的外部,删除顶部的一个半平面。
    while 底部的两个半平面的交点在顶部半平面的外部,删除底部的一个半平面。
   5)计算出顶部和底部的交点即可。
   关于交点在平面外,叉积即可。

   然后算法描述完了,按照白书的打一遍应该就可以了额...

   
  评论这张
 
阅读(17)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017