计算几何的一点笔记

1.点积Dot Product Cos(θ) = (A ⋅ B)/(|A||B|) so we can get angle θ by acos function , θ 是A，B的夹角 没有正负

 

2.叉积Cross Product  A x B = |A||B|Sin(θ) , θ 的正负由A，B的右手定则决定

其值同时代表A,B形成的平行四边形的面积

 

3.线段与点之间距离Line-Point Distance L = | (AB x AC)/|AB| |其中L是从C到A,B这条直线的距离 因为AB x AC/2是ABC形成的三角形面积 而三角形面积也等于|AB|*L/2 注意根据cross product的定义 L值应该取绝对值

 

4.求垂直平分线 首先构造AB的方程 Ax+By=C 则平分线方程为 -Bx+Ay=D 把AB的中点代入进去就得到了D

 

5.求3点共圆 A,B,C 首先做出 AB 和 BC的平分线 求出交点o 则交点o就是圆心 而 dis(o, B)就是半径

6.求点A相对一直线L的对面点B 首先得到AB的方程 根据A点坐标求出AB的方程 再求出AB与L的交点Y 接着就是A' = 2 * Y - X

 

7.求50000个点的最远距离 先用NlogN的算法求凸包 再枚举点距

 

8.判断一个点是否在一个多边形内 可以沿这个点做一条射线 然后判断这个点与其他边的交点的个数 如果是偶数则在外部 如果为奇数 则在里面 如果在边界 可以用点线距为0来判断

 

9.球坐标转化成立体坐标   

    double x = sin(lng/180*PI)*cos(lat/180*PI)*alt;
    double y = cos(lng/180*PI)*cos(lat/180*PI)*alt;
    double z = sin(lat/180*PI)*alt；

2.关于凸包的题目

gift-Wrapping算法复杂度O(n^2)很慢
Gram-Scan算法复杂度为O(NlogN) 但是极角序存在一些问题 所以最好写成水平序

Melkan算法是对于多边形的凸包算法 效率为O(N) 但是对于点集首先要用排序将其转化成多边形(复杂度为(NlogN)) 不实用

如果点是有限制的 比如0 <= x,y <= N 则可以现用maxy[x], miny[x]来保存纵坐标的最大值 和 最小值 显然只有这些点才可能出现在凸包上面 然后使用Graham-Scan算法按横坐标从小到大排序求凸包即可（蓝书P8） 这样排序的时间从nlogn 变成N

1.怎样由凸包上面的点确定最大的三角形面积？

枚举每一个点a

  定下b点为a+1 c为a+2

    移动c点直到面积不再增加（因为是凸多边形 故面积呈现先增后减序列）

      移动b点在a，c之间 直到面积不再增加

 

刚刚看到的别人的学习札记，先copy过来再说，有时间再看看。