2020-2021:teams:running_chicken:halfplaneintersection
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:halfplaneintersection [2020/05/15 20:27] chenjiyuan3 [2.算法介绍] |
2020-2021:teams:running_chicken:halfplaneintersection [2020/05/15 20:31] (当前版本) chenjiyuan3 |
||
|---|---|---|---|
| 行 39: | 行 39: | ||
| <code> | <code> | ||
| - | bool BothSide(Point p , Line a){ | + | bool Bothside(Point p , Line a){ |
| return a.v * (p - a.p) > eps; | return a.v * (p - a.p) > eps; | ||
| } | } | ||
| 行 74: | 行 74: | ||
| 我们尝试去维护一个下凸壳（这个下凸壳包围的区域就是目前得到的半平面）。 | 我们尝试去维护一个下凸壳（这个下凸壳包围的区域就是目前得到的半平面）。 | ||
| - | 对于一个新加的半平面（对应直线$L_i$），我们尝试将目前下凸壳的点$P_tail$(下凸壳的点是相邻两组成直线的交点)和直线$L_i$进行比较，$P_tail$如果不在$L_i$一侧，就说明该交点和下凸壳最后一条直线已经没有任何的意义（这条线严格在最终交平面外面），将这条线删除，并继续和前一交点$P_{tail-1}$比较，直到得到下凸壳中无点或者点严格在$L_i$一侧。同时在下凸壳靠前的点，我们也通过$L_i$往后筛，如果点$P_head$不符合要求（和前面一样），删除并继续比较，直到下凸壳中无点或者点严格在$L_i$一侧。 | + | 对于一个新加的半平面（对应直线$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$。 | ||
| 行 105: | 行 105: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | **3.应用** | ||
| + | |||
| + | **4.未来扩展** | ||
| + | |||
| + | 可以研究如何利用set进行动态半平面交。 | ||
2020-2021/teams/running_chicken/halfplaneintersection.1589545679.txt.gz · 最后更改: 2020/05/15 20:27 由 chenjiyuan3
