2020-2021:teams:running_chicken:halfplaneintersection

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:running_chicken:halfplaneintersection [2020/05/15 19:53]
chenjiyuan3 创建
+++ 2020-2021:teams:running_chicken:halfplaneintersection [2020/05/15 20:31] (当前版本)
chenjiyuan3
@@ 行 39: / 行 39: @@
 <code>
-bool BothSide(Point p , Line a){
+bool Bothside(Point p , Line a){
     return a.v * (p - a.p) > eps;
 }
@@ 行 70: / 行 70: @@
 在朴素的做法中，我们对于最终的半平面交是一个凸包的这个性质并没有使用。如果我们有效的利用这个性质，将能得到时间复杂度更低的做法。
-首先我们按照半平面的分界线的方向角度$angle$排序，我们尝试去维护一个下凸壳（这个下凸壳包围的区域就是目前得到的半平面）。
+首先我们按照半平面的分界线的方向角度$angle$排序，对于方向角相同的半平面，我们留那个半平面面积更小的直线（即所留的直线在另外一条直线的内部）。
+我们尝试去维护一个下凸壳（这个下凸壳包围的区域就是目前得到的半平面）。
+对于一个新加的半平面（对应直线$L_i$），我们尝试将目前下凸壳的点$P_{tail}$(下凸壳的点是相邻两组成直线的交点)和直线$L_i$进行比较，$P_{tail}$如果不在$L_i$一侧，就说明该交点和下凸壳最后一条直线已经没有任何的意义（这条线严格在最终交平面外面），将这条线删除，并继续和前一交点$P_{tail-1}$比较，直到得到下凸壳中无点或者点严格在$L_i$一侧。同时在下凸壳靠前的点，我们也通过$L_i$往后筛，如果点$P_{head}$不符合要求（和前面一样），删除并继续比较，直到下凸壳中无点或者点严格在$L_i$一侧。
+在过程中要同时维护下凸壳的点集合$P$和边集合$Q$。
+最后再用下凸壳中的第一条边，从后往前删除不符合要求的点。
+最终$P$和$Q$即为所求
+该方法时间复杂度为$O(nlogn)$
+代码
 <code>
-d
+void HalfPlaneIntersect(Line *L){
-d
+    int head = 0 , tail = 0;
+    Q[head] = L[1];
+    for(int i = 2 ; i <= n ; ++ i){
+	if(fabs(L[i].angle - L[i - 1].angle) < eps) continue; //两条直线平行
+	while(head < tail && !Bothside(P[tail - 1] , L[i]))
+	    tail --;
+	while(head < tail && !Bothside(P[head] , L[i]))
+	    head ++;
+	Q[++ tail] = L[i];
+	if(head < tail)
+	    P[tail - 1] = Linewithline(Q[tail] , Q[tail - 1]);
+    }
+    while(head < tail && !Bothside(P[tail - 1] , Q[head]))
+        tail --;
+    P[tail] = Linewithline(Q[tail] , Q[head]);
+}
 </code>
+**3.应用**
+**4.未来扩展**
+可以研究如何利用set进行动态半平面交。

2020-2021/teams/running_chicken/halfplaneintersection.1589543581.txt.gz · 最后更改: 2020/05/15 19:53 由 chenjiyuan3