//二维计算几何模板
#includ e
#includ e
#includ e
#includ e
using namespace std;
//-----------------基础定义-----------------
struct point
{
d oubl
e x,y;
point(d oubl e x=0,doubl e y=0):x(x),y(y){}//构造
};
typed ef 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,d oubl e p) {return vector(a.x*p,a.y*p);}
vector operator / (vector a,d oubl e p) {return vector(a.x/p,a.y/p);}
bool operator < (const point& a,const point& b) {return a.x //高精度比较 const d oubl e eps=1e-10; int d cmp(d oubl e x) {if(fabs(x) bool operator == (const point &a,const point &b) { return d cmp(a.x-b.x)==0&&d cmp(a.y-b.y)==0;} //---------------------------------------- //-----------------向量------------------- //点积 d oubl e d ot(vector a,vector b) { return a.x*b.x+a.y*b.y;} //向量模 d oubl e length(vector a) { return sqrt(dot(a,a));} //两向量夹角 d oubl e angl e(vector a,vector b) {return acos(d ot(a,b)/l ength(a)/l ength(b));} //叉积 d oubl e cross(vector a,vector b) {return a.x*b.y-a.y*b.x;} //三点平行四边形面积，除以2为三角形面积 d oubl e area2(point a,point b,point c) {return cross(b-a,c-a);} //向量旋转，rad>0逆时针，rad<0顺时针 vector rotate(vector a,doubl e rad) {return vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));} //向量逆时针旋转90度 vector normal(vector a) {d oubl e l=l ength(a);return vector(-a.y/l,a.x/l);} //--------------------------------------- //-----------------直线------------------ //直线交点,调用前确保有交点，叉积判断 point GetLineIntersection(point p,vector v,point q,vector w) { vector u=p-q; d oubl e t=cross(w, u)/cross(v, w); return p+v*t; } //点到直线距离 d oubl e DstanceToLine(point p,point a,point b) { vector v1=b-1,v2=p-a; return fabs(cross(v1, v2))/l ength(v1); } //求p点在直线ab上的投影 point GetLineProjection(point p,point a,point b) { vector v=b-a; return a+v*(d ot(v,p-a))/dot(v,v); } //--------------------------------------- //---------------线段--------------- //点到线段的距离 d oubl e distancetosegma(point p,point a,point b) if(a==b) return length(p-a); vector v1=b-a,v2=p-a,v3=p-b; if(d cmp(cross(v1, v2))<0) return l ength(v2); else if(dcmp(dot(v1,v3))>0) return l ength(v1); else return fabs(cross(v1, v2))/l ength(v1); } //线段规范相交，交点不含端点 bool segmentproperintersection(point a1,point a2,point b1,point b2) { d oubl e c1=cross(a2-a1, b1-a1),c2=cross(a2-a1, b2-a1), c3=cross(b2-b1, a1-b1),c4=cross(b2-b1, a2-b1); return d cmp(c1)*dcmp(c2)<0&&d cmp(c3)*d cmp(c4)<0; } //p点是否在线段ab上,<=0表示p点可能在端点上 bool onsegment(point p,point a1,point a2) {return d cmp(cross(a1-p, a2-p))==0&&d cmp(dot(a1-p, a2-p))<=0;} //二者结合判断线段相交 //求两线段交点，线段共线（cross()==0）不行 point GetSegmentIntesection(point a1,point a2,point b1,point b2) { d oubl e s1=fabs(cross(b1-a1, a2-a1)), s2=fabs(cross(a2-a1, b2-a1)); point p; p.x=(s1*b2.x+s2*b1.x)/(s1+s2); p.y=(s1*b2.y+s2*b1.y)/(s1+s2); return p; } //----------------------------------- //--------------n边形----------------- //极角排序 bool cmpPolarange(point a,point b) { point c(1,1);//按c点排序 return d cmp(cross(a-c, b-c))>0; } //n边形有向面积,逆时针？ d oubl e polygenarea(point *p,int n) d oubl e area=0; for(int i=1;i area+=cross(p[i]-p[0], p[i+1]-p[0]); return area/2; } //判断点是否在多边形内，凹凸都适合，逆时针 int isPointInPolygon(point p,point *poly,int n) { int wn=0,i; for(i=0;i { if(onsegment(p, poly[i], poly[(i+1)%n])) return -1;//在边界上 int k=d cmp(cross(poly[(i+1)%n]-poly[i], p-poly[i])); int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%n].y-p.y); if(k>0&&d1<=0&&d2>0) wn++; if(k<0&&d2<=0&&d1>0) wn--; } if(wn!=0) return 1;//在内部 return 0;//不在内部 } ///////////////////////////// //Andrew算法求凸包,确保没有重复点 bool cmpXY(point a,point b) { if(a.x==b.x) return a.y else return a.x } //若让ch不保存凸包边上的点则将两个<=改为< int ConvexHull(point *p,int n,point *ch) { sort(p,p+n,cmpXY); int m=0,i; for(i=0;i { whil e(m>1&&cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } int k=m; for(i=n-2;i>=0;i--) { whil e(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; } ///////////////////////////// //------------------------------------ //-------------半平面------------------ //有向直线 struct line { point p; vector v; d oubl e ang;//向量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 }; //点p在直线l的左边 bool OnLeft(line l,point p) {return cross(l.v, p-l.p)>0;} //直线a，b的交点 point GetIntersection(line a,line b) { vector u=a.p-b.p; d oubl e 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 first,last;//双端队列指针 point *p=new point[n]; line *q=new line[n]; q[first=last=0]=l[0]; int i; for(i=1;i { whil e(first whil e(first q[++last]=l[i]; if(fabs(cross(q[last].v, q[last-1].v)) { last--; if(OnLeft(q[last], l[i].p)) q[last]=l[i]; } if(first } whil e(first if(last-first<=1) return 0; p[last]=GetIntersection(q[last], q[first]); int m=0; for(i=first;i<=last;i++) poly[m++]=p[i]; return m; } //------------------------------------ int main() { return 0; } 计算几何基础知识整理 一、序言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、本基础目录 本文整理的计算几何基本概念和常用算法包括如下内容： 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 向量法解立体几何 用传统的方法解立体几何需要烦琐的分析、复杂的计算。而用向量法解题思路清晰、过程简洁。对立体几何的常见问题都可以起到化繁为简，化难为易的效果。 一. 证明两直线平行 已知两直线a 和b , b D C a B A ∈∈,,,,则?b a //存在唯一的实数λ使CD AB λ= 二. 证明直线和平面平行 1.已知直线αα∈∈?E D C a B A a ,,,,,且三点不共线，则a ∥?α存在有序实数 对μλ,使CE CD AB μλ+= 2.已知直线,,,a B A a ∈?α和平面 α的法向量n ,则a ∥n AB ⊥?α 三.证明两个平面平行 已知两个不重合平面βα,,法向量分别为n m ,,则α∥n m //?β 四．证明两直线垂直 已知直线b a ,。b D C a B A ∈∈,,,，则0=??⊥CD AB b a 五.证明直线和平面垂直 已知直线α和平面a ，且A 、B a ∈,面α的法向量为m ,则m AB a //?⊥α 六.证明两个平面垂直 已知两个平面βα,,两个平面的法向量分别为n m ,,则n m ⊥?⊥βα 七．求两异面直线所成的角 已知两异面直线b a ,，b D C a B A ∈∈,,,，则异面直线所成的角θ 为：CD AB ?=θcos 八．求直线和平面所成的角 A B 已知A,B 为直线a 上任意两点，n 为平面α的法向量，则a 和平面α所成的角θ为: 1． 当??? ? ??2, 0π 时?-=2πθ 2． 当??? ??∈?ππ,2 时2πθ-?= 九．求二面角 1．已知二面角βα--l ，且l CD l AB D C B A ⊥⊥∈∈,,,,且βα，则二面角的平面角θ 的大小为：=θ 2.已知二面角,βα--l n m ,分别为面βα,的法向量，则二面角的平面角θ的 大小与两个法向量所成的角相等或互补。即-=πθ 注:如何判断二面角的平面角和法向量所成的角的关系。 (1)通过观察二面角锐角还是钝角,再由法向量的成的角求之。 (2)通过观察法向量的方向,判断法向量所成的角与二面角的平面角相等还是互补。 十.求两条异面直线的距离 已知两条异面直线b a ,,m 是与两直线都垂直的向量,b B a A ∈∈,则两条 异面直线的距离d = 十一.求点到面的距离 已知平面α和点A,B 且αα∈?B A ,,m 为平面α的法向量,则点A 到平面 α 的距离d = POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 常见几何体的面积、体积求法与应用 要计算某材料的密度、重量，研究某物体性能及其物质结构等，特别对于机械专业的学生，必须要求工件的面积、体积等，若按课本上公式来计算，而课本上公式不统一，不好记住，并且很繁杂，应用时要找公式，对号入座很麻烦。笔者在教学与实践中总结出一种计算常见几何体的面积、体积方法。其公式统一，容易记住，且计算简单。对技校学生来说，排除大部分繁琐的概念、定理，以及公式的推导应用等。 由统计学中的用加权平均数对估计未来很准确。比如，估计某商品下个月销售量，若去年平均销售量为y ，设本月权为4，上月权数为1，下月权数为1，各月权数分别乘销售量相加后除以6等于y 。这样能准确地确定下个月销售量。能不能以这种思想方法用到求几何体的面积、体积呢？通过推导与实践，对于常见的几何体确实可用这种方法来求得其面积、体积。下面分别说明求常见几何体的面积、体积统一公式的正确性与可用性。 常见几何体的面积、体积统一公式： ) 4(6 )4(621002100S S S h V C C C h A ++= ++= （其中A 为几何体侧面积，C 0为上底面周长，C 1为中间横截面周长，C 2 为下底面周长，V 为几何体体积，S 0为上底面面积，S 1为中间横截面面积，S 2为下底面面积，h 为高，h 0为斜高或母线长。注：中间横截面为上、下底等距离的截面。） 一、棱柱、棱锥、棱台、圆柱、圆锥、圆台的面积 、体积用统一公式的正确性 1、棱柱： ⑴据棱柱上底周长、下底周长、中间横截面周长相等，即2 1 C C C ==， 可得： 2020210066 )4(6 C h C h C C C h =?= ++，这与课本中的棱柱侧面积公式等同。 以下每个几何体都能推得与课本中相应公式等同，说明这统一公式的正确性。 ⑵据棱柱上底面、下底面、中间横截面相等，可知：2 1 S S S ==，即： h S S S S h S S S h V 2222210)4(6 )4(6 =++= ++= 。 2、棱锥 ⑴设底边长为a 2，边数为n ，斜高为h 0，侧面三角形中位线为a 1，则 立体几何与平面几何计算公式 初中数学几何中，不论是平面几何还是立体几何，他们的计算公式是我们进行数学试题计算的基础，因此，希望中考考生积极的做好几何计算公式的复习。下面是初中数学几何计算公式，一起了解一下： 1 、正方形 C：周长S：面积：a：边长 周长=边长×4 C=4a 正方形面积=边长×边长S= a a 2 、长方形C：周长S：面积a：边长 周长=(长+宽)×2 C = 2(a+b) 长方形面积=长×宽S = a b 3 、三角形s：面积a：底h：高 三角形面积=底×高÷2 s = ah÷2 4 、平行四边形s：面积a：底h：高 平行四边形面积=底×高s = ah 5、梯形s面积a上底b下底h高 梯形面积=(上底+下底)×高÷2 s = (a+b) h÷2 6 、圆形r:半径d：直径c：周长s：面积 半径=直径÷2 r = d/2 半径=周长÷圆周率÷2 r = c/2π 直径=半径×2 d = 2r 直径=周长÷圆周率d = c/π 周长=圆周率×直径 c = πd 周长=圆周率×半径×2 c = 2πr 圆面积=圆周率×半径×半径s = πr r 圆环面积=圆周率×(大圆半径×大圆半径-小圆半径×小圆半径) s=π(R R-r r) 7 、长方体V:体积s:面积a:长b: 宽h:高 体积=长×宽×高V = abh 8、正方体V:体积a:棱长 总棱长=棱长×12 C = 12a 表面积=棱长×棱长×6 S表= a a6 体积=棱长×棱长×棱长V = a a a 9、圆柱体V:体积s:底面积h:高 圆柱体侧面积=底面周长×高s= c h 圆柱体体积=底面积×高V= sh 圆柱体体积=圆周率×半径×半径×高V =πr r h 圆柱体体积=1/2×侧面积×半径V =1/2s侧r 10、圆锥体V:体积s:底面积h:高 圆锥体体积=1/3×底面积×高V = 1/3sh 圆锥体体积=1/3×圆周率×半径×半径×高V = 1/3×πr r h GIS算法的计算几何基础 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。 如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量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 )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。 设矢量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共线，但可能同向也可能反向。 折线段的拐向判断： 折线段的拐向判断方法可以直接由矢量叉积的性质推出。 对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向： 若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。 若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。 空间角和距离的计算(1) 一 线线角 1．直三棱柱A 1B 1C 1-ABC ，∠BCA=900，点D 1，F 1分别是A 1B 1和A 1C 1的中点，若BC=CA=CC 1，求BD 1与AF 1所成角的余弦值． 2．在四棱锥P-ABCD 中，底面ABCD 是直角梯形，∠BAD=900，AD ∥BC ，AB=BC=a ，AD=2a ，且PA ⊥面ABCD ，PD 与底面成300角． （1）若AE ⊥PD ，E 为垂足，求证：BE ⊥PD ； （2）若AE ⊥PD ，求异面直线AE 与CD 所成角的大小． 二．线面角 1．正方体ABCD-A 1B 1C 1D 1中，E ，F 分别为BB 1、CD 的中点，且正方体的棱长为2． （1）求直线D 1F 和AB 和所成的角； （2）求D 1F 与平面AED 所成的角． F 1D 1B 1 C 1A 1 B A C A B C D P E C D E F D 1 C 1 B 1 A 1 A B 2．在三棱柱A 1B 1C 1-ABC 中，四边形AA 1B 1B 是菱形，四边形BCC 1B 1是矩形，C 1B 1⊥AB ，AB=4，C 1B 1=3，∠ABB 1=600，求AC 1与平面BCC 1B 1所成角的大小． 三．二面角 1．已知A 1B 1C 1-ABC 是正三棱柱，D 是AC 中点． （1）证明AB 1∥平面DBC 1； （2）设AB 1⊥BC 1，求以BC 1为棱，DBC 1与CBC 1为面的二面角的大小． 2．ABCD 是直角梯形，∠ABC=900，SA ⊥面ABCD ，SA=AB=BC=1，AD=0.5． （1）求面SCD 与面SBA 所成的二面角的大小； （2）求SC 与面ABCD 所成的角． 3．已知A 1B 1C 1-ABC 是三棱柱，底面是正三角形，∠A 1AC=600，∠A 1AB=450，求二面角B —AA 1—C 的大小． B 1 C 1 A 1 B A C D B 1 C 1 A 1B A C B A D C S B 1 C 1 B C A 1 不四 s = —+ 爲Mu = =￡￡sin B 2 2 边形 不四 平边 行形 a. b. c. d —各边长險、爲rsi s -面积右、必一对角线 [H^hY^bh + cH 2 H, 曰-面枳 € _ a￡K abc % 4」戸（尹_&）〔戸 _&）（尹_亡） P-三边和之半 s-三角形囲积 艮-三角形外接圆半径 外 切 角 形 直 角 角 形 尸=匚石一刁 ■S _ 血 P V F P-三边和之半 2 -三角形面积 r -三角形内切圆半径 以=胪亠阱弘b -直角边 c = 3十戸? _斜边 1 , "尹占-面积 c -J/ ■n?十2&曰a'b^ -各边长 隅 角 0 ]073t a s - 面积 d -短轴D - 长轴匸-短 半轴 R -长半轴 扇 形 ISO* -°01745^ 亠二喫 2 360 半径 圆心角= 0.008727r^* 弓-面积 正 六 E 体 正 十 _____ L 面 体 正 多 边 形 (六个正方形 ) 口 -边 数 a - 一边之长 R -外接圆半径 r 内切圆半径 e-巒 财之 1D 心角 顶 用 官-面 积 D -周良 tzFhj u 〔教目） F=6a 2 棱顶点 12 3 丁 = / C 数 目） 稜腆点 30 20 正 立 方 体 截 头 直 锥 （十二个五甬形）爲 柱 卩二 20.6457^ r= 7.663 la 5 F = 6a 2 C L □ -边 长 d-对角线长 = 7^" = 1732^1 。=扌心1 +比） 尸=#餉+宀） + s i 十巧 衍“2 —两端周 围的长 ￡ L-S 2 —两端的 面积 $二gk 十邑+ J 远”叼） C* P -宜截断面周长 F = ^/ + 2s h - 高 V = sh 目-底面积 度。下图是个例子： 四、实验结果与分析（源程序及相关说明） 1)#include N维空间几何体质心的计算方法 摘要:本文主要是求一个图形或物体的质心坐标的问题,通过微积分方面的知识来求解,从平面推广到空间,问题也由易到难。首先提出质心或形心问题,然后给出重心的定义,再由具体的例子来求解相关问题。 关键字:质心重心坐标平面薄板二重积分三重积分 一.质心或形心问题: 这类问题的核心是静力矩的计算原理。 1.均匀线密度为M的曲线形体的静力矩与质心: 静力矩的微元关系为 , dMx yudl dMy xudl ==. 其中形如曲线L( (, y f x a x b =≤≤的形状体对x轴与y轴的静力矩分别 为( b a y f x S = ? , ( b y a M u f x =? 设曲线AB L 的质心坐标为( ,x y,则,, y x M M x y M M == 其 中( b a M u x d x u l == ? 为AB L 的质量,L为曲线弧长。若在式 y M x M = 与式 x M y M = 两端同乘以2π,则可得 到22( b a y xl f x S ππ == ? , 22( b a x yl f x S ππ == ? ,其中x S 与y S 分别表示曲线AB L 绕x轴与y轴旋转而成的旋转体的侧面积。 2.均匀密度平面薄板的静力矩与质心: 设f(x为 [],a b 上的连续非负函数,考虑形如区域 {} (,,0( D x y a x b y f x =≤≤≤≤ 的薄板质心,设M为其密度,利用微元法,小曲边梯形MNPQ的形心坐标为1 (,(, 2 y f y x y x x ≤≤+? ,当分割无限细化时,可当小曲边梯形MNPQ的质量视为集中于点 1 (,( 2 x f x 处的一个质点,将它对x轴与y轴分别取静力矩微元可有 1 (( 2 x dM u f x f x dx 计算几何算法概览 [ 2001-03-23 ] 怒火之袍出处:放飞技术网 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1.矢量的概念 2.矢量加减法 3.矢量叉积 4.折线段的拐向判断 5.判断点是否在线段上 6.判断两线段是否相交 7.判断线段和直线是否相交 8.判断矩形是否包含点 9.判断线段、折线、多边形是否在矩形中 10.判断矩形是否在矩形中 11.判断圆是否在矩形中 12.判断点是否在多边形中 13.判断线段是否在多边形内 14.判断折线是否在多边形内 15.判断多边形是否在多边形内 16.判断矩形是否在多边形内 17.判断圆是否在多边形内 18.判断点是否在圆内 19.判断线段、折线、矩形、多边形是否在圆内 20.判断圆是否在圆内 教案 教师姓名授课班级授课形式 授课日期年月日第周授课时数 授课章节名称立体几何的计算 教学目的计算立体几何中的有关角度和距离以及一些体积问题教学重点二面角和几何体的体积 教学难点二面角的计算 更新、补充、 删节内容 使用教具三角板 课外作业补充 课后体会注意立体图形与平面图形的转化 授课主要内容或板书设计 一、复习知识点 1． 有关角的计算 ⑴异面直线所成的角 a ． 定义：设,a b 是异面直线，过空间任一点o 引'',a a b b ，则'a 与'b 所成的锐角（或直角）叫异面直线,a b 所成的角。 b ．范围(0,90] c ． 求法：作平行线，将异面转化成相交 ⑵线面所成的角 a ． 定义：平面的一条斜线和它在平面上的射影所成的锐角，叫这条斜线和这个平面所成的角。 b ．范围：[0,90] c ． 求法：作垂线，找射影 ⑶二面角 a ． 定义：从一条直线出发的两个半平面所组成的图形叫二面角，其大小通过二面角的平面角来度量。 b ．二面角的平面角：以二面角的棱上任意一点为端点，在两个面内分别作垂直于棱的两条射线所成的角叫二面角的平面角。 c ． 范围：[0,]π d ．作法： 1定义法：过棱上任一点o 在两个半平面内分别引棱的两条垂线,OA OB ，则 AOB ∠为二面角的平面角 2三垂线定理法：过二面角的一个半平面内一点A ，作棱l 的垂线，垂足为O ， 作另一个面的垂线，垂足为B ，连接OB ，则AOB ∠为二面角的平面角。 β α O B A 3作棱的垂面法：过二面角内任意一点O ，分别向两个平面作垂线，垂足为,A B 则,AO BO 所确定的平面与棱l 交于P ，则APB ∠为二面角的平面角。 平面上有n个点，给定n个点的坐标，试找一个半径最小的圆，将n 个点全部包围，点可以在圆上。 1. 在点集中任取3点A,B,C。 2. 作一个包含A,B,C三点的最小圆,圆周可能通过这3点，也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端。 3. 在点集中找出距离第2步所建圆圆心最远的D点，若D点已在圆内或圆周上，则该圆即为所求的圆，算法结束.则，执行第4步。 4. 在A,B,C,D中选3个点,使由它们生成的一个包含这4个点的圆为最小，这3 点成为新的A,B,C，返回执行第2步。若在第4步生成的圆的圆周只通过A,B,C,D 中的两点，则圆周上的两点取成新的A 和B,从另两点中任取一点作为新的C。 程序设计题解上的解题报告： 对于一个给定的点集A，记MinCircle(A)为点集A的最小外接圆，显然，对于所有的点集情况A,MinCircle(A)都是存在且惟一的。需要特别说明的是，当A为空集时，MinCircle(A)为空集，当A={a}时，MinCircle(A)圆心坐标为a，半径为0；显然，MinCircle(A)可以有A 边界上最多三个点确定(当点集A中点的个数大于1时，有可能两个点确定了MinCircle(A))，也就是说存在着一个点集B，|B|<=3 且B 包含与A，有MinCircle(B)=MinCircle(A).所以，如果a不属于B，则MinCircle(A-{a})=MinCircle(A);如果MinCircle(A-{a})不等于 MinCircle(A),则a属于B。所以我们可以从一个空集R开始，不断的把题目中给定的点集中的点加入R，同时维护R的外接圆最小，这样就可以得到解决该题的算法。 不断添加圆，维护最小圆。如果添加的点i在圆内，不动，否则： 问题转化为求1~I的最小圆：求出1与I的最小圆，并且扫描j=2~I-1，维护（1）+（i）+(2~j)的最小圆，如果找到J不在最小圆内，问题转化为：求(1~J)+(i)的最小圆。求出I与J的最小圆，继续扫描K=1~j-1,找到第一个不在最小圆内的，求出I J K三者交点即可，此时找到了(1~j)+(i)的最小圆，可以回到上一步（三点定一圆，所以1~J-1一定都在求出的最小圆上）。 实际上利用了这么个定理： 若I不在1~I-1的最小圆上，则I在1~I的最小圆上。 若J不在(i)+(1~j-1)的最小圆上，则j在(i)+(1~J)的最小圆上。 证明可以考虑这么做：最小圆必定是可以通过不断放大半径，直到所有以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆。所以上述定理可以通过这个思想得到。 这个做法复杂度是O(n)的，当加入圆的顺序随机时，因为三点定一圆，所以不在圆内概率是3/i,求出期望可得是On. 计算几何算法概览 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 矢量加减法 矢量叉积 折线段的拐向判断 判断点是否在线段上 判断两线段是否相交 判断线段和直线是否相交 判断矩形是否包含点 判断线段、折线、多边形是否在矩形中 判断矩形是否在矩形中 判断圆是否在矩形中 判断点是否在多边形中 判断线段是否在多边形内 判断折线是否在多边形内 判断多边形是否在多边形内 判断矩形是否在多边形内 判断圆是否在多边形内 判断点是否在圆内 判断线段、折线、矩形、多边形是否在圆内判断圆是否在圆内 计算点到线段的最近点 计算点到折线、矩形、多边形的最近点 计算点到圆的最近距离及交点坐标 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 凸包的概念 凸包的求法 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为：P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 立体几何知识点整理（文科） 一．直线和平面的三种位置关系： 1. 线面平行 l 符号表示： 2. 线面相交 符号表示： 3. 线在面内 符号表示： 二．平行关系： 1.线线平行： 方法一：用线面平行实现。 m l m l l // // ? ? ? ? ? ? = ? ? β α β α 方法二：用面面平行实现。 m l m l// // ? ? ? ? ? ? = ? = ? β γ α γ β α 方法三：用线面垂直实现。 若α α⊥ ⊥m l,，则m l//。 方法四：用向量方法： 若向量和向量共线且l、m不重合，则m l//。 2.线面平行： 方法一：用线线平行实现。 α α α// // l l m m l ? ? ? ? ? ? ? ? 方法二：用面面平行实现。 α β β α // // l l ? ? ? ? ? 方法三：用平面法向量实现。 若为平面α的一个法向 量，⊥且α ? l,则 α // l。 3.面面平行： 方法一：用线线平行实现。 β α α β // ' ,' , ' // ' // ? ? ? ? ? ? ? ? ? ? 且相交 且相交 m l m l m m l l 方法二：用线面平行实现。 β α β α α // , // // ? ? ? ? ? ? ?且相交 m l m l 三．垂直关系： 1. 线面垂直： 方法一：用线线垂直实现。 α α ⊥ ? ? ? ? ? ? ? ? ? = ? ⊥ ⊥ l AB AC A AB AC AB l AC l , 方法二：用面面垂直实现。 l αββαβα⊥??? ? ?? ?⊥=?⊥l l m l m , 2. 面面垂直： 方法一：用线面垂直实现。 βαβα⊥?? ?? ?⊥l l 方法二：计算所成二面角为直角。 3. 线线垂直： 方法一：用线面垂直实现。 m l m l ⊥?? ?? ?⊥αα 方法二：三垂线定理及其逆定理。 PO l OA l PA l αα⊥? ? ⊥?⊥???? 方法三：用向量方法： 若向量和向量的数量积为0，则m l ⊥。 三．夹角问题。 (一) 异面直线所成的角： (1) 范围：]90,0(?? (2)求法： 方法一：定义法。 步骤1：平移，使它们相交，找到夹角。 步骤2：解三角形求出角。(常用到余弦定理) 余弦定理： ab c b a 2cos 2 22-+= θ (计算结果可能是其补角) 方法二：向量法。转化为向量的夹角 (计算结果可能是其补角)： = θcos (二) 线面角 (1)定义：直线l 上任取一点P （交点除外），作PO ⊥ α于O,连结AO ， 则AO 为斜线PA 在面α内的射影，PAO ∠(图中θ)为直线l 与面α所成的角。 (2)范围：]90,0[?? 当?=0θ时，α?l 或α//l 当?=90θ时，α⊥l (3)求法： 方法一：定义法。 步骤1：作出线面角，并证明。 步骤2：解三角形，求出线面角。 (三) 二面角及其平面角 (1)定义：在棱l 上取一点P ，两个半平面内分别作l 的垂线（射线）m 、n ，则射线m 和n 的夹角θ为二面角 α—l —β的平面角。 θ c b a GIS中的计算几何 GIS是一个图形系统，必然会涉及到几何学上理论应用，比如，图形的可视化，空间拓扑分析，GIS图形编辑等都需要借助几何。向量几何是用代数的方法来研究几何问题，首先，请大家翻一翻高等数学里有关向量的章节，熟悉一下几个重要的概念：向量、向量的模、向量的坐标表示、向量的加减运算、向量的点积、向量的叉积...下面我们将用这些基本概念来解答GIS中一些几何问题。 一，点和线的关系。 点是否在线段上，这样的判断在图形编辑，拓扑判断(比如，GPS跟踪判 断是否跑在线上)需要用到这样的判断。通常的想法是：先求线段的直线 方程，再判断点是否符合这条直线方程，如果符合，还要判断点是否在 线段所在的矩形区域(MBR)内，以排除延长线上的可能性，如果不符合， 则点不在线段上。这种思路是可行的，但效率不高，涉及到建立方程， 解方程。借助向量的叉积（也叫向量的向量积，结果还是向量，有方向 的）可以很容易的判断。设向量a=(Xa,Ya,Za) b=(Xb,Yb,Zb) 向量叉积 a X b如下： 二维向量叉积的模|a X b|=|a|*|b|*sinα=|Xa*Yb-Ya*Xb| （α是向量a,b之间的夹角），向量叉积模的几何意义是以向量a,b为邻边的平行四边 形的面积。可以推测：如果两向量共线，向量叉积模(所代表的平行四边 形的面积为零) 则|a X b|=|a|*|b|*sinα=|Xa*Yb-Ya*Xb|=0,否则不共线，叉 积的模为非零，根据这样条件可以很轻松的判断点和线的关系，避免了 建立方程和解方程的麻烦。 向量叉积的模|AB X AC|=0即可判断C点在AB所确定的直线上，再结合 C点是否在AB所在的MBR范围内，就可以最终确定C是否在AB线段 上。关于点和线段的其他关系，都可以通过叉积的求得，比如判断点在 线的哪一侧，右手法则，可以通过 a X b=(Xa*Yb-Ya*Xb)*k中的 （Xa*Yb-Ya*Xb）正负来判断。留给大家思考，很简单的，呵呵… 二，线和线的关系 判断两条线段是否相交，在很多拓扑判断和图形编辑(比如，线的打断来 构建拓扑，编辑线对象，叠置分析，面与面关系的判断等) 中都需要用到 线线相交的判断，如果两条线段相交，一条线段的两端点必然位于另一 条线段的两侧（不考虑退化情况，也就是一条线段的端点在另一条线段 上，这个很容易判断） 两向量的叉积a X b= (Xa*Yb-Ya*Xb)*k ，分别判断AB X AC的方向与 AB X AD的方向是否异号，再判断CD X CA 的方向与CD X CB的方向 是否异号即可判断两线段是否相交。 退化情况，一条线的端点在另一条线上，则AB X AC、 AB X AD 、CD X CA、CD X CB 是否存在有一个为零的，存在则表明肯定有一条线的端 点在另一个线上或者共用一个端点。详细区分留给大家思考。呵呵… 利用向量的方向还可以判断线段的转向，这个在道路导航中有所应用 立体几何平面公式大全 最早的几何学当属平面几何。平面几何就是研究平面上的直线和二次曲线(即圆锥曲线，就是椭圆、双曲线和抛物线)的几何结构和度量性质(面积、长度、角度)。为了计算体积和面积问题，人们实际上已经开始涉及微积分的最初概念。 名称符号周长C和面积S 1、长方形a和b-边长C=2(a+b)S=ab 2、正方形a—边长C=4aS=a2 3、三角形a,b,c-三边长;h-a边上的高;s-周长的一半;A,B,C-内角 其中s=(a+b+c)/2 S=ah/2=ab/2·sinC =[s(s-a)(s-b)(s-c)]1/2 =a2sinBsinC/(2sinA) 4、四边形d,D-对角线长;α-对角线夹角 S=dD/2·sinα 5、平行四边形a,b-边长;h-a边的高;α-两边夹角 S=ah=absinα 6、菱形a-边长;α-夹角;D-长对角线长;d-短对角线长 S=Dd/2=a2sinα 7、梯形a和b-上、下底长;h-高;m-中位线长 S=(a+b)h/2=mh 8、圆r-半径;d-直径; C=πd=2πrS=πr2=πd2/4 9、扇形r—扇形半径a—圆心角度数 C=2r+2πr×(a/360) S=πr2×(a/360) 10、弓形l-弧长;b-弦长;h-矢高;r-半径;α-圆心角的度数S=r2/2·(πα/180-sinα) =r2arccos[(r-h)/r]-(r-h)(2rh-h2)1/2 =παr2/360-b/2·[r2-(b/2)2]1/2 =r(l-b)/2+bh/2 ≈2bh/3 11、圆环R-外圆半径;r-内圆半径;D-外圆直径;d-内圆直径S=π(R2-r2)=π(D2-d2)/4 12、椭圆D-长轴;d-短轴;S=πDd/4 计算几何常用算法概览 本站原创：怒火之袍一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量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 )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量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 长方形 面积：长×宽 周长：（长+宽）*2 平行四边形 面积=底边*高/2 周长=（底+高）×2 三角形 面积S=√p(p-a)(p-b)(p-c), p=（a+b+c）/2,为三角形三边 周长c=a+b+c 梯形 面积=｛（上底+下底）×高｝÷2周长=四边之和 圆形 面积=πR2 周长=2πR （R为半径） 椭圆形 面积=A = PI * 半长轴长 * 半短轴长 周长= 4A * SQRT(1-E^SIN^T)的(0 - π/2)积分, 其中A为椭圆长轴,E为离心率精确计算要用到积分或无穷级数的求和 半圆形 周长=2R(丌+1) 面积=(丌R的平方)/2 正多边形 面积： 正多边形内角计算公式与半径无关 要已知正多边形边数为N 内角和=180(N-2) 半径为R 圆的内接三角形面积公式:(3倍根号3)除以4再乘以R方 外切三角形面积公式:3倍根号3 R方 外切正方形:4R方 内接正方形:2R方 五边形以上的就分割成等边三角形再算 内角和公式——（n-2）*180` 我们都知道已知A(x1,y1)、B(x2,y2)、C(x3,y3)三点的面积公式为 |x1 x2 x3| S(A,B,C) = |y1 y2 y3| * = [(x1-x3)*(y2-y3) - (x2-x3)*(y1-y3)]* |1 1 1 | (当三点为逆时针时为正，顺时针则为负的) 对多边形A1A2A3、、、An(顺或逆时针都可以)，设平面上有任意的一点P，则有：S(A1,A2,A3，、、、,An) = abs(S(P,A1,A2) + S(P,A2,A3)+、、、+S(P,An,A1)) 目录 ㈠点的基本运算 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 计算几何基础知识整理
立体几何中的向量公式
ACM经典算法及配套练习题
常见的几何体计算公式
立体几何与平面几何计算公式
GIS算法的计算几何基础
空间几何中的角和距离的计算
各种几何图形计算公式.
计算几何算法的实现
N维空间几何体质心的计算方法.
计算几何算法概览.
立体几何的计算
ACM 计算几何 最小圆覆盖算法
计算几何算法概览叉积
文科立体几何知识点、方法总结高三复习
GIS中的计算几何
立体几何平面公式大全
计算几何常用算法概览
各种几何图形面积和周长公式
计算几何常用函数
相关主题
文本预览