精华内容
下载资源
问答
  • 包含点、线、多边形、凸多边形、圆、半平面交等算法的板子
  • ACM计算几何大全

    2019-03-12 20:04:28
    一、 注意事项 4 二、 一些公式 4 三、二维相关 6 基础: 6 点-点距离 7 点-点对称点 7 点-线对称点 7 点在直线上的投影 7 点到线段的距离(求得最近点) 7 点到直线距离(求得最近点) 7 点到直线距离 7 ...
  • ACM 计算几何模板

    2014-05-09 14:51:37
    ACM 很全的计算几何模板 基础部分 1.几何公式 5 1.1三角形 5 1.2四边形 5 1.3正n边形 5 1.4圆 5 1.5棱柱 6 1.6棱锥 6 1.7棱台 6 1.8圆柱 6 1.9圆锥 6 1.10圆台 7 1.11球 7 1.12球台 7 1.13球扇形 7 2.直线与线段 7 ...
  • ACM计算几何

    2013-05-20 21:35:05
    对学习ACM计算几何有一定的帮助,对于初学计算几何的更好的了解几何
  • ACM计算几何

    万次阅读 多人点赞 2018-08-19 01:24:05
    1.1 计算几何算法 1.2 计算几何题目特点及要领 1.3 预备知识 2 凸包 2.1 定义 2.1.1 凸多边形 2.1.2 凸包 2.2 颜料配色问题 2.2.1 问题描述 2.2.2 问题简化 2.2.3 问题抽象 2.2.4 数学抽象 2.2....

    文章目录

    https://linxi99.gitee.io/20190211/ACM计算几何篇/

    1 前言

    1.1 计算几何算法

    ACM各种算法中计算几何算是比较实际的算法,在很多领域有着重要的用途

    常用算法包括经典的凸包求解,离散化及扫描线算法、旋转卡壳、半平面交等

    1.2 计算几何题目特点及要领

    • 大部分不会很难,少部分题目思路很巧妙

    • 做计算几何题目,模板很重要,模板必须高度可靠

    • 要注意代码的组织,因为计算几何的题目很容易上两百行代码,里面大部分是模板。如果代码一片混乱,那么会严重影响做题正确率。

    • 注意精度控制

    • 能用整数的地方尽量用整数,要想到扩大数据的方法(扩大一倍,或扩大sqrt2)。因为整数不用考虑浮点误差,而且运算比浮点快

    1.3 预备知识

    见ACM几何基础篇

    https://linxi99.gitee.io/20190211/ACM几何基础篇/

    https://blog.csdn.net/linxilinxilinxi/article/details/81750327

    计算几何将用到大量基础篇中的函数与知识

    2 凸包

    2.1 定义

    2.1.1 凸多边形

    过多边形的任意一边做一条直线,如果其他各个顶点都在这条直线的同侧,则把这个多边形叫做凸多边形

    凸包求解算法的基础便是凸多边形的定义与性质

    2.1.2 凸包

    假设平面上n个点,过某些点作一个多边形,使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候,我们就叫它“凸包”

    形象理解:皮筋包裹钉子群

    凸包

    2.2 颜料配色问题

    2.2.1 问题描述

    假设每种颜料都拥有 ( R , G , B ) (R,G,B) (R,G,B)三种属性,表示该种颜料红色,绿色,与蓝色的化学成分所占的比重

    给你若干种已有的不限量的颜料,问是否能够勾兑出目标颜料 ( R 0 , G 0 , B 0 ) (R_0, G_0, B_0) (R0,G0,B0)

    2.2.2 问题简化

    若只考虑 ( R , G ) (R, G) (R,G)这两种颜色

    给定 X = ( 10 % , 35 % ) , Y = ( 16 % , 20 % ) X = (10\%, 35\%), Y = (16\%, 20\%) X=(10%,35%),Y=(16%,20%)

    问是否能够配制出 U = ( 12 % , 30 % ) U = (12\%, 30\%) U=(12%,30%)的燃料

    V = ( 13 % , 22 % ) V = (13\%, 22\%) V=(13%,22%)这一种呢

    如果再给你一种 Z = ( 7 % , 15 % ) Z = (7\%, 15\%) Z=(7%,15%)颜料呢

    2.2.3 问题抽象

    将每一种颜料映射为二维欧氏空间中的一个点,我们可以将已经给定的颜料与目的颜料在空间中标定出来

    经过观察与思考,我们可以发现,一个颜料能够被勾兑出来当且仅当该颜料对应的点,位于以给定颜料所构成的凸包之中

    2.2.4 数学抽象

    Given a point set S = { p 1 , ⋯   , p n } ⊆ ε 2 S = \{p_1, \cdots, p_n\} \subseteq \varepsilon ^ 2 S={p1,,pn}ε2

    Let λ = &lt; λ 1 , ⋯ &ThinSpace; , λ n &gt; ∈ R n , λ 1 + λ 2 + ⋯ + λ n = 1 \lambda = &lt;\lambda _ 1, \cdots, \lambda _ n&gt; \in R ^ n, \lambda _ 1 + \lambda _ 2 + \cdots + \lambda _ n = 1 λ=<λ1,,λn>Rn,λ1+λ2++λn=1 and m i n { λ 1 , ⋯ &ThinSpace; , λ n } ≥ 0 min\{\lambda _ 1, \cdots, \lambda _ n\} \ge 0 min{λ1,,λn}0

    The point

    p = [ p 1 , ⋯ &ThinSpace; , p n ] λ = λ 1 p 1 + ⋯ + λ n p n p = [p _ 1, \cdots, p _ n]\lambda = \lambda _ 1 p _ 1 + \cdots + \lambda _ n p _ n p=[p1,,pn]λ=λ1p1++λnpn

    is called a convex combination of S

    2.2.4.1 Convex Combination And Affine Combination

    凸组合:Convex Combination

    两个点的Convex Combination会是这两个点所构成的线段

    仿射组合:Affine Combination

    而两个点的Affine Combination将会确定这两个点所对应的那条直线

    2.2.4.2 区别与联系

    也就是说Convex Combination 是 Affine Combination的一个子集

    原因便是

    m i n { λ 1 , ⋯ &ThinSpace; , λ n } ≥ 0 min\{\lambda _ 1, \cdots, \lambda _ n\} \ge 0 min{λ1,,λn}0

    这个根据生活实际添加的条件

    2.3 构造凸包的初步尝试

    2.3.1 转化思想

    大事化小,小事化了

    2.3.2 极性 Extremity

    称最终对点集所构成的凸包有贡献的点具有极性

    称其为极点 Extreme Point

    通过观察,所谓的这些极点,我们可以找到一条穿过它们的直线,使得点集中的所有点都落在直线的同一侧

    2.3.3 基于极点的凸包构造算法

    类比冒泡排序,我们可以逐个判断每一个给定的点是否位于任何三个点所构成的三角形的内部

    这样我们可以逐个剔除所有的非极点,从而得到所有的极点,即凸包的解

    很容易想到,该算法的时间复杂度 O ( n 4 ) O(n ^ 4) O(n4)

    2.3.4 基于极边的凸包构造算法

    2.3.4.1 极边

    类比极点的定义相应的我们也可以定义极边(Extreme Edge),它们具有类似的性质

    很容易可以发现凸包边界上的边若取逆时针走向,点集中所有的都位于极边的左侧(ToLeftTest)

    2.3.4.2 尝试实现

    枚举所有点所有边,判断其左右位置相对关系,如果所有点都落在该边的某一侧,则该边为极边,其端点为极点

    易得,时间复杂度为 O ( n 3 ) O(n ^ 3) O(n3)

    2.4 更进一步

    2.4.1 减而治之

    类比插入排序

    我们可以考虑根据之前数据已经构成一个凸包,当新点来临之后,我们便可以考虑当前的点是否位于多边形内部 isPointInPolygon()

    若位于内部或边界之上,我们便可以断定该点对凸包没有贡献

    否则,将该点与凸包所构成的两条支撑线(Support-Lines)缝合到已有答案集合之中,并舍弃失去极性的点

    2.4.2 转向形式

    Pattern Of Turns

    利用每个顶点相对于当前试图加入的点的不同的转向形式,获得支撑线以及不被丢弃的所有点

    2.4.3 优点与劣势

    该算法为在线算法,可以动态的添加点,从而改变凸包形式

    但其复杂度虽然达到了 O ( n 2 ) O(n ^ 2) O(n2),但还是不尽如人意

    2.5 求解凸包的高效算法

    2.5.1 Jarvis March的步进算法

    类比选择排序

    2.5.1.1 思路分析

    Lowest-Then-Leftmost

    纵坐标最小然后横坐标最小的点一定是凸包上的点, 我们将其记为 p 0 p _ 0 p0

    p 0 p _ 0 p0 开始,按逆时针的方向,逐个找凸包上的点,每前进一步找到一个点,所以叫作步进法。

    怎么找下一个点呢?利用夹角。假设现在已经找到 { p 0 , p 1 , p 2 } \{p _ 0,p _ 1,p _ 2\} {p0p1p2}

    要找下一个点:剩下的点分别和 p 2 p _ 2 p2 组成向量,设这个向量与向量 p ⃗ 1 p 2 \vec p _ 1 p _ 2 p 1p2的夹角为 β \beta β

    β \beta β 最小时就是所要求的下一个点了

    JM步进法

    2.5.1.2 时间复杂度

    O ( n H ) O(nH) O(nH)。(其中 n 是点的总个数,H 是凸包上的点的个数)

    具有输出敏感性,所花费的时间与输出的凸包的顶点个数有关

    2.5.1.3 注意

    找第二个点 p 1 p _ 1 p1 时,因为已经找到的只有 p 0 p _ 0 p0 一个点,所以向量只能和水平线作夹角 α \alpha α,当 α \alpha α 最小时求得第二个点

    共线情况:如果直线 p 2 p 3 p _ 2 p _ 3 p2p3 上还有一个点 p 4 p _ 4 p4,即三个点共线

    此时由向量 p 2 p 3 ⃗ \vec{p _ 2 p _ 3} p2p3 和向量 p 2 p 4 ⃗ \vec{p _ 2 p _ 4} p2p4 产生的两个 β \beta β 是相同的

    我们应该把 p 3 p _ 3 p3 p 4 p _ 4 p4 都当做凸包上的点

    并且把距离 p 2 p _ 2 p2 最远的那个点作为最后搜索到的点,继续找它的下一个连接点

    2.5.2 Graham Scan

    2.5.2.1 预处理

    Graham扫描的思想和Jarvis步进法类似,也是先找到凸包上的一个点,然后从那个点开始按逆时针方向逐个找凸包上的点,但它不是利用夹角。

    Graham预处理

    把所有点放在二维坐标系中,则纵坐标最小的点一定是凸包上的点,如图中的 p 0 p _ 0 p0

    把所有点的坐标平移一下,使 p 0 p _ 0 p0 作为原点,如上图。

    2.5.2.2 具体步骤

    1. 计算各个点相对于 p 0 p _ 0 p0 的幅角 α \alpha α ,按从小到大的顺序对各个点排序。

    2. α \alpha α 相同时,距离 p 0 p _ 0 p0 比较近的排在前面。例如上图得到的结果为 p 1 p _ 1 p1 p 2 p _ 2 p2 p 3 p _ 3 p3 p 4 p _ 4 p4 p 5 p _ 5 p5 p 6 p _ 6 p6 p 7 p _ 7 p7 p 8 p _ 8 p8

    3. 我们由几何知识可以知道,结果中第一个点 p 1 p _ 1 p1 和最后一个点 p 8 p _ 8 p8 一定是凸包上的点。
      (以上是准备步骤,以下开始求凸包)
      以上,我们已经知道了凸包上的第一个点 p 0 p _ 0 p0 和第二个点 p 1 p _ 1 p1,我们把它们放在栈里面。
      现在从按照极角排好的集合里,把 p 1 p _ 1 p1 后面的那个点拿出来做当前点,即 p 2 p _ 2 p2 。接下来开始找第三个点:

    4. 连接栈顶的点与次栈顶的点,得到直线 l l l 。看当前点是在直线 l l l 的右边还是左边。
      如果在直线的右边就执行步骤5;
      如果在直线上,或者在直线的左边就执行步骤6。

    5. 如果在右边,则栈顶的那个元素不是凸包上的点,把栈顶元素出栈。执行步骤4。

    6. 当前点是凸包上的点,把它压入栈,执行步骤7。

    7. 检查当前的点 p i p _ i pi 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 p i p _ i pi 后面那个点做当前点,返回步骤4。

    最后,栈中的元素就是凸包上的点了。

    以下为用 GrahamScan 动态求解的过程:

    大家可以直观的了解一下

    Graham Scan

    2.5.2.3 时间复杂度

    根据Scan过程的步骤分析,我们可以得到其时间复杂度为 O ( n ) O(n) O(n)

    但由于其预处理排序时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

    故其总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

    2.5.2.4 代码实现

    根据实现难度,对上述步骤做了些许修改

    const int maxn = 1e3 + 5;
    struct Point {
        double x, y;
        Point(double x = 0, double y = 0):x(x),y(y){}
    };
    typedef Point Vector;
    Point lst[maxn];
    int stk[maxn], top;
    Vector operator - (Point A, Point B){
        return Vector(A.x-B.x, A.y-B.y);
    }
    int sgn(double x){
        if(fabs(x) < eps)
            return 0;
        if(x < 0)
            return -1;
        return 1;
    }
    double Cross(Vector v0, Vector v1) {
        return v0.x*v1.y - v1.x*v0.y;
    }
    double Dis(Point p1, Point p2) { //计算 p1p2的 距离
        return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
    }
    bool cmp(Point p1, Point p2) { //极角排序函数 ,角度相同则距离小的在前面
        int tmp = sgn(Cross(p1 - lst[0], p2 - lst[0]));
        if(tmp > 0)
            return true;
        if(tmp == 0 && Dis(lst[0], p1) < Dis(lst[0], p2))
            return true;
        return false;
    }
    //点的编号0 ~ n - 1
    //返回凸包结果stk[0 ~ top - 1]为凸包的编号
    void Graham(int n) {
        int k = 0;
        Point p0;
        p0.x = lst[0].x;
        p0.y = lst[0].y;
        for(int i = 1; i < n; ++i) {
            if( (p0.y > lst[i].y) || ((p0.y == lst[i].y) && (p0.x > lst[i].x)) ) {
                p0.x = lst[i].x;
                p0.y = lst[i].y;
                k = i;
            }
        }
        lst[k] = lst[0];
        lst[0] = p0;
        sort(lst + 1, lst + n, cmp);
        if(n == 1) {
            top = 1;
            stk[0] = 0;
            return ;
        }
        if(n == 2) {
            top = 2;
            stk[0] = 0;
            stk[1] = 1;
            return ;
        }
        stk[0] = 0;
        stk[1] = 1;
        top = 2;
        for(int i = 2; i < n; ++i) {
            while(top > 1 && Cross(lst[stk[top - 1]] - lst[stk[top - 2]], lst[i] - lst[stk[top - 2]]) <= 0)
                --top;
            stk[top] = i;
            ++top;
        }
        return ;
    }
    

    2.5.3 Andrew算法

    2.5.3.1 由来

    Andrew算法是GrahamScan算法的变种

    和原始的GrahamScan算法相比,Andrew更快,且数值稳定性更好

    2.5.3.2 预处理

    基于水平排序

    首先把所有点按照 Leftmost Then Lowest 原则排序,删除重复点后得到序列 p 1 , p 2 ⋯ p _ 1, p _ 2\cdots p1,p2

    然后把 p 1 p _ 1 p1 p 2 p _ 2 p2放到凸包中。

    2.5.3.3 算法步骤

    p 3 p _ 3 p3开始,当新点在凸包的“前进”方向的左边时继续,否则依次删除最近加入凸包的点,直到新点在左边

    重复此过程,直到碰到最右边的 p n p _ n pn,就求出了“下凸包”。然后反过来从 p n p _ n pn开始再做一次,求出“上凸包”,合并起来就是完整的凸包

    2.5.3.4 时间复杂度

    两次扫描均为 O ( n ) O(n) O(n)

    预处理排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

    总时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

    2.5.3.5 代码实现

    struct Point {
        double x, y;
        Point(double x = 0, double y = 0):x(x),y(y){}
    };
    typedef Point Vector;
    Vector operator - (Point A, Point B){
        return Vector(A.x-B.x, A.y-B.y);
    }
    bool operator < (const Point& a, const Point& b){
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    }
    double Cross(Vector v0, Vector v1) {
        return v0.x*v1.y - v1.x*v0.y;
    }
    //计算凸包,输入点数组为 p,个数为 n, 输出点数组为 ch。函数返回凸包顶点数
    //如果不希望凸包的边上有输入点,则把两个 <= 改为 <
    //在精度要求高时建议用dcmp比较
    //输入不能有重复点,函数执行完后输入点的顺序被破坏
    int ConvexHull(Point* p, int n, Point* ch) {
        sort(p, p+n);
        int m = 0;
        for(int i = 0; i < n; ++i) {
            while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) {
                m--;
            }
            ch[m++] = p[i];
        }
        int k = m;
        for(int i = n-2; i>= 0; --i) {
            while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) {
                m--;
            }
            ch[m++] = p[i];
        }
        if(n > 1)
            --m;
        return m;
    }
    

    2.5.4 分治法求解凸包

    2.5.5 Melkman算法

    3 离散化

    3.1 概述

    与其说离散化是一种算法,不如说是一种程序设计中的非常常用的技巧,它可以有效的降低时间复杂度

    离散化不仅在计算几何中经常用到,它几乎和所有算法都能结合成为考点

    3.2 基本思想

    在众多可能的情况中只考虑我需要用的值

    3.3 例题:区域的个数

    3.3.1 题目描述

    w × h w \times h w×h 的的格子画了 n n n条或垂直或水平宽度为1的直线,求出这些格子被划分成了多少个4连块(上、下、左、右连通)。

    区域的个数

    【输入格式】

    第一行包含两个整数:w和h,表示矩形的列数和行数(行列编号都从1开始)。
      第二行包含一个整数n,表示有n条直线。
      接下来的n行,每行包含四个整数:x1,y1,x2,y2,表示一条直线的列号和行号。

    【输出格式】

    一个整数,表示区域数量。

    【输入样例】

    10 10
    5
    1 4 6 4
    1 8 10 8
    4 1 4 10
    9 1 9 5
    10 6 10 10

    【输出样例】

    6

    【数据范围】

    1<=w,h<=1000000 , 1<=n<=500

    3.3.2 思路分析

    准备好 w × h w \times h w×h的数组,并记录是否有直线通过,然后一通 b f s bfs bfs或者 d f s dfs dfs就可以解决战斗

    但这个问题中 w w w h h h最大为1000000,所以没有办法创建 w × h w \times h w×h的数组

    因此我们需要使用坐标离散化这一技巧

    坐标离散化

    如上图所示,将前后没有变化的行列消除后并不会影响区域的个数

    数组里只需要存储有直线的行列以及其前后的行列就足够了,这样的话大小最多 6 n × 6 n 6n \times 6n 6n×6n,因此就可以创建出数组并利用搜索求出区域的个数

    3.3.3 代码实现

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 5e2 + 5;
    int x1[maxn], x2[maxn], y1[maxn], y2[maxn];//开始列号结束列号,开始行号,结束行号
    int w, h, n, ans;//宽,高,以及横线的个数
    bool line[maxn*6][maxn*6];
    int dire[5][3]= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    struct node {
        int x, y;
        node(int x, int y):x(x), y(y) {}
    };
    //对x1和x2进行离散化,并返回离散化之后的宽度
    int compress(int *xx1,int *xx2,int w) { //开始坐标,结束坐标
        vector<int> v;
        for(int i = 0; i < n; ++i) //将横线本身以及附近两横线存储
            for(int d = -1; d <= 1; ++d) {
                int nx1 = xx1[i] + d;
                int nx2 = xx2[i] + d;
                if(nx1 >= 1 && nx1 <= w) v.push_back(nx1);
                if(nx2 >= 1 && nx2 <= w) v.push_back(nx2);
            }
        //去重
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        //unique()函数去重并返回多余元素存储的起始位置
        //erase()函数区间删除左开右闭的区间
        //离散化后的坐标
        for(int i = 0; i < n; ++i) {
            xx1[i] = find(v.begin(), v.end(), xx1[i]) - v.begin();
            xx2[i] = find(v.begin(), v.end(), xx2[i]) - v.begin();
            //通过find()函数将坐标转化为了下标
        }
        return v.size();
    }
    
    void bfs(int xx,int yy) {
        queue<node> q;
        q.push(node{xx, yy});
        line[xx][yy] = 1;
    
        while(!q.empty()) {
            node t=q.front();
            q.pop();
            int x=t.x;
            int y=t.y;
    
            for(int i=0; i<4; i++) {
                int nx=x+dire[i][0];
                int ny=y+dire[i][1];
                if(nx<0||nx>=h||ny<0||ny>=w)continue;
                if(!line[nx][ny]) {
                    line[nx][ny]=1;
                    q.push(node(nx, ny));
                }
            }
        }
        return ;
    }
    int main() {
        while(cin >> w >> h >> n) {
            ans = 0;
            memset(line, false, sizeof(line));
    
            for(int i = 0; i < n; ++i) cin >> x1[i];
            for(int i = 0; i < n; ++i) cin >> x2[i];
            for(int i = 0; i < n; ++i) cin >> y1[i];
            for(int i = 0; i < n; ++i) cin >> y2[i];
    
            w = compress(x1, x2, w);
            h = compress(y1, y2, h);
    
            //标记上所在横线上的点
            for(int i = 0; i < n; ++i) //枚举n条横线
                for(int y = y1[i]; y <= y2[i]; ++y) //枚举行
                    for(int x = x1[i]; x <= x2[i]; ++x) //枚举列
                        line[y][x] = true;
    
            //打印查看离散化后的图形
            /*
            for(int i=0;i<h;i++)
            {
            	for(int j=0;j<w;j++)
            	{
            		if(line[i][j])cout<<1<<" ";
            		else cout<<0<<" ";
             }
             cout<<endl;
            }
            cout<<endl<<ans<<endl;
            */
            //搜索求区域块数 防止爆栈,这里使用广搜
            for(int i = 0; i < h; ++i){
                for(int j = 0; j < w; ++j) {
                    if(!line[i][j]) {
                        ++ans;
                        bfs(i,j);
                    }
                }
            }
            cout<<ans<<endl;
        }
    
        return 0;
    }
    /*
    10 10 5
    1 1 4 9 10
    6 10 4 9 10
    4 8 1 1 6
    4 8 10 5 10
    */
    
    

    4 扫描线法(平面扫描)

    4.1 描述

    在集合问题中,我们经常利用平面扫描技术来降低算法的复杂度

    所谓平面扫描,是指扫描线在平面上按给定轨迹移动的同时,不断根据扫描线扫过部分更新信息,从而得到整体所要求的结果的方法

    扫描的方法,既可以从左向右与 y y y轴平行的直线,也可以固定射线的端点逆时针转动

    4.2 例题:矩形面积并

    4.2.1 题目描述

    给出 n n n个矩形的左下角和右上角的坐标,求矩形面积的并

    转化前

    转化后

    【输入格式】

    第一行包含一个整数:n,表示矩形数量。
      第 2 2 2 n + 1 n + 1 n+1行,每行包含四个浮点数,表示该矩形左下角与右上角的坐标

    【输出格式】

    矩形面积交的大小

    【输入样例】
      2
      10 10 20 20
      5 15 25 25.5
    【输出样例】

    180.00

    【数据范围】

    1 <= n <= 100
    0 <= x1 < x2 <= 100000,0 <= y1 < y2 <= 100000

    4.2.2 思路分析

    首先,矩形比较多,坐标也很大,所以横坐标需要离散化(纵坐标不需要离散化)

    //不离散化直接线段树维护也可以

    考虑一条扫描线,从最下方竖直向上扫描

    扫描前我们需要保存好矩形的上下边,并且按照高度进行排序,

    另外如果该边为矩形的上边则将其标记为-1

    否则将其标记为1

    接着让扫描线从下往上扫描,每遇到一条上下边就停下来,将这条线段投影到总区间上

    这个投影对应的其实就是插入和删除线段的操作

    下边是1,扫描到下边的话相当于往总区间插入一条线段

    上边是-1,扫描到上边的话相当于在总区间删除一条线段

    每次扫描到一条上下边后,就区间求和,得到现在被覆盖的总长度,乘其扫过的高度并将其统计起来

    以此往复,当扫出最高的那条边,我们便获得了所需求得矩形面积交

    4.3 寻找平面线段交点O(nlogn)

    5 半平面交

    5.1 描述

    简单地说,半平面交问题就是给出若干个半平面,求他们的公共部分。

    其中每个半平面都用一条有向线段表示,它的左侧就是它所代表的半平面

    5.2 有向线段

    代码实现

    struct Line{
        Point p;//直线上任意一点
        Vector v;//方向向量,它的左边就是对应的半平面
        double ang;//极角,即从x轴正半轴旋转到向量v所需要的角(弧度)
        Line(){}
        Line(Point p, Vector v) : p(p), v(v){
            ang = atan2(v.y, v.x);
        }
        bool operator < (const Line& L) const {//排序用的比较运算符
            return ang < L.ang;
        }
    };
    

    5.3 半平面交的结果

    在很多情况下,半平面交的结果都是一个凸多边形

    但也有时候会得到一个无界多边形

    甚至是一条直线、线段或者是点

    但不管怎样,结果一定是凸的(凸集的交是凸的)

    当然,半平面交也可以为空

    5.4 计算方法

    5.4.1 增量法

    初始答案为整个平面

    然后逐一的加入各个半平面,维护当前的半平面交

    为了编程方便,我们一般用一个很大的矩形(4个半平面的交)代替“整个平面”

    计算出结果以后再删去这四个人工半平面

    这样,没加入一个平面就相当于用一条有向直线去切割多边形

    5.4.2 切割方法

    按照逆时针顺序考虑多边形所有的顶点

    保留在直线左侧和直线上的点,而删除直线右边的点

    如果有向直线和多边形相交时产生了新的点,这些点应该加在新的多边形中

    5.4.3 时间复杂度

    每次遍历切割的时间复杂度为 O ( n ) O(n) O(n)

    但我们可以通过双端队列优化加扫描的方式将每次切割的成本平摊为 O ( l o g n ) O(logn) O(logn)

    因此半平面交可以在 O ( n l o g n ) O(nlogn) O(nlogn)的时间内解决

    5.4.4 代码实现

    const double eps = 1e-6;
    struct Point{
        double x, y;
        Point(double x = 0, double y = 0):x(x),y(y){}
    };
    typedef Point Vector;
    Vector operator + (Vector A, Vector B){
        return Vector(A.x+B.x, A.y+B.y);
    }
    Vector operator - (Point A, Point B){
        return Vector(A.x-B.x, A.y-B.y);
    }
    Vector operator * (Vector A, double p){
        return Vector(A.x*p, A.y*p);
    }
    int sgn(double x){
        if(fabs(x) < eps)
            return 0;
        if(x < 0)
            return -1;
        return 1;
    }
    double Dot(Vector A, Vector B){
        return A.x*B.x + A.y*B.y;
    }
    double Cross(Vector A, Vector B){
        return A.x*B.y-A.y*B.x;
    }
    double Length(Vector A){
        return sqrt(Dot(A, A));
    }
    Vector Normal(Vector A){//向量A左转90°的单位法向量
        double L = Length(A);
        return Vector(-A.y/L, A.x/L);
    }
    struct Line{
        Point p;//直线上任意一点
        Vector v;//方向向量,它的左边就是对应的半平面
        double ang;//极角,即从x轴正半轴旋转到向量v所需要的角(弧度)
        Line(){}
        Line(Point p, Vector v) : p(p), v(v){
            ang = atan2(v.y, v.x);
        }
        bool operator < (const Line& L) const {//排序用的比较运算符
            return ang < L.ang;
        }
    };
    //点p在有向直线L的左侧
    bool OnLeft(Line L, Point p){
        return Cross(L.v, p - L.p) > 0;
    }
    //两直线交点。假定交点唯一存在
    Point GetIntersection(Line a, Line b){
        Vector u = a.p - b.p;
        double t = Cross(b.v, u)/Cross(a.v, b.v);
        return a.p + a.v*t;
    }
    //半平面交的主过程
    int HalfplaneIntersection(Line* L, int n, Point* poly){
        sort(L, L + n);//按照极角排序
        int fst = 0, lst = 0;//双端队列的第一个元素和最后一个元素
        Point *P = new Point[n];//p[i] 为 q[i]与q[i + 1]的交点
        Line *q = new Line[n];//双端队列
        q[fst = lst = 0] = L[0];//初始化为只有一个半平面L[0]
        for(int i = 1; i < n; ++i){
            while(fst < lst && !OnLeft(L[i], P[lst - 1])) --lst;
            while(fst < lst && !OnLeft(L[i], P[fst])) ++fst;
            q[++lst] = L[i];
            if(sgn(Cross(q[lst].v, q[lst - 1].v)) == 0){
                //两向量平行且同向,取内侧一个
                --lst;
                if(OnLeft(q[lst], L[i].p)) q[lst] = L[i];
            }
            if(fst < lst)
                P[lst - 1] = GetIntersection(q[lst - 1], q[lst]);
        }
        while(fst < lst && !OnLeft(q[fst], P[lst - 1])) --lst;
        //删除无用平面
        if(lst - fst <= 1) return 0;//空集
        P[lst] = GetIntersection(q[lst], q[fst]);//计算首尾两个半平面的交点
        //从deque复制到输出中
        int m = 0;
        for(int i = fst; i <= lst; ++i) poly[m++] = P[i];
        return m;
    }
    

    6 分治法解决平面最近点对(O(nlogn))

    const int maxn = 2e5 + 5;
    const double inf = 1e10;
    
    struct Point {
        double x,y;
        bool operator <(const Point &a)const {
            return x < a.x;
        }
    };
    
    inline double dist(const Point &p1, const Point &p2) {
        return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
    }
    
    Point p[maxn], q[maxn];
    double ClosestPair(int l, int r) {
        if(l == r)
            return inf;
        int mid = (l+r)>>1;
        double tx = p[mid].x;
        int tot = 0;
        double ret = min(ClosestPair(l, mid), ClosestPair(mid + 1, r));
        for(int i = l, j = mid + 1; (i <= mid || j <= r); ++i) {
            while(j <= r && (p[i].y > p[j].y || i > mid)) {
                q[tot++] = p[j];
                j++; //归并按y排序
            }
            if(abs(p[i].x - tx) < ret && i <= mid) { //选择中间符合要求的点
                for(int k = j - 1; k > mid && j - k < 3; --k)
                    ret = min(ret, dist(p[i], p[k]));
                for(int k = j; k <= r && k-j < 2; ++k)
                    ret = min(ret, dist(p[i], p[k]));
            }
            if(i <= mid)
                q[tot++] = p[i];
        }
        for(int i = l, j = 0; i <= r; ++i, ++j)
            p[i] = q[j];
        return ret;
    }
    

    7 旋转卡壳(O(nlogn)解决平面最远点对)

    double Dist2(Point p1, Point p2) { //计算距离的平方
        double ret = Dot(p1 - p2, p1 - p2);
        return ret;
    }
    double RotatingCalipers(Point* ch, int m) {//返回平面最大距离的平方
        if(m == 1) return 0.0;
        if(m == 2) return Dist2(ch[0], ch[1]);
        double ret = 0.0;
        ch[m] = ch[0];
        int j = 2;
        for(int i = 0; i < m; ++i) {
            while(Cross(ch[i + 1] - ch[i], ch[j] - ch[i]) < Cross(ch[i + 1] - ch[i], ch[j + 1] - ch[i]))
                j = (j + 1)%m;
            ret = max(ret, max(Dist2(ch[j], ch[i]), Dist2(ch[j], ch[i + 1])));
        }
        return ret;
    }
    

    8 三点确定外接圆圆心坐标

    struct Point {
        double x,y;
        Point(double x = 0, double y = 0):x(x),y(y){}
    };
    Point Excenter(Point a, Point b, Point c){
        double a1 = b.x - a.x;
        double b1 = b.y - a.y;
        double c1 = (a1*a1 + b1*b1)/2;
        double a2 = c.x - a.x;
        double b2 = c.y - a.y;
        double c2 = (a2*a2 + b2*b2)/2;
        double d = a1*b2 - a2*b1;
        return Point(a.x + (c1*b2 - c2*b1)/d, a.y + (a1*c2 - a2*c1)/d);
    }
    
    展开全文
  • 2014 PKU ACM 计算几何

    2014-08-30 15:31:10
    2014 PKU ACM 计算几何,本资料完整的讲解了计算几何的各个专题,主要是基础知识的讲解和各类算法的思想的讲解,没有具体的代码。
  • ACM计算几何模板

    2012-03-31 19:21:21
    ACM计算几何模板,74页,包括几何公式,几何图形,三维几何等等。
  • ACM 计算几何基础模板

    2021-03-24 21:43:45
    ACM计算几何中,我们常常重复用到许多方法,例如求点距,求直线方程,等等。不妨利用模板总结之。这些模板为我从网上学习后加入自己的理解糅合得来qwq,看了很多的博客,查了很多书籍,其中印象最深的是林夕林夕...

    在ACM计算几何中,我们常常重复用到许多方法,例如求点距,求直线方程,等等。不妨利用模板总结之。这些模板为我从网上学习后加入自己的理解糅合得来qwq,看了很多的博客,查了很多书籍,其中印象最深的是林夕林夕关于计算几何模板的总结,大家也可以去参考他的应该比我的更详细qwq
    (不过大佬最近好像出没比较少了)
    所以我这个主要还是留着自己参考吧,能帮到他人再好不过了

    为了不产生歧义,方便理解,本模板使用笛卡尔坐标系,封装的多是数学中常见的函数。

    前置知识:高中数学,向量外积相关

    模板仅供参考学习,不保证任何情况下不会因为误差WA掉或是RE掉

    基础声明

    首先,打acm的时候double这个数据类型就比较恶心(容易浮动导致误差),而计算几何中各种计算又几乎没法单独用整型解决。因此我们需要一个小常数来判断误差。

    例如,计算啥啥面积的时候,我们需求误差在10的-6次方以内,那么就可以定义这个常数为10的-6次方:

    const double eps = 1e-6;
    

    然后,我们的目标是,当误差小于1e-6时,误差将被忽略不计。也就是说,两个数比较时,差距在1e-6以内,我们就可以认为这两个数相等。

    一般的计算中,本来两个相等的数字,因为我们计算路径的不同,浮点数就可能会发生不同的浮动,导致 = = == ==运算符检查本来应该相等的两个浮点数时返回了0。这时我们就可以用误差来避免了。

    以下为重载大小判断的函数:

    int cmp(const double& a, const double& b)
    {
    	if(fabs(a - b) < eps) return 0; // 若误差范围内相等,返回0
    	else if(a > b) return 1; // 若a > b,返回1
    	return -1;	// 若a < b,返回-1
    }
    

    另外还有计算几何中常用的常量:

    const double pi = 3.1415927536;
    const double INF = 1e100;
    

    浮点数的表数范围巨大,可以表示到10的200多次方,但是实际上几十次方浮动误差就大到难以接受了……因此,我们可以用一个100次方表示无穷大,反正它够大就对了,但是却不能直接拿来做计算(总之就是误差非常大)。

    另外,我们也常用C++内置的反三角函数acos()来求角度。但是这个函数有个问题,我们都知道反余弦函数的定义域是 [ − 1 , 1 ] [-1,1] [1,1],然而由于浮点数的浮动偏移,我们得到的1很可能实际上是1.00001,1.0000001这种数,这些数据不在反余弦函数的定义域内了,那么把它们作为参数传进去就没法计算,就会导致Runtime Error,就没法AC!QAQ!所以我们可以把acos()函数二次包装一下,打消这个顾虑。

    double acs(double x)
    {
    	if(x > 1) x = 1;
    	else if(x < -1) x = -1;
    	return acos(x);
    }
    

    顺便把反正弦函数也包装一下

    double asn(double x)
    {
    	if(x > 1) x = 1;
    	else if(x < -1) x = -1;
    	return asin(x);
    }
    

    当然啦,上面这个函数的调用还得保证理论上传入的x确实在 [ − 1 , 1 ] [-1,1] [1,1]范围内。

    另外还有一个关于double注意事项,即其应该以%lf格式读入,而以%f格式输出。寒假曾因为这个在好几个图论题上wa了,自己也不知道为啥,后来也有很多巨巨强调……

    好,这些就是基本需要注意的地方,下面我们来建立笛卡尔的王国吧~

    直接定义:

    struct point
    {
    	double x, y;
    	point(double xx = 0, double yy = 0){x = xx, y = yy;}
    };
    

    即可。
    然后点与点之间有一系列的计算函数,下面列出我用过的几个:

    double dis(const point& a, const point& b) // 计算两点距离
    {
    	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }
    
    double slope(const point& a, const point& b) // 求两点斜率
    {
    	if(cmp(a.x, b.x) == 0) return INF;
    	return (a.y - b.y) / (a.x - b.x);
    }
    
    double gradient(const point& a, const point& b) // 计算倾斜角
    {
    	if(cmp(a.y, b.y) == 0) return 0;
    	if(cmp(a.x, b.x) == 0) return pi / 2.0;
    	return atan(slope(a, b));
    }
    

    只有点的就到这里,下面的向量是应用更多的~

    向量

    由于空间中的向量也可以用坐标表示,因此我们不妨:

    typedef point Vector;
    

    V大写是因为关键字vector已经被STL用去了。(C无视我)

    在计算几何领域,使用向量不仅操作比传统解析几何方法更简洁易写,而且产生的浮点误差也更小。因此,向量是计算几何的重头戏。

    先看看高中学过的一些东西:
    向量点积,重载一下:

    double operator * (const Vector& a, const Vector& b)
    {
    	return a.x * b.x + a.y * b.y;
    }
    

    接着是几大运算,向量加减,数乘等等等等

    Vector operator + (const Vector& a, const Vector& b) // 向量加法
    {
    	return Vector(a.x + b.x, a.y + b.y);
    }
    
    Vector operator - (const Vector& a, const Vector& b) // 向量减法
    {
    	return Vector(a.x - b.x, a.y - b.y);
    }
    
    Vector operator * (const Vector& a, const double& b) // 向量数乘
    {
    	return Vector(a.x * b, a.y * b);
    }
    
    Vector length(const Vector& x) // 向量模长
    {
    	return sqrt(x * x);
    }
    
    Vector angle(const Vector& a, const Vector& b) // 向量夹角
    {
    	return acs((a * b) / length(a) / length(b));
    }
    

    向量叉乘,返回结果向量的有向长度。用^运算符重载之。
    注意叉乘的绝对值也就是两向量围成的平行四边形的面积。

    double operator ^ (const Vector& a, const Vector& b)
    {
    	return a.x * b.y - a.y * b.x;
    }
    

    对向量进行操作。向量逆时针旋转:

    Vector Rotate(const Vector& a, double rad)
    {
    	return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
    }
    

    接下来,点的排序。在诸如求凸包的一类问题中,我们需要为点进行排序方便操作,这里以Andrew凸包算法中的Left then Low排序为例给一个排序函数:

    bool leftThenLow(const point& a, const point& b)
    {
    	if(cmp(a.x, b.x) == 0) return a.y < b.y;
    	return a.x < b.x;
    }
    

    以及Graham Scan中必不可少的极角排序:

    point p; // 基准点
    bool angleSort(const point& a, const point& b)
    {
    	return (angle(a - p, Vecotr(1, 0)) < angle(b - p, Vector(1, 0)));
    }
    

    直线

    计算几何体系的直线通常使用向量表示法(类似参数方程)而不是一般的 y = k x + b y=kx+b y=kx+b的形式。一般我们这样表示直线: y = v t + p y=vt+p y=vt+p. 其中 v v v是一个向量,而 p p p是某个点。其几何意义为从一定点 p p p出发,经过 t t t v v v所能到达的点的集合。这样的表示方法是因为可以表示无斜率的直线和斜率为0的直线,也能表示线段。有了这个表示法,我们再进行一系列函数封装。

    struct line
    {
    	double v, p;
    	line(double vv = 0, double pp = 0){v = vv, p = pp;}
    };
    

    点线距离:

    double dis(const line& l, const point& x)
    {
    	Vector v = l.p - x;
    	return fabs(v ^ l.v) / length(l.v);
    }
    

    点是否在线上:

    bool pointOnLine(const point& x, const line& l)
    {
    	return cmp((Vector(l.p - x) ^ l.v), 0);
    }
    

    点在直线上的投影:

    point prj(const point& x, const line& l)
    {
    	return l.p + l.v * (l.v * (x - l.p) / (l.v * l.v));
    }
    

    使用标准方法表示:圆心和半径。

    struct circle
    {
    	point p;
    	double r;
    	circle(double x, double y, double rr){p.x = x, p.y = y, r = rr;}
    };
    
    展开全文
  • ACM计算几何---关于点和直线的所有问题的模板 直接可以用#include&lt;bits/stdc++.h&gt; using namespace std; typedef long long ll; const double PI = 3.1415927; const double EPS=1e-10; //double类型...

    ACM计算几何---关于点和直线的所有问题的模板 直接可以用

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const double PI = 3.1415927;
    const double EPS=1e-10;	//double类型等于0统一用是否<0来判断 
    struct Point{
        double x,y;
        Point(){}
        Point(double x,double y):x(x),y(y){} // 构造函数,方便代码编写
        Point(const Point & p):x(p.x),y(p.y){}
        Point operator +(Point p){
            return Point(x+p.x,y+p.y);
        }
        Point operator-(Point p){
            return Point(x-p.x,y-p.y);
        }
        Point operator*(double d){
            return Point(x*d,y*d);
        }
        double operator*(Point p){  // 内积 点乘
            return x*p.x+ y*p.y;
        }
        double operator^(Point p){//  外积 叉乘
            return x*p.y-y*p.x;
        }
        //下面两个friend貌似是实现可以 cin连续输入和cout连续输出的 
        //已验证 的确是为了可以用 cin连续输入 和cout连续输出的 
        //如 cin>>p1>>p2; cout<<p1<<p2;  
        friend ostream& operator<<(ostream& os,const Point& p ){
            os<<p.x<<" "<<p.y<<endl;
            return os;
        }
        friend istream& operator>>(istream& is, Point&p) {// Point 不能是常量,是变量
            is>>p.x>>p.y;
            return is;
        }
        double dist(Point p){//两点距离 p1.dist(p2)用的时候这样用 
            return sqrt( (x-p.x)*(x-p.x)+ (y-p.y)*(y-p.y) );
        }
    };
    Point intersecting(Point p1,Point p2,Point q1,Point q2){ // 计算直线p1p2与q1q2的交点 
        double d1=( (q2-q1)^(q1-p1) );
        double d2=( (q2-q1)^(p2-p1) );
        return p1+ (p2-p1)*(d1/d2) ;
    }
    struct Line{
        Point st , ed ;
        Line(){}
        Line(Point s, Point e){
            st = s ;
            ed = e ;
        }
        bool parallel(Line l){//判断直线是否平行 平行返回1 
            return ((ed - st)^(l.ed - l.st)) == 0 ;
        }
        bool overlap(Line l){//判断直线是否共线 共线返回1 
            return (((ed - st)^(l.ed - st)) == 0 ) && (((ed -st)^(l.ed - st)) == 0) ;
        }
        bool onSegment(Point Q){//判断点是否在线段上  包括端点  在返回1 
    		if((Q.x - st.x) * (ed.y - st.y) == (ed.x - st.x) * (Q.y - st.y)  //叉乘   //保证Q点坐标在st,ed之间   
    		&& min(st.x , ed.x) <= Q.x && Q.x <= max(st.x , ed.x)      
    		&& min(st.y , ed.y) <= Q.y && Q.y <= max(st.y , ed.y))  
            return true;  
    		else  
            return false;
    	}
    	bool perpendicular(Line l){//判断两条直线是否垂直 垂直返回1  也可以把两条直线换成四个点 
    		return ((ed-st)*(l.ed-l.st)==0);
    	}
        Point intersectionode(Line l){//输出两直线的交点 返回 Point类型 
            double t = (l.ed - l.st)^(l.st - st) ;
            double t1 = (l.ed - l.st)^(ed - st) ;
            return st + (ed - st) * (t / t1) ;
        }
        void read(){//读入一条直线  如l1.read(); 需要输入四个点 即一条直线 
            scanf("%lf%lf%lf%lf" , &st.x, &st.y ,&ed.x ,&ed.y);
        }
    };
    double Norm(Point p) // 计算矢量p的模   
    {   
        return sqrt(p.x * p.x + p.y * p.y);   
    }
    double disptoline(Point p,Line l){//输出点到直线的最短距离 
        return fabs( ((p-l.st)^(p-l.ed)) / l.st.dist(l.ed));  
    }  
    
    Point ptoline(Line l,Point p){ //输出点到直线上的最近点  
    		Line l1; 
        	l1.st=l1.ed=p; 
       		l1.ed.x+=l.st.y-l.ed.y,l1.ed.y+=l.ed.x-l.st.x; 
    		return l.intersectionode(l1);  
    }
    
    Point ptoseg(Line l,Point p){  //输出点到线段上的最近点
        Line l1;  
        l1.st=l1.ed=p;
        l1.ed.x+=l.st.y-l.ed.y,l1.ed.y+=l.ed.x-l.st.x;  
        if ( ((p-l1.ed)^(p-l.ed)) * ((p-l1.ed)^(p-l.st)) >EPS)  
            return p.dist(l.st)<p.dist(l.ed)?l.st:l.ed;  
        return l.intersectionode(l1);  
    }  
    
    double disptoseg(Line l,Point p){ //输出点到线段的最短距离 
        Line l1;  
        l1.st=l1.ed=p;
        l1.ed.x+=l.st.y-l.ed.y,l1.ed.y+=l.ed.x-l.st.x;  
    	if ( ((p-l1.ed)^(p-l.ed)) * ((p-l1.ed)^(p-l.st)) >EPS)  
            return p.dist(l.st)<p.dist(l.ed)?p.dist(l.st):p.dist(l.ed);  
    	return fabs( ((p-l.st)^(p-l.ed)) / l.st.dist(l.ed));  
    }  
    // 求二维两直线的夹角,   
    // 返回值是0~Pi之间的弧度   
    double Inclination(Line L1, Line L2)   
    {   
        Point u = L1.ed - L1.st;   
        Point v = L2.ed - L2.st;   
        return acos( (u * v) / (Norm(u)*Norm(v)) );   
    }   
    

    展开全文
  • 计算几何知识点总结 来源于网络整理 一、引言  计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的...

                                                     计算几何知识点总结                                                                                来源于网络整理

    一、引言 

      计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为计算机科学的一个分支,计算几何主要研究解决几何问题的算法。在现代工程和数学领域,计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中,我们将对计算几何常用的基本算法做一个全面的介绍,希望对您了解并应用计算几何的知识解决问题起到帮助。
    二、目录
    本文整理的计算几何基本概念和常用算法包括如下内容:
    1. 矢量的概念
    2. 矢量加减法
    3. 矢量叉积
    4. 折线段的拐向判断
    5. 判断点是否在线段上
    6. 判断两线段是否相交
    7. 判断线段和直线是否相交
    8. 判断矩形是否包含点
    9. 判断线段、折线、多边形是否在矩形中
    10. 判断矩形是否在矩形中
    11. 判断圆是否在矩形中
    12. 判断点是否在多边形中
    13. 判断线段是否在多边形内
    14. 判断折线是否在多边形内
    15. 判断多边形是否在多边形内
    16. 判断矩形是否在多边形内
    17. 判断圆是否在多边形内
    18. 判断点是否在圆内
    19. 判断线段、折线、矩形、多边形是否在圆内
    20. 判断圆是否在圆内
    21. 计算点到线段的最近点
    22. 计算点到折线、矩形、多边形的最近点
    23. 计算点到圆的最近距离及交点坐标
    24. 计算两条共线的线段的交点
    25. 计算线段或直线与线段的交点
    26. 求线段或直线与折线、矩形、多边形的交点
    27. 求线段或直线与圆的交点
    28. 凸包的概念
    29. 凸包的求法
    三、算法介绍
    1.矢量的概念:
      如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点,我们可以把它称为矢量(vector)p2。
    2.矢量加减法:
       设二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量加法定义为: P + Q = ( x1 + x2 , y1 + y2 ),同样的,矢量减法定义为: P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P,P - Q = - ( Q - P )。
    3.矢量叉积:
      计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 ),Q = ( x2, y2 ),则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积,即:P × Q = x1*y2 - x2*y1,其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下,本文下述算法中所有的点都看作矢量,两点的加减法就是矢量相加减,而点的乘法则看作矢量叉积。
      叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
      若 P × Q > 0 , 则P在Q的顺时针方向。
      若 P × Q < 0 , 则P在Q的逆时针方向。
      若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。
    4.折线段的拐向判断:
      折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:
      若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
      若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
      若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。
    具体情况可参考下图:
    5.判断点是否在线段上:
      设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内。前者保证Q点在直线P1P2上,后者是保证Q点不在线段P1P2的延长线或反向延长线上,对于这一步骤的判断可以用以下过程实现:
      

    ON-SEGMENT(pi,pj,pk)//保证k点在线段内部
      if min(xi,xj) <= xk <= max(xi,xj) and min(yi,yj) <= yk <= max(yi,yj)
      then return true;
      else return false;


    特别要注意的是,由于需要考虑水平线段和垂直线段两种特殊情况,min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。
    6.判断两线段是否相交:
      我们分两步确定两条线段是否相交:
      (1)快速排斥试验
        设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交。
      (2)跨立试验
        如果两线段相交,则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是:( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示:
      在相同的原理下,对此算法的具体的实现细节可能会与此有所不同,除了这种过程外,大家也可以参考《算法导论》上的实现。
    7.判断线段和直线是否相交:
      有了上面的基础,这个算法就很容易了。如果线段P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。
    8.判断矩形是否包含点:
      只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
    9.判断线段、折线、多边形是否在矩形中:
      因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。
    10.判断矩形是否在矩形中:
      只要比较左右边界和上下边界就可以了。
    11.判断圆是否在矩形中:
      很容易证明,圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。
    12.判断点是否在多边形中:
      判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
      但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中,L和多边形的顶点相交,这时候交点只能计算一个;在图(b)中,L和多边形顶点的交点不应被计算;在图(c)和(d) 中,L和多边形的一条边重合,这条边应该被忽略不计。如果L和多边形的一条边重合,这条边应该被忽略不计。
      为了统一起见,我们在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。由此得出算法的伪代码如下:

     

    count ← 0;
    以P为端点,作从右向左的射线L; 
    for 多边形的每条边s
    do if P在边s上 
    then return true;
    if s不是水平的
    then if s的一个端点在L上
    if 该端点是s两端点中纵坐标较大的端点
    then count ← count+1
    else if s和L相交
    then count ← count+1;
    if count mod 2 = 1 
    then return true;
    else return false;


    其中做射线L的方法是:设P'的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),则P和P'就确定了射线L。 
      判断点是否在多边形中的这个算法的时间复杂度为O(n)。
      另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较,这种算法由于使用浮点数运算所以会带来一定误差,不推荐大家使用。 
    13.判断线段是否在多边形内: 
      线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能为凹,所以这不能成为判断的充分条件。如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交。 
      线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是否包含于多边形内部(反例见图b)。 
      因此我们可以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序(X坐标小的排在前面,对于X坐标相同的点,Y坐标小的排在前面,这种排序准则也是为了保证水平和垂直情况的判断正确),这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形内。 
      证明如下:
      命题1:
        如果线段和多边形的两相邻交点P1 ,P2的中点P' 也在多边形内,则P1, P2之间的所有点都在多边形内。
      证明:
        假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P'之间,因为多边形是闭合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P'属于多边性内部,P1-Q-P'完全连续,所以P1Q和QP'一定跨越多边形的边界,因此在P1,P'之间至少还有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕。 
      由命题1直接可得出推论:
      推论2:
      设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多边形内。
      在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段上就可以了。
      至此我们得出算法如下:

     

    if 线端PQ的端点不都在多边形内 
    then return false;
    点集pointSet初始化为空;
    for 多边形的每条边s
    do if 线段的某个端点在s上
    then 将该端点加入pointSet;
    else if s的某个端点在线段PQ上
    then 将该端点加入pointSet;
    else if s和线段PQ相交 // 这时候已经可以肯定是内交了
    then return false;
    将pointSet中的点按照X-Y坐标排序;
    for pointSet中每两个相邻点 pointSet[ i ] , pointSet[ i+1]
    do if pointSet [ i] , pointSet[ i+1] 的中点不在多边形中
    then return false;
    return true;


    这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n,所以最多是常数级的复杂度,几乎可以忽略不计。因此算法的时间复杂度也是O(n)。 
    14.判断折线是否在多边形内: 
      只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,则该算法的时间复杂度为O(m*n)。 
    15.判断多边形是否在多边形内: 
      只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。 
    16.判断矩形是否在多边形内: 
      将矩形转化为多边形,然后再判断是否在多边形内。 
    17判断圆是否在多边形内: 
      只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。 
    18.判断点是否在圆内: 
      计算圆心到该点的距离,如果小于等于半径则该点在圆内。 
    19.判断线段、折线、矩形、多边形是否在圆内: 
      因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。 
    20.判断圆是否在圆内: 
      设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r1<r2则O2不可能在O1内;否则如果两圆心的距离大于r1 - r2 ,则O2不在O1内;否则O2在O1内。 
    21.计算点到线段的最近点: 
      如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt2,斜率为:k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );该直线方程为:y = k* ( x - pt1.x) + pt1.y。其垂线的斜率为 - 1 / k,垂线方程为:y = (-1/k) * (x - point.x) + point.y 。 
      联立两直线方程解得:x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ,y = k * ( x - pt1.x) + pt1.y;然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足的距离,选择距离垂足较近的端点返回。 
    22.计算点到折线、矩形、多边形的最近点: 
      只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。 
    23.计算点到圆的最近距离及交点坐标: 
      如果该点在圆心,因为圆心到圆周任一点的距离相等,返回UNDEFINED。 
      连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius或 centerPoint.y - radius。如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,这时直线PO斜率为k = ( P.y - O.y )/ ( P.x - O.x )。直线PO的方程为:y = k * ( x - P.x) + P.y。设圆方程为(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2,联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。 
    24.计算两条共线的线段的交点: 
      对于两条共线的线段,它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点;图 (b) 和 (d) 中两条线段有无穷焦点;图 (c) 中两条线段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了line2的两个端点,则是图(d)的情况,两线段有无穷交点;如果line1只包含line2的一个端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图(c)的情况,这时两线段只有一个交点,否则就是图(b)的情况,两线段也是有无穷的交点;如果line1不包含line2的任何端点,则是图(a)的情况,这时两线段没有交点。 
    25.计算线段或直线与线段的交点: 
      设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。
     1. 首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。 
     2. 如果P1和P2横坐标相同,即L0平行于Y轴 
      a) 若L1也平行于Y轴, 
        i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
        ii. 否则说明L0和L1平行,他们没有交点; 
      b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交点纵坐标; 
     3. 如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标; 
     4. 如果P1和P2纵坐标相同,即L0平行于X轴 
      a) 若L1也平行于X轴, 
        i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
        ii. 否则说明L0和L1平行,他们没有交点; 
      b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交点横坐标; 
     5. 如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标; 
     6. 剩下的情况就是L1和L0的斜率均存在且不为0的情况 
      a) 计算出L0的斜率K0,L1的斜率K1 ; 
      b) 如果K1 = K2 
        i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
        ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
      c) 联立两直线的方程组可以解出交点来
      这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部看作直线来考虑。需要注意的是,我们可以将直线或线段方程改写为ax+by+c=0的形式,这样一来上述过程的部分步骤可以合并,缩短了代码长度,但是由于先要求出参数,这种算法将花费更多的时间。 
    26.求线段或直线与折线、矩形、多边形的交点: 
      分别求与每条边的交点即可。 
    27.求线段或直线与圆的交点: 
      设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。 
      1. 如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步。 
      2. 如果L平行于Y轴, 
       a) 计算圆心到L的距离dis;
       b) 如果dis > r 则L和圆没有交点;
       c) 利用勾股定理,可以求出两交点坐标,但要注意考虑L和圆的相切情况。
      3. 如果L平行于X轴,做法与L平行于Y轴的情况类似; 
      4. 如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点; 
      5. 如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。 
    28.凸包的概念: 
      点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 
    29.凸包的求法: 
      现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话,Krikpatrick和Seidel的剪枝搜索算法可以达到O(n*logh),在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单介绍一下Graham扫描法,其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。 
      对于一个有三个或以上点的点集Q,Graham扫描法的过程如下: 
      

    令p0为Q中Y-X坐标排序下最小的点 
      设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集(如果有多个点有相同的极角,除了距p0最远的点外全部移除
      压p0进栈S
      压p1进栈S
      压p2进栈S
    for i ← 3 to m
    do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧
    对S弹栈
    压pi进栈S
    return S;

     


      此过程执行后,栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是,我们对点按极角逆时针排序时,并不需要真正求出极角,只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。 
    四、结语 
      尽管人类对几何学的研究从古代起便没有中断过,但是具体到借助计算机来解决几何问题的研究,还只是停留在一个初级阶段,无论从应用领域还是发展前景来看,计算几何学都值得我们认真学习、加以运用,希望这篇文章能带你走进这个丰富多彩的世界。

    目录 
    ㈠ 点的基本运算 
    1. 平面上两点之间距离 1 
    2. 判断两点是否重合 1 
    3. 矢量叉乘 1 
    4. 矢量点乘 2 
    5. 判断点是否在线段上 2 
    6. 求一点饶某点旋转后的坐标 2 
    7. 求矢量夹角 2 
    ㈡ 线段及直线的基本运算 
    1. 点与线段的关系 3 
    2. 求点到线段所在直线垂线的垂足 4 
    3. 点到线段的最近点 4 
    4. 点到线段所在直线的距离 4 
    5. 点到折线集的最近距离 4 
    6. 判断圆是否在多边形内 5 
    7. 求矢量夹角余弦 5 
    8. 求线段之间的夹角 5 
    9. 判断线段是否相交 6 
    10.判断线段是否相交但不交在端点处 6 
    11.求线段所在直线的方程 6 
    12.求直线的斜率 7 
    13.求直线的倾斜角 7 
    14.求点关于某直线的对称点 7 
    15.判断两条直线是否相交及求直线交点 7 
    16.判断线段是否相交,如果相交返回交点 7 
    ㈢ 多边形常用算法模块 
    1. 判断多边形是否简单多边形 8 
    2. 检查多边形顶点的凸凹性 9 
    3. 判断多边形是否凸多边形 9 
    4. 求多边形面积 9 
    5. 判断多边形顶点的排列方向,方法一 10 
    6. 判断多边形顶点的排列方向,方法二 10 
    7. 射线法判断点是否在多边形内 10 
    8. 判断点是否在凸多边形内 11 
    9. 寻找点集的graham算法 12 
    10.寻找点集凸包的卷包裹法 13 
    11.判断线段是否在多边形内 14 
    12.求简单多边形的重心 15 
    13.求凸多边形的重心 17 
    14.求肯定在给定多边形内的一个点 17 
    15.求从多边形外一点出发到该多边形的切线 18 
    16.判断多边形的核是否存在 19 
    ㈣ 圆的基本运算 
    1 .点是否在圆内 20 
    2 .求不共线的三点所确定的圆 21 
    ㈤ 矩形的基本运算 
    1.已知矩形三点坐标,求第4点坐标 22 
    ㈥ 常用算法的描述 22 
    ㈦ 补充 
    1.两圆关系: 24 
    2.判断圆是否在矩形内: 24 
    3.点到平面的距离: 25 
    4.点是否在直线同侧: 25 
    5.镜面反射线: 25 
    6.矩形包含: 26 
    7.两圆交点: 27 
    8.两圆公共面积: 28 
    9. 圆和直线关系: 29 
    10. 内切圆: 30 
    11. 求切点: 31 
    12. 线段的左右旋: 31 
    13.公式: 32 

     

     

    /* 需要包含的头文件 */ 
    #include <cmath > 
    
    /* 常用的常量定义 */ 
    const double INF = 1E200 
    const double EP = 1E-10 
    const int MAXV = 300 
    const double PI = 3.14159265 
    
    /* 基本几何结构 */ 
    struct POINT 
    { 
        double x; 
        double y; 
        POINT(double a=0, double b=0) { x=a; y=b;} //constructor 
    }; 
    struct LINESEG 
    { 
        POINT s; 
        POINT e; LINESEG(POINT a, POINT b) { s=a; e=b;} 
        LINESEG() { } 
    }; 
    struct LINE // 直线的解析方程 a*x+b*y+c=0 为统一表示,约定 a >= 0 
    { 
        double a; 
        double b; 
        double c; LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;} 
    }; 
    
    
    /********************\ 
    * 点的基本运算 * 
    \********************/ 
    double dist(POINT p1,POINT p2) // 返回两点之间欧氏距离 
    { 
       return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) ); 
    } 
    bool equal_point(POINT p1,POINT p2) // 判断两个点是否重合 
    { 
       return ( (abs(p1.x-p2.x)<EP)&&(abs(p1.y-p2.y)<EP) ); 
    } 
    
    
    /****************************************************************************** 
    r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉积 
    r>0:ep在矢量opsp的逆时针方向; 
    r=0:opspep三点共线; 
    r<0:ep在矢量opsp的顺时针方向 
    *******************************************************************************/ 
    double multiply(POINT sp,POINT ep,POINT op) 
    { 
       return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); 
    } 
    
    
    /******************************************************************************* 
    r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的点积,如果两个矢量都非零矢量 
    r<0:两矢量夹角为锐角;r=0:两矢量夹角为直角;r>0:两矢量夹角为钝角 
    *******************************************************************************/ 
    double dotmultiply(POINT p1,POINT p2,POINT p0) 
    { 
        return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y)); 
    } 
    /* 判断点p是否在线段l上,条件:(p在线段l所在的直线上)&& (点p在以线段l为对角线的矩形内) */ 
    bool online(LINESEG l,POINT p) 
    { 
       return((multiply(l.e,p,l.s)==0) &&( ( (p.x-l.s.x)*(p.x-l.e.x)<=0 )&&( (p.y-l.s.y)*(p.y-l.e.y)<=0 ) ) ); 
    } 
    // 返回点p以点o为圆心逆时针旋转alpha(单位:弧度)后所在的位置 
    POINT rotate(POINT o,double alpha,POINT p) 
    { 
        POINT tp; 
        p.x-=o.x; 
        p.y-=o.y; 
        tp.x=p.x*cos(alpha)-p.y*sin(alpha)+o.x; 
        tp.y=p.y*cos(alpha)+p.x*sin(alpha)+o.y; 
        return tp; 
    } 
    
    
    /* 返回顶角在o点,起始边为os,终止边为oe的夹角(单位:弧度) 
    角度小于pi,返回正值 
    角度大于pi,返回负值 
    可以用于求线段之间的夹角 
    */ 
    double angle(POINT o,POINT s,POINT e) 
    { 
    double cosfi,fi,norm; 
    double dsx = s.x - o.x; 
    double dsy = s.y - o.y; 
    double dex = e.x - o.x; 
    double dey = e.y - o.y; 
    
    
    cosfi=dsx*dex+dsy*dey; 
    norm=(dsx*dsx+dey*dey)*(dex*dex+dey*dey); 
    cosfi /= sqrt( norm ); 
    
    
    if (cosfi >= 1.0 ) return 0; 
    if (cosfi <= -1.0 ) return -3.1415926; 
    
    
    fi=acos(cosfi); 
    if (dsx*dey-dsy*dex>0) return fi; // 说明矢量os 在矢量 oe的顺时针方向 
    return -fi; 
    }
    
    
    /*****************************\ 
    * * 
    * 线段及直线的基本运算 * 
    * * 
    \*****************************/ 
    
    
    /* 判断点与线段的关系,用途很广泛 
    本函数是根据下面的公式写的,P是点C到线段AB所在直线的垂足 
    
    
    AC dot AB 
    r = --------- 
    ||AB||^2 
    (Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay) 
    = ------------------------------- 
    L^2 
    r has the following meaning: 
    r=0 P = A 
    r=1 P = B 
    r<0 P is on the backward extension of AB 
    r>1 P is on the forward extension of AB 
    0<r<1 P is interior to AB 
    */ 
    double relation(POINT p,LINESEG l) 
    { 
        LINESEG tl; 
        tl.s=l.s; 
        tl.e=p; 
        return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e)); 
    } 
    
    
    // 求点C到线段AB所在直线的垂足 P 
    POINT perpendicular(POINT p,LINESEG l) 
    { 
        double r=relation(p,l); 
        POINT tp; 
        tp.x=l.s.x+r*(l.e.x-l.s.x); 
        tp.y=l.s.y+r*(l.e.y-l.s.y); 
        return tp; 
    } 
    /* 求点p到线段l的最短距离,并返回线段上距该点最近的点np 
    注意:np是线段l上到点p最近的点,不一定是垂足 */ 
    double ptolinesegdist(POINT p,LINESEG l,POINT &np) 
    { 
        double r=relation(p,l); 
        if(r<0) 
        { 
           np=l.s; 
           return dist(p,l.s); 
        } 
        if(r>1) 
        { 
           np=l.e; 
           return dist(p,l.e); 
        } 
        np=perpendicular(p,l); 
        return dist(p,np); 
    } 
    
    
    // 求点p到线段l所在直线的距离,请注意本函数与上个函数的区别 
    double ptoldist(POINT p,LINESEG l) 
    { 
        return abs(multiply(p,l.e,l.s))/dist(l.s,l.e); 
    } 
    
    
    /* 计算点到折线集的最近距离,并返回最近点. 
    注意:调用的是ptolineseg()函数 */ 
    double ptopointset(int vcount,POINT pointset[],POINT p,POINT &q) 
    { 
        int i; 
        double cd=double(INF),td; 
        LINESEG l; 
        POINT tq,cq;  
        for(i=0;i<vcount-1;i++) 
        { 
           l.s=pointset[ i ]; 
           l.e=pointset[i+1]; 
           td=ptolinesegdist(p,l,tq); 
           if(td<cd) 
           { 
              cd=td; 
              cq=tq; 
           } 
        } 
        q=cq; 
        return cd; 
    } 
    /* 判断圆是否在多边形内.ptolineseg()函数的应用2 */ 
    bool CircleInsidePolygon(int vcount,POINT center,double radius,POINT polygon[]) 
    { 
        POINT q; 
        double d; 
        q.x=0; 
        q.y=0; 
        d=ptopointset(vcount,polygon,center,q); 
        if(d<radius||fabs(d-radius)<EP) 
            return true; 
        else 
           return false; 
    } 
    
    
    /* 返回两个矢量l1和l2的夹角的余弦(-1 --- 1)注意:如果想从余弦求夹角的话,注意反余弦函数的定义域是从 0到pi */ 
    double cosine(LINESEG l1,LINESEG l2) 
    { 
        return (((l1.e.x-l1.s.x)*(l2.e.x-l2.s.x) + 
         (l1.e.y-l1.s.y)*(l2.e.y-l2.s.y))/(dist(l1.e,l1.s)*dist(l2.e,l2.s))) ); 
    } 
    // 返回线段l1与l2之间的夹角 单位:弧度 范围(-pi,pi) 
    double lsangle(LINESEG l1,LINESEG l2) 
    { 
        POINT o,s,e; 
        o.x=o.y=0; 
        s.x=l1.e.x-l1.s.x; 
        s.y=l1.e.y-l1.s.y; 
        e.x=l2.e.x-l2.s.x; 
        e.y=l2.e.y-l2.s.y; 
        return angle(o,s,e); 
    } 
    // 如果线段u和v相交(包括相交在端点处)时,返回true 
    bool intersect(LINESEG u,LINESEG v) 
    { 
        return( (max(u.s.x,u.e.x)>=min(v.s.x,v.e.x))&& //排斥实验 
        (max(v.s.x,v.e.x)>=min(u.s.x,u.e.x))&& 
        (max(u.s.y,u.e.y)>=min(v.s.y,v.e.y))&& 
        (max(v.s.y,v.e.y)>=min(u.s.y,u.e.y))&& 
        (multiply(v.s,u.e,u.s)*multiply(u.e,v.e,u.s)>=0)&& //跨立实验 
        (multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0)); 
    } 
    
    
    
    
    // (线段u和v相交)&&(交点不是双方的端点) 时返回true 
    bool intersect_A(LINESEG u,LINESEG v) 
    { 
       return((intersect(u,v))&& 
        (!online(u,v.s))&& 
        (!online(u,v.e))&& 
        (!online(v,u.e))&& 
        (!online(v,u.s))); 
    } 
    
    
    // 线段v所在直线与线段u相交时返回true;方法:判断线段u是否跨立线段v 
    bool intersect_l(LINESEG u,LINESEG v) 
    { 
         return multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0; 
    } 
    
    // 根据已知两点坐标,求过这两点的直线解析方程: a*x+b*y+c = 0 (a >= 0) 
    LINE makeline(POINT p1,POINT p2) 
    { 
        LINE tl; 
        int sign = 1; 
        tl.a=p2.y-p1.y;
    	if(tl.a<0) 
        { 
            sign = -1; 
            tl.a=sign*tl.a; 
        } 
        tl.b=sign*(p1.x-p2.x); 
        tl.c=sign*(p1.y*p2.x-p1.x*p2.y); 
        return tl; 
    } 
    
    // 根据直线解析方程返回直线的斜率k,水平线返回 0,竖直线返回 1e200 
    double slope(LINE l) 
    { 
        if(abs(l.a) < 1e-20)return 0; 
        if(abs(l.b) < 1e-20)return INF; 
        return -(l.a/l.b); 
    } 
    
    
    // 返回直线的倾斜角alpha ( 0 - pi) 
    double alpha(LINE l) 
    { 
        if(abs(l.a)< EP)return 0; 
        if(abs(l.b)< EP)return PI/2; 
        double k=slope(l); 
        if(k>0) 
           return atan(k); 
        else 
           return PI+atan(k); 
    } 
    
    
    // 求点p关于直线l的对称点 
    POINT symmetry(LINE l,POINT p) 
    { 
        POINT tp; 
        tp.x=((l.b*l.b-l.a*l.a)*p.x-2*l.a*l.b*p.y-2*l.a*l.c)/(l.a*l.a+l.b*l.b); 
        tp.y=((l.a*l.a-l.b*l.b)*p.y-2*l.a*l.b*p.x-2*l.b*l.c)/(l.a*l.a+l.b*l.b); 
        return tp; 
    } 
    
    
    // 如果两条直线 l1(a1*x+b1*y+c1 = 0), l2(a2*x+b2*y+c2 = 0)相交,返回true,且返回交点p 
    bool lineintersect(LINE l1,LINE l2,POINT &p) // 是 L1,L2 
    { 
        double d=l1.a*l2.b-l2.a*l1.b; 
        if(abs(d)<EP) // 不相交 
           return false; 
        p.x = (l2.c*l1.b-l1.c*l2.b)/d; 
        p.y = (l2.a*l1.c-l1.a*l2.c)/d; 
        return true; 
    } 
    
    
    // 如果线段l1和l2相交,返回true且交点由(inter)返回,否则返回false 
    bool intersection(LINESEG l1,LINESEG l2,POINT &inter) 
    { 
         LINE ll1,ll2; 
         ll1=makeline(l1.s,l1.e); 
         ll2=makeline(l2.s,l2.e); 
         if(lineintersect(ll1,ll2,inter)) 
         { 
             return online(l1,inter); 
        } 
        else 
             return false; 
    }
    可以应付大部分zoj上的几何题Sample TextSample Text
    
    
    zoj上的计算几何题
    Vol I 
    1010 by pandahyx 
    1032 by javaman 
    1037 by Vegetable Bird 
    1041 by javaman 
    1081 by Vegetable Bird 
    1090 by Vegetable Bird 
    
    
    Vol II 
    1104 by javaman 
    1123 by javaman 
    1139 by Vegetable Bird 
    1165 by javaman 
    1199 by Vegetable Bird 
    
    
    Vol V 
    1426 by Vegetable Bird 
    1439 by Vegetable Bird 
    1460 by Vegetable Bird 
    1472 by Vegetable Bird 
    
    
    Vol VI 
    1597 by Vegetable Bird 
    
    
    Vol VII 
    1608 by Vegetable Bird 
    1648 by Vegetable Bird 
    
    
    Vol XII 
    2102 by pandahyx 
    2107 by pandahyx 
    2157 by pandahyx 
    
    
    Vol XIII 
    2234 by pandahyx 
    
    
    Vol XIV 
    2318 by ahyangyi 
    2394 by qherlyt 
    
    
    Vol XV 
    2403 by Vegetable Bird




     

    展开全文
  • 计算几何题的特点与做题要领: 1.大部分不会很难,少部分题目思路很巧妙 2.做计算几何题目,模板很重要,模板必须高度可靠。 3.要注意代码的组织,因为计算几何的题目很容易上两百行代码,里面大部分是模板。如果...
  • ACM计算几何模板(模板)

    千次阅读 2016-08-15 21:39:42
    1. 判断空间三点共线 点的储存方式: 判断...角度是按逆时针来计算的 如计算点积,角度是向量p1逆时针转到p2的角度 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qtTHhNQD-1613976880250)...
  • 要求计算多边形的面积。 多边形被放置在一个X-Y的卡笛尔平面上,它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数(因此多边形的面积也为整数) 输入 第 一行...
  • acm计算几何与数论

    2018-09-09 08:18:17
    acm计算几何模板
  • //计算线段与圆的交点可用这个函数后判点是否在线段上 void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2){ point p=c; double t; p.x+=l1.y-l2.y; p.y+=l2.x-l1.x; ...
  • acm 计算几何题目集合

    千次阅读 2015-01-27 14:36:43
    计算几何题的特点与做题要领: 1.大部分不会很难,少部分题目思路很巧妙 2.做计算几何题目,模板很重要,模板必须高度可靠。 3.要注意代码的组织,因为计算几何的题目很容易上两百行代码,里面大部分是模板。如果...
  • 有南邮校队的ACM计算几何的课件,内容虽然不丰富,但还算实用
  • ACM 计算几何

    2010-11-08 23:02:58
    计算几何
  • [转载]...! 文章目录1 前言1.1 计算几何算法1.2 计算几何题目特点及要领1.3 预备知识2 凸包2.1 定义2.1.1 凸多边形2.1.2 凸包2.2 颜料配色问题2.2.1 问题描述2.2.2 问题...
  • ACM计算几何题目推荐

    千次阅读 2016-12-20 22:03:02
    3.要注意代码的组织,因为计算几何的题目很容易上两百行代码,里面大部分是模板。如果代码一片混乱,那么会严重影响做题正确率。 4.注意精度控制。 5.能用整数的地方尽量用整数,要想到扩大数据的方法(扩大一倍,...
  • 里面有介绍acm计算几何的详细ppt,涵盖各种计算几何的知识!
  • ACM计算几何源码

    2011-09-16 23:09:50
    计算几何常用算法,包括凸包算法,平面点集最接远对算法,平面点集最接近对算法,计算任意多边形的面积,三角形相关算法。
  • 计算几何,北大暑期acm,讲解详细,难度较大,没有学过的可以先下载回去受点打击
  • ACM计算几何模板大全 线段 圆 凸包 平面 立体几何 最小圆覆盖 多边形 切割 交并
  • ACM计算几何总结

    千次阅读 多人点赞 2018-09-11 12:52:04
    1 几何基础 2 点与向量 2.1 手动实现 2.2 复数黑科技 3 点与线 3.1 直线定义 3.2 求两直线交点 3.3 求点到直线距离 3.4 求点到线段距离 3.5 求点在直线上的投影点 3.6 判断点是否在线段上 3.7 判断两...
  • acm计算几何模版.

    2012-02-10 20:07:01
    不错的一份计算几何模版!适用于ACM的。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,167
精华内容 4,466
关键字:

acm计算几何