计算几何学习笔记 II

发表于 更新于

计算几何学习笔记第二弹，主要包括算法部分

目前包含二维凸包(Todo)、旋转卡壳(Todo)、半平面交……

尚未完成 QwQ

凸包

然而并不是三维的

TODO

旋转卡壳

TODO

半平面交

模板：luogu P4196

半平面

一条直线将平面分成两个平面，称为半平面

可以使用直线表示半平面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct HalfPlane
{
    Point p;
    Vector v;
    double ang;
    HalfPlane() {};
    HalfPlane(Point _p, Vector _v) : p(_p), v(_v)
    {
        ang = atan2(v.y, v.x);
    }
    bool operator< (const HalfPlane &l) const
    {
        return ang < l.ang;
    }
};

与直线的表示不同，在半平面的表示中，需要使用点和方向表示直线（即Point p和Vector v，使用向量表示方向），并单独储存与水平面的夹角（用于排序）

这样表示之后，进行叉乘的运算时就可以直接使用Vector v运算，不用再做减法了

求半平面交

将直线按斜率排序，依次入队

观察发现，每加入一条直线时，可能影响到队首也可能影响到队尾，所以需要使用双端队列维护

考虑每次插入直线的过程：

  1. 当前交点在新加入直线的右侧，覆盖队首
  2. 队首交点在新加入直线右侧，覆盖队尾
  3. 当存在平行直线时，只保留最左侧的向量

Code: TODO

最小圆覆盖

link

可以用模拟退火过 QwQ

正解需要使用随机增量法 怎么还是随机

暂时还没学会 QwQ