计算几何之凸包(一) {卷包裹算法}
{
半个寒假都在写凸包
这几篇文章整理一下
主要介绍二维凸包的求解算法
以及一个简单的应用
｝
================================================== ==================
一.凸集&凸包
(下文中所有的集合若不作特殊说明都是指欧氏空间上的集合)
凸集(Convex Set):任意两点的连线都在这个集合内的集合就是一个凸集.
A set in Euclidean space is convex set if it contains all the line segm ents connecting any pair of its points.
https://www.doczj.com/doc/b614654005.html,/Convex.html
凸包(Convex Hull):包含集合S的所有凸集的交集就是集合S的凸包.
The convex hull of a set of points S in N dimensions is the intersection of all convex sets containing S.
我们经常关注一个点集的凸包这也是计算几何学的一个基本问题
我们现在已经有成熟的算法可以求出平面点集的凸包和空间点集的凸包
甚至有的算法可以方便的求出任意维度欧氏空间内的一个点集的凸包
凸包有着优美而实用的性质我们可以利用凸包把一个杂乱的点集所包含的信息进行有效的概括梳理
================================================== ==================
二.平面点集的凸包的算法
(下文中所有凸包若不作特殊说明都是指平面点集的凸包)
有两种直观的理解凸包的方式
在木板上钉钉子用一个有弹性的橡皮筋去框住所有钉子
橡皮筋形成的图形就是这个钉子所构成的点集的凸包
还有一种理解我们用一根麻绳绑住一个外面的钉子然后拉着麻绳绕所有钉子一圈这个麻绳最后也构成了点集的凸包
其中第二种理解是我们一个经典算法卷包裹法(Gift Wrapping)的思路
卷包裹算法从一个必然在凸包上的点开始向着一个方向依次选择最外侧的点
当回到最初的点时所选出的点集就是所要求的凸包
这里还有两个问题不是很清楚:
1.怎么确定一个肯定在凸包上的点?
这个问题很好解决取一个最左边的也就是横坐标最小的点
如果有多个这样的点就取这些点里纵坐标最小的
这样可以很好的处理共线的情况
2.如何确定下一个点(即最外侧的点)?
我们需要利用向量的叉积来解决这个问题
-----------------------------------------------------------------------
向量的叉积(Cross Product)原本是三维空间中的问题在二维中也有巧妙的应用https://www.doczj.com/doc/b614654005.html,/CrossProduct.html
(下文中所有的叉积若不作特殊说明都是指二维中新定义的叉积
下文中所有的向量乘法若不作特殊说明都是指向量的叉积)
我们定义二维向量
1.叉积的一半是一个三角形的有向面积
这个公式可以避免面积计算的误差如果点是整点那么所有运算都是整数2.向量的叉积的符号代表着向量旋转的方向
向量的叉积是不满足交换律的
向量A乘以向量B 如果为正则为A逆时针旋转向B 否则为顺时针
当然这里A转向B的角总是考虑一个小于180度以内的角否则就会出错----------------------------------------------------------------------- 有了向量我们就可以选取一个最外侧的点了
比如现在我们卷包裹卷到J点我们要选取一个最外侧的点
当然比较红色的到角可以直接得到最外侧的点不过不方便
我们可以考虑那个蓝色的到角
利用向量我们可以比较哪个点"更外侧"
比如点K和点I 我们利用向量JK乘以向量JI得到一个数这个数应该是负数说明I比K更外侧
两个向量的比较具有传递性所以我们可以像N个数里取最大的数一样取出最外侧的
遍历所有点每个点都和现有最外侧的点比较得到新的最外侧的点
至此两个问题都得以解决我们可以写出满足一般要求的卷包裹算法了
不过还遗留有一个问题就是处理共线的问题
有时候我们需要凸包边上的点也考虑到有时候却需要去掉这些点
我们通常称在凸包顶点处的点为极点
如果我们只要求保留极点而去除在边上的点
我们只需在取外侧的点的时候碰到共线的点取最远的
相反如果我们要保留所有在边上的点我们只需要在共线的点中取最近的
这样整个卷包裹法终于完成了
给出完整的代码:
GiftWrapping
{$inline on}
const zero=1e-6; maxn=100000;
type point=record x,y:extended; end;
var p:array[1..maxn]of point;
ch:array[1..maxn]of longint;
temp,n,m,i,j,k:longint;
function sgn(x:extended):longint; inline;
begin
if abs(x) if x<0then sgn:=-1else sgn:=1; end; function cross(a,b,c:point):extended; inline; begin cross:=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); end; function dist(a,b:point):extended; inline; begin dist:=sqr(a.x-b.x)+sqr(a.y-b.y); end; function cmp(a,b,c:point):boolean; inline; var temp:longint; begin temp:=sgn(cross(a,b,c)); if temp<>0then exit(temp<0); {*B} cmp:=dist(a,b) end; begin assign(input,'Hull.in'); reset(input); assign(output,'Hull1.out'); rewrite(output); readln(n); for i:=1to n do begin readln(p[i].x,p[i].y); if (j=0)or(p[i].x (sgn(p[i].x-p[j].x)=0)and(p[i].y end; temp:=j; while true do begin k:=0; inc(m); ch[m]:=j; for i:=1to n do if (i<>j)and((k=0)or cmp(p[j],p[k],p[i])) then k:=i; if k=temp then break; j:=k; end; for i:=1to m do writeln(p[ch[i]].x:0:2,' ',p[ch[i]].y:0:2); close(input); close(output); end. *A Change Direction *B Remove Colinear Points 还有两点要补充说明一下: 1.卷包裹算法的复杂度是O(NH) N是全部的点数H是最终在凸包上的点数 所以卷包裹算法很适合凸包上的点很少的时候通常随机数据很快 但是构造出的凸包上的点很多的数据这个算法就会很慢 比如所有的点都在一个圆周上 2.卷包裹算法输出的点是有序的 这也是对二维凸包算法的一个基本要求 通常只有保证有序才能进行进一步的计算 通过改变CMP函数可以改变上文中提到的共线(取/不取)以及这里的序(顺时针/逆时针)的问题================================================== ================== 三.凸包的面积和周长 凸包的一个简单算法介绍完了 来看一个具体的问题Poj 1113 https://www.doczj.com/doc/b614654005.html,/problem?id=1113 问题是求到一个简单多边形距离最少为L的点的轨迹的周长 我们可以先求凸包然后得到计算公式 实际上圆的部分可以拼接起来变成一个整圆 这样就好算多了注意把共线的都去掉不然误差会很大的 代码就不贴了很简单的 下一篇介绍更快速的平面凸包算法 Graham Scan 和QuickHull 强烈推荐QuickHull BOB HAN 原创转载请注明出处https://www.doczj.com/doc/b614654005.html,/Booble/ 标签: 计算几何, 多边形, 凸包, 卷包裹算法, 向量 计算几何基础知识整理 一、序言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、本基础目录 本文整理的计算几何基本概念和常用算法包括如下内容： 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 小学数学图形计算公式 （C ：周长 S ：面积 a ：边长、长 、底、上底、棱长 b: 宽 、下底 h: 高 d ：直径 r ：半径 V:体积 ） 1、长方形周长=(长+宽)×2 C=2(a+b) 长方形面积=长×宽 S=ab 2、正方形周长＝边长×4 C = 4a 正方形面积=边长×边长 S = a×a = a 2 3、平行四边形面积=底×高 s=ah 4、三角形面积=底×高÷2 s=ah÷2 三角形高=面积 ×2÷底 h = 2s ÷a 三角形底=面积 ×2÷高 5、梯形面积=(上底+下底)×高÷2 s=(a+b)× h÷2 6、圆的周长=直径×圆周率=2×圆周率×半径 C=лd=2лr d=C π r=C 2π 圆的面积=半径×半径×圆周率 S = πr 2 环形的面积=外圆的面积-内圆的面积 S 环=π（R 2-r 2） 7、长方体的棱长总和 = 长×4 + 宽×4 + 高×4 =（长 + 宽 + 高）×4 长方体表面积=(长×宽+长×高+宽×高)×2 S = 2( ab + ah + bh ) 长方体体积=长×宽×高 = 底面积×高 V=abh = sh 8、正方体的棱长总和=棱长×12 正方体表面积=棱长×棱长×6 S 表 = a×a×6 = 6a 2 正方体体积=棱长×棱长×棱长=底面积×高 V = a×a×a = a 3 = sh 9、圆柱的侧面积=底面周长×高 s 侧=ch=πdh=2πrh 圆柱表面积=侧面积+底面积×2 s 表=s 侧+s 底×2 圆柱体积=底面积×高 V 柱 = sh =πr 2h 10、圆锥体体积=底面积×高×13 V 锥 = 13 sh = 1 3 πr 2h 小学数学图形计算公式 （C ：周长 S ：面积 a ：边长、长 、底、上底、棱长 b: 宽 、下底 h: 高 d ：直径 r ：半径 V:体积 ） 1、长方形周长=(长+宽)×2 C=2(a+b) 长方形面积=长×宽 S=ab 2、正方形周长＝边长×4 C = 4a 正方形面积=边长×边长 S = a×a = a 2 3、平行四边形面积=底×高 s=ah 4、三角形面积=底×高÷2 s=ah÷2 三角形高=面积 ×2÷底 h = 2s ÷a 三角形底=面积 ×2÷高 5、梯形面积=(上底+下底)×高÷2 s=(a+b)× h÷2 6、圆的周长=直径×圆周率=2×圆周率×半径 C=лd=2лr d=C π r=C 2π 圆的面积=半径×半径×圆周率 S = πr 2 环形的面积=外圆的面积-内圆的面积 S 环=π（R 2-r 2） 7、长方体的棱长总和 = 长×4 + 宽×4 + 高×4 =（长 + 宽 + 高）×4 长方体表面积=(长×宽+长×高+宽×高)×2 S = 2( ab + ah + bh ) 长方体体积=长×宽×高 = 底面积×高 V=abh = sh 8、正方体的棱长总和=棱长×12 正方体表面积=棱长×棱长×6 S 表 = a×a×6 = 6a 2 正方体体积=棱长×棱长×棱长=底面积×高 V = a×a×a = a 3 = sh 9、圆柱的侧面积=底面周长×高 s 侧=ch=πdh=2πrh 圆柱表面积=侧面积+底面积×2 s 表=s 侧+s 底×2 圆柱体积=底面积×高 V 柱 = sh =πr 2h 10、圆锥体体积=底面积×高×13 V 锥 = 13 sh = 1 3 πr 2h 中小学教师信息技术考试理论试题 一选择题（40分，每一题1分） 1.下面选项是对信息的实质的理解和说明,其中错误的选项是________. A. 信息就是计算机的处理对象 B. 信息就是关于事物运动的状态和规律的知识 C. 信息就是信息,既不是物质,也不是能量 D. 信息就是人类同外部世界进行交换的内容的名称 2. 信息技术在教学中常用作获取学习资源的工具,人们常说,"因特网是知识的海洋". 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)组合数学: 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)#include 几何体计算公式大全 长方形的面积=长×宽 长方形的周长=(长+宽)×2 正方形的周长=边长×4 正方形的面积=边长×边长 三角形的面积=底×高÷2 平行四边形的面积=底×高 梯形的面积=(上底+下底)×高÷2 直径=半径×2 半径=直径÷2 圆的周长=圆周率×直径= 圆周率×半径×2 圆的面积=圆周率×半径×半径 长方体的表面积= (长×宽+长×高＋宽×高)×2 长方体的体积=长×宽×高 正方体的表面积=棱长×棱长×6 正方体的体积=棱长×棱长×棱长 圆柱的侧面积=底面圆的周长×高 圆柱的表面积=上下底面面积+侧面积 圆柱的体积=底面积×高 圆锥的体积=底面积×高÷3 长方体(正方体、圆柱体) 的体积=底面积×高平面图形名称符号周长C与面积S 正方形a—边长C＝4a S＝a2 长方形a与b－边长C＝2(a+b) S＝ab 三角形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) 四边形d,D－对角线长 α－对角线夹角S＝dD/2·sinα 平行四边形a,b－边长 h－a边的高 α－两边夹角S＝ah ＝absinα 菱形a－边长 α－夹角 D－长对角线长 d－短对角线长S＝Dd/2 ＝a2sinα 梯形a与b－上、下底长 h－高 m－中位线长S＝(a+b)h/2 ＝mh 圆r－半径 d－直径C＝πd＝2πr S＝πr2 ＝πd2/4 扇形r—扇形半径 a—圆心角度数 C＝2r＋2πr×(a/360) S＝πr2×(a/360) 弓形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 圆环R－外圆半径 r－内圆半径 D－外圆直径 d－内圆直径 S＝π(R2-r2) ＝π(D2-d2)/4 椭圆D－长轴 d－短轴S＝πDd/4 立方图形 名称符号面积S与体积V 正方体a－边长S＝6a2 V＝a3 长方体a－长 b－宽 c－高S＝2(ab+ac+bc) V＝abc 棱柱S－底面积 h－高V＝Sh 棱锥S－底面积 h－高V＝Sh/3 棱台S1与S2－上、下底面积 h－高V＝h[S1+S2+(S1S1)1/2]/3 拟柱体S1－上底面积 S2－下底面积 S0－中截面积 计算几何算法概览 [ 2001-03-23 ] 怒火之袍出处:放飞技术网 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1.矢量的概念 2.矢量加减法 3.矢量叉积 4.折线段的拐向判断 5.判断点是否在线段上 6.判断两线段是否相交 7.判断线段和直线是否相交 8.判断矩形是否包含点 9.判断线段、折线、多边形是否在矩形中 10.判断矩形是否在矩形中 11.判断圆是否在矩形中 12.判断点是否在多边形中 13.判断线段是否在多边形内 14.判断折线是否在多边形内 15.判断多边形是否在多边形内 16.判断矩形是否在多边形内 17.判断圆是否在多边形内 18.判断点是否在圆内 19.判断线段、折线、矩形、多边形是否在圆内 20.判断圆是否在圆内 小学几何图形基本概念及计算公式 轴对称图形：如果一个图形沿着一条直线对折,直线左右的两部分能够完全重合,那么这个图形就叫做轴对称图形.这条直线叫做对称轴.长方形（2条对称轴）,正方形（4条对称轴）,等腰三角形（1条）,等边三角形（3条）,等腰直角三角形（1条）,等腰梯形（1条）,圆（无数条）. 点：线和线相交于点. 直线：某点在空间中或平面上沿着一定方向和相反方向运动,所画成的图形,叫做直线.直线是向相反方向无限延伸的,所以它没有端点,不可以度量. （可以用表示直线上任意两点的大写字母来记：直线AB,也可以用一个小写字母来表示：直线a) 射线：由一个定点出发,向沿着一定的方向运动的点的轨迹,叫做射线.这个定点叫做射线的端点,这个端点也叫原点.射线只有一个端点,可以向一端无限延长，不可以度量.（射线可以用表示他端点,和射线上任意一点的两个大写字母表示：射线OA） 线段：直线上任意两点间的部分,叫做线段.这两点叫做线段的端点,线段有长度,可以度量.（线段可以用两个端点的大写字母表示：线段AB,也可以用一个小写字母表示；线段a）线段的性质：在连接两点的所有线中,线段最短. 角：从一点引出两条射线所组成的图形,叫做角.这两条射线的公共端点,叫做角的顶点.组成角的两条射线,叫做角的边. 角的大小与夹角两边的长短无关. 角的分类： 直角：90度的角叫做直角 平角：一条射线由原来的位置,绕它的端点按逆时针方向旋转,到所成的角的终边和始边成一直为止,这时所成的角叫做平角.或者角的两边的方向相反,且同在一条直线上时的角叫做平角,平角是180度. 锐角：小于90度的角叫做锐角 钝角：大于90度的角叫做钝角 垂直与平行：在同一个平面内不相交的两条直线叫做平行线,也可以说这两条直线互相平行. 如果两条直线相交成 平面上有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. 一。几何图形及计算公式 平面几何图形和立体几何图形。包括面积体积表面积等等公式三角形 面积 1）S=1/2底*高 2）S=1/2*意两边的乘积*这两边夹角的正弦值（已知两边及其夹角的大小） 3）S=根号下p(p-a)(p-b)(p-c)---------------------(海伦公式：已知三边的长，p=周长/2） 分类：钝角直角锐角 特例:等边三角形：S=四分之一倍根号三*边长的平方 等腰直角三角形：S=1/2倍直角边的平方 注：顶角为36°的等腰三角形也很重要 性质：正弦定理： sinA/a=sinB/b=sinc/C 余弦定理： a^2=b^2+c^2-2bc cosA b^2=a^2+c^2-2ac cosB c^2=a^2+b^2-2ab cosA 三角形2条边向加大于第三边. 三角形内角和=180度 四边形 梯形：S=（上底+下底）*高/2 平行四边形：S=底*高 长方形：S=长*宽 正方形：S=边长*边长 内角和为360° 多边形：内角和为（n-2)*180° 面积：具体问题具体分析（可用切割法划为简单图形计算） 圆：s=πr^2 周长=2πr 性质：园内以直径为一边的圆周三角形为直角三角形，且直径所对的角为直角相同弧长所对的圆心角为其圆周角的两倍 弦切角=圆周角=1/2圆心角 过圆内一点最短的弦与过该点的直径垂直 立体 棱柱：V=底面积*高（四棱柱可切为6个三棱锥） 椎体：V=C底面积*高（C为一常数，三棱柱时为1/3;正三棱锥很重要） 球：S=4πr^2 V=4/3倍πr^3 提问人的追问 2010-01-03 16:18 很清晰。但好像还不是很完整，比如说扇形的，还有椎体，台体。还有像问一下，椎体哪里的c为一常数是怎么看的 回答人的补充 2010-01-03 16:36 嗯~2扇形：S=顶角/360°*（πr^2） 弓形：S=相应扇形的面积-相应三角形的面积 椎体体积的计算时始终记住底面积乘以高然后根据其特点确定C （因为底面积乘以高为四棱柱的体积所以只要确定几个这样的椎体构成一个四棱柱则 C=1/n)上面那个地方写错了应该是1/6 更为复杂的立体一定要用切割法或是互补法 几年没碰过了忘了好多还有什么遗漏的告诉我我再看一下能不能记起 提问人的追问 2010-01-03 16:43 弧长公式。用不同的公式表示 回答人的补充 2010-01-03 16:54 因弧度数=弧长/半径 所以1）弧长=弧度*半径 又 2）弧长=（圆心角/360°）*周长 3）在物理方面弧长=角速度*半径*时间 提问人的追问 2010-01-03 17:18 弦切角=圆周角=1/2圆心角可以帮我画个图吗 回答人的补充 2010-01-03 17:34 计算几何算法概览 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 矢量加减法 矢量叉积 折线段的拐向判断 判断点是否在线段上 判断两线段是否相交 判断线段和直线是否相交 判断矩形是否包含点 判断线段、折线、多边形是否在矩形中 判断矩形是否在矩形中 判断圆是否在矩形中 判断点是否在多边形中 判断线段是否在多边形内 判断折线是否在多边形内 判断多边形是否在多边形内 判断矩形是否在多边形内 判断圆是否在多边形内 判断点是否在圆内 判断线段、折线、矩形、多边形是否在圆内判断圆是否在圆内 计算点到线段的最近点 计算点到折线、矩形、多边形的最近点 计算点到圆的最近距离及交点坐标 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 凸包的概念 凸包的求法 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为：P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 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 是否存在有一个为零的，存在则表明肯定有一条线的端 点在另一个线上或者共用一个端点。详细区分留给大家思考。呵呵… 利用向量的方向还可以判断线段的转向，这个在道路导航中有所应用 直齿圆柱齿轮的基本参数和几何尺寸计算 课题：直齿圆柱齿轮的基本参数和几何尺寸计算（一） 教学目的和要求：使学生掌握直齿圆柱齿轮几何要素的名称的代号，基本参数 重点：基本参数 难点：基本参数 教学方法：讲解 计划课时：2课时 教学过程： 复习： 渐开线齿廓 新授： 一、直齿圆柱齿轮几何要素的名称的代号 1、端平面 在圆柱齿轮上，垂直于齿轮轴线的表面 2、齿顶圆柱面、齿顶面。 圆柱齿轮的齿顶曲面称为齿顶圆柱面。 d 在圆柱齿轮上，其齿顶圆柱面与端平面的交线称为齿顶圆。a 3、齿根圆柱面、齿根面。 圆柱齿轮的齿根曲面称为齿根圆柱面。 d 在圆柱齿轮上，其齿根圆柱面与端平面的交线称为齿根圆。f 4、分度圆柱面、分度圆。 圆柱齿轮的分度曲面称为分度圆柱面。 在圆柱齿轮上，其分度圆柱面与端平面的交线称为分度圆。d 5、齿宽。 齿轮的有齿的部分沿分度圆柱面的直母线方向量度的宽度称为齿宽。b 6、端面齿距。 p 7、端面齿厚。 s 8、端面齿槽宽。 e 9、齿顶高。 h a 10、齿根高。 h f 二、直齿圆柱齿轮的基本参数 1、齿数z 一个齿轮的轮齿总数叫做齿数 2、模数m 齿距除以圆周率π所得到的商称为模数。单位为mm。 模数是齿轮几何尺寸计算中最基本的一个参数。 模数的大小反映了齿距的大小，也就是反映了轮齿的大小。 3、齿形角 对于渐开线齿轮，通常所说的齿形角是指分度圆上的齿形角。 α =20 ? 4、齿顶高系数*a h 齿顶高与模数之比值称为齿顶高系数。 m h h a a *= 标准直齿圆柱齿轮的齿顶高系数1*=a h 5、顶隙系数*c 一齿轮的齿顶与另一齿轮的槽底间的径向间隙，称为顶隙。 m c c *= 所以： m c h c h h a a f )(**+=+= 标准直齿圆柱齿轮的顶隙系数25.0*=c 。 小结：基本参数 作业：P71 课题：直齿圆柱齿轮的基本参数和几何尺寸计算（二） 教学目的和要求：标准直齿圆柱齿轮几何尺寸的计算 重点：标准直齿圆柱齿轮几何尺寸的计算 难点：标准直齿圆柱齿轮几何尺寸的计算 教学方法：讲解 计划课时：2课时 三、标准直齿圆柱齿轮几何尺寸的计算 采用标准模数m ，齿形角?=20α，齿顶高系数1* =a h ，顶隙系数25.0*=c ，端面齿厚s 等于端面齿槽宽e 的渐开线直齿圆柱齿轮称为标准直齿圆柱齿轮，简称标准直齿轮。 标准直齿轮几何要素的名称、代号、定义和计算公式 参见教材P48表3－5 例1：一对相啮合的标准直齿圆柱齿轮，已知齿数1224,40z z ==，模数5m mm =。试计算其分度圆直径，齿顶圆直径，齿根圆直径，基圆直径，齿距，齿厚，齿顶高，齿根高和中心距。 解：略（详细板书） 例2：已知一标准直齿圆柱齿轮的齿数36z =，顶圆直径304a d mm =。试计算其分度圆直径，根圆直径，齿距以及齿高。 例3：已知一标准直齿圆柱齿轮副，其传动比3i =，主动齿轮转速1750/min n r =，中心距240a mm =，模数5m mm =。试求从动轮转速以及两齿轮齿数和。 练习1：已知一标准直齿圆柱齿轮的齿数42z =，齿顶圆直径264a d mm =。试确定其分度 计算几何常用算法概览 本站原创：怒火之袍一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(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共线，但可能同向也可能反向。 目录 ㈠点的基本运算 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 渐开线标准直齿圆柱齿轮的主要参数及几何尺寸计算 12.3.1 齿轮各部分名称及符号 此主题相关图片如下： 此主题相关图片如下： 此主题相关图片如下： 此主题相关图片如下：554554.jpg 12.3.2 渐开线标准直齿圆柱齿轮的基本参数及几何尺寸计算 1 模数 齿轮圆周上轮齿的数目称为齿数，用z表示。根据齿距的定义知 此主题相关图片如下： 2 压力角 此主题相关图片如下： 此主题相关图片如下： 3 齿数 4 齿顶高系数 h a =h a *m （h a *=1） 5 顶隙系数 c=c*m (c*=0.25) h f =(h a *+c*)m 全齿高 h=h a +h f =(2h a *+c*)m 此主题相关图片如下： 标准齿轮是指模数、压力角、齿顶高系数和顶隙系数均为标准值，且分度圆上的齿厚等于齿槽宽的齿轮。 表12-2 标准直齿圆柱齿轮的几何尺寸计算公式 此主题相关图片如下： 4. 内齿轮与齿条 图示为一内齿圆柱齿轮，内齿轮的轮齿是分布在空心圆柱体的内表面上。与外齿轮相比有下列几个不同点： 1）内齿轮的齿厚相当于外齿轮的齿槽宽，内齿轮的齿槽宽相当于外齿轮的齿厚。 2）内齿轮的齿顶圆在它的分度圆之内，齿根圆在它的分度圆以外。 图示为一齿条，它可以看作齿轮的一种特殊型式。与齿轮相比有下列两个主要特点： 1）由于齿条的齿廓是直线，所以齿廓上各点的法线是平行的；传动时齿条是直线移动的，故各点的速度大小和方向均相同；齿条齿廓上各点的压力角也都相同，等于齿廓的倾斜角。 2）与分度线相平行的各直线上的齿距都相等。 此主题相关图片如下： 齿轮基本知识 1、 齿顶圆d a ：由齿顶所确定的圆。 2、 齿槽：相临两齿之间的空间。 3、 齿根圆d f ：齿槽底部所确定的圆。 4、 分度圆d ：齿轮某一圆周上的比值π k p 规定为标准值，并使该圆上的压力角也为标准值，这个圆为分度圆。 5、 模数m ：分度圆上齿距P 对π的比值。m=π p 6、 齿顶：在齿轮上介于齿顶圆和分度圆之间的部分。 7、 齿根：介于齿根圆和分度圆之间的部分。 8、 全齿高h ：齿顶圆与齿根圆之间齿轮的径向高度。 9、渐开线圆柱齿轮基准齿形及齿形参数 ⑴ 齿形角α：α=20° ⑵ 齿顶高h a ：h a =m ，齿顶高系数h a *=1 ⑶ 工作齿高h ′：h ′=2m ⑷ 齿距P ：P=πm ⑸ 径向间隙c ：c=0.25m ，径向间隙系数c *=0.25 ⑹ 齿根圆半径ρf ：0.38m 齿轮几何尺寸计算 一、 斜齿轮几何尺寸计算 1、法向齿距P n ：P n = P t cos β 式中：P t —端面齿距 β—螺旋角，8°～20° 2、法向模数m n ：m n = m t cos β 式中：m t —端面模数 3、端面压力角αt ：αt =arctg β αcos n tg ，αn 为标准值20° 4、分度圆直径：d 1= m t Z 1=βcos 1Z m n ，d 2= m t Z 2=β cos 2Z m n 5、齿顶高h a ：h a =m n 6、齿根高h f ：h f =1.25m n 7、齿顶间隙c ：c=h f -h a =0.25m n 8、中心距a ：a= 221d d +=2)(21Z Z m t +=β cos 2) (21Z Z m n + 二、 圆锥齿轮几何尺寸计算 1、 模数m ：以大端模数为标准 2、 传动比i ：i= 1 2 Z Z =tg δ2=ctg δ1，单级i ＜6～7 3、 分度圆锥角：δ2=arctg 1 2 Z Z ，δ1=90°-δ2 4、 分度圆直径：d 1=mZ 1，d 2=mZ 2 5、 齿顶高：h a =m 6、 齿根高：h f =1.2m 算法系列之九：计算几何与图形学有关的几种常用算法（一） 分类：算法系列2011-12-18 23:13 8182人阅读评论(41) 收藏举报 我的专业是计算机辅助设计（CAD），算是一半机械一半软件，《计算机图形学》是必修课，也是我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍，这种重复劳动虽然意义不大，但是收获很多，特别是丢弃了多年的数学又重新回到了脑袋中，算是最大的收获吧。尽管已经毕业多年了，但是每次回顾这些算法的代码，都觉得内心十分澎湃，如果换成现在的我，恐怕再也不会有动力去做这些事情了。 在学习《计算机图形学》之前，总觉得很多东西高深莫测，但实际掌握了之后，却发现其中了无神秘可言，就如同被原始人像神一样崇拜的火却被现代人叼在嘴上玩弄一样的感觉。图形学的基础之一就是计算几何，但是没有理论数学那么高深莫测，它很有实践性，有时候甚至可以简单到匪夷所思。计算几何是随着计算机和CAD的应用而诞生的一门新兴学科，在国外被称为“计算机辅助几何设计（Computer Aided Geometric Design，CAGD）”。“算法系列”接下来的几篇文章就会介绍一些图形学中常见的计算几何算法（顺便晒晒我的旧代码），都是一些图形学中的基础算法，需要一些图形学的知识和数学知识，但是都不难。不信？那就来看看到底有多难。 本文是第一篇，主要是一些图形学常用的计算几何方法，涉及到向量、点线关系以及点与多边形关系求解等数学知识，还有一些平面几何的基本原理。事先声明一下，文中涉及的算法实现都是着眼于解释原理以及揭示算法实质的目的，在算法效率和可读性二者的考量上，更注重可读性，有时候为了提高可读性会刻意采取“效率不高”的代码形式，实际工程中使用的代码肯定更紧凑更高效，但是算法原理都是一样的，请读者们对此有正确的认识。 一、判断点是否在矩形内 计算机图形学和数学到底有什么关系？我们先来看几个例子，增加一些感性认识。首先是判断一个点是否在矩形内的算法，这是一个很简单的算法，但是计算几何基础知识整理
最新几何图形计算公式汇总
ACM经典算法及配套练习题
GIS算法的计算几何基础
计算几何算法的实现
几何计算公式大全
计算几何算法概览.
小学几何图形基本概念及计算公式
ACM 计算几何 最小圆覆盖算法
几何图形及计算公式
计算几何算法概览叉积
GIS中的计算几何
直齿圆柱齿轮的基本参数和几何尺寸计算教案
计算几何常用算法概览
计算几何常用函数
渐开线标准直齿圆柱齿轮的主要参数及几何尺寸计算
齿轮几何尺寸计算[1]
计算几何与图形学有关的几种常用算法
相关主题
文本预览