计算几何学

tswrshang

贡献于2013-02-26

字数:0 关键词:

第 1111 章 计算几何学 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直 观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为计算 机科学的一个分支,计算几何主要研究解决几何问题的算法。在现代工程和数学领域,计 算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的 应用。 11.1 判断点是否在多边形中 判断点 P 是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点 P 为 端点,向左方作射线 L,由于多边形是有界的,所以射线 L 的左端一定在多边形外,考虑 沿着 L 从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边 形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当 L 和多边形的 交点数目 C 是奇数的时候,P 在多边形内,是偶数的话 P 在多边形外。 但是有些特殊情况要加以考虑。如下图 11.1(a)( b)( c)( d)所示。在图 11.1(a) 中,L 和多边形的顶点相交,这时候交点只能计算一个;在图 11.1(b)中,L 和多边形顶 点的交点不应被计算;在图 11.1(c)和(d)中,L 和多边形的一条边重合,这条边应该 被忽略不计。如果 L 和多边形的一条边重合,这条边应该被忽略不计。 ·151· 第 11 章 计算几何学 图 A 图 C 图 B 图 D 图 11.1 为了统一起见,我们在计算射线 L 和多边形的交点的时候,1。对于多边形的水平边 不作考虑;2。对于多边形的顶点和 L 相交的情况,如果该顶点是其所属的边上纵坐标较 大的顶点,则计数,否则忽略;3。对于 P 在多边形边上的情形,直接可判断 P 属于多边 形。由此得出算法的伪代码如下: count=0; 以 P 为端点,作从右向左的射线 L; for(多边形的每条边 s){ if(P 在边 s 上){ return true; } if(s 不是水平的){ if(s 的一个端点在 L 上){ if(该端点是 s 两端点中纵坐标较大的端点){ count++; }else if(s 和 L 相交){ count++; if(count%2==1){ return true; }else{ return false; } } } } } 判断点是否在多边形中的这个算法的时间复杂度为 O(n)。 11.2 判断线段是否在多边形内: 线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能 为凹,所以这不能成为判断的充分条件。如果线段和多边形的某条边内交(两线段内交是 ·152· ACM 程序设计培训教程 指两线段相交且交点不在两线段的端点),因为多边形的边的左右两侧分属多边形内外不同 部分,所以线段一定会有一部分在多边形外(见图 11.2A)。于是我们得到线段在多边形内 的第二个必要条件:线段和多边形的所有边都不内交。 线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个 顶点和线段相交,还必须判断两相交交点之间的线段是否包含于多边形内部(反例见图11.2B)。 图 A 图 B 图 11.2 因此我们可以先求出所有和线段相交的多边形的顶点,然后按照 X-Y 坐标排序(X 坐 标小的排在前面,对于 X 坐标相同的点,Y 坐标小的排在前面,这种排序准则也是为了保 证水平和垂直情况的判断正确),这样相邻的两个点就是在线段上相邻的两交点,如果任意 相邻两点的中点也在多边形内,则该线段一定在多边形内。 在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交, 倘若线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都 不内交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在 线段上就可以了。 得出算法如下: if(线端 PQ 的端点不都在多边形内){ return false; } 点集 pointSet 初始化为空; for(多边形的每条边 s){ if(线段的某个端点在 s 上){ 将该端点加入 pointSet; }else if(s 的某个端点在线段 PQ 上){ 将该端点加入 pointSet; }else if(s 和线段 PQ 相交){ // 这时候已经可以肯定是内交了 return false; } } 将 pointSet 中的点按照 X-Y 坐标排序; for(pointSet 中每两个相邻点 pointSet[i] , pointSet[ i+1]){ if(pointSet[i] , pointSet[ i+1] 的中点不在多边形中){ return false; } } return true; ·153· 第 11 章 计算几何学 这个过程中的排序因为交点数目肯定远小于多边形的顶点数目 n,所以最多是常数级 的复杂度,几乎可以忽略不计。因此算法的时间复杂度也是 O(n)。 11.3 计算几何典型算法 计算几何不同于其他算法,一般很难在没有见过的题目中很快找到规律,所以,知道 一些计算几何的典型题目不但可以增加对知识的理解,同时也是比赛时加快此类题目解题 速度的必经阶段。 11.3.1 〖案例 1〗计算周长问题 计算组合图形的轮廓线长度,即周长。给定若干个矩形,这些矩形的边平行于 x,y 轴。矩形之间可能相互重叠,也可能相互分离,要求计算这些组合图形的周长。 输入文件 perimeter.in 中,输入文件的第一行是矩形的数目 n;接下来的 n 行每行为四 个整数 x1,y1,x2,y2,分别表示一个矩形的左下角 x,y 坐标,右上角 x,y 坐标,四个 整数之间用空格隔开。 Sample input 7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16 输出文件 perimeter.out 中。输出文件只包含一个整数,即根据对应的输入数据计算出 的周长。 Sample output 228 限制条件 0< n<5000, 其中 n 是矩形的数目;所有的坐标在〔-10000,10000〕范围内。 一、降维思想 将高维问题转化为低维思想。 一维情况:在数轴上有 n 条线段 L1,L2,…Ln。其中 Li=〔ai,bi〕。计算线段并的 长度。 算法 1: 将 Li 的端点坐标从小到大排序,存入数组 x〔1..2n〕中; ·154· ACM 程序设计培训教程 x[0]=x[1]; length=0; c=0; for(i=1;i<=2n;i++){ if(c!=0){ length+=x[i]-x[i-1]; } if(x[i]是左端点){ c++; }else{ c--; } } 算法 2 1)对矩形的竖直边按 x 坐标从小到大进行排序,结果存入线性表 L[1..2n]中; 2) perimeter=0; old_M=0; old_Seg=0; L[0]=L[1]; 线性表 Y 初始化为空; 3) for(i=1; i<=2n; i++){ 4) if(L[i]是左边界){ 5) 将 L[i]的两个端点插入线性表 Y 中,并保持 Y 中元素的递增顺序; 6) }else{ 7) 将 L[i]的两个端点从线性表 Y 中删除 8) } 9) y[0]=y[1]; c=0; M=0; Seg=0; //Seg 记录线段 10) for(j=1; j<=Y.Length(); j++){ 11) if(C!=0)M+=y[j]-y[j-1]; 12) if(y[j]是矩形竖直边的下端点)c++ 13) else c--; 14) if(c=0) seg++; 15) } 16) perimeter+=2*old_Seg*(L[i]的横坐标- L[i-1]的横坐标)+|M-old_M|; 17) old_Seg=Seg; old_M=M; 18)} 11.3.2 〖案例 2〗正方形问题 一、问题描述 在直角坐标平面中,其边与坐标轴平行,顶点坐标均为正整数,所有正方形互不相接 或重叠。 定义:如果一个正方形的一条边上存在两个不同点 A 和 B 与坐标原点 O 组成的三角 形⊿OAB 与其它的正方形没有公共点,则它是一个从原点 O 可以看到的正方形。 你的任务:计算在给定的 N 个正方形中有多少个是从原点 O 可以看到的正方形。 输入数据文件 SQUARES.IN 第一行为正整数 N,1≦N ≦10000; 下面 N 行每行用三个整数 X、Y、L 描述一个正方形,X、Y 是正方形的左下角顶点坐 ·155· 第 11 章 计算几何学 标,L 是其边长,其中 1 ≦X,Y,L ≦10000。 输出数据文件 SQUARES.OUT 只有一行,记录从原点 O 可以看到的正方形的个数。 方法 1: (1)保存每个正方形的视角范围。 (2)通过遍及所有正方形是否被其他正方形的视角范围所覆盖。复杂度为 o(n2) 方法 2: (1)从文件中读入正方形的数据到数组中。 (2)使用快速排序对正方形数组进行排序。(由近到远)。 (3)初始化被遮角链表为空。可视正方形的个数初始化为正方形的总数。 (4)取出一个正方形数据。计算它的可视。右下角顶点、左上角顶点同原点的夹角称 为始边和终边。 (5)考虑始边是否在某个被遮角 I 内,或在第 I 个被遮角的左侧空挡中。 (6)考虑终边是否在某个被遮角 J 内,或在第 J 个被遮角的右侧空挡中。 (7)将从 I 到 J 的被遮角全部合并到新建的被遮角中去。若在被遮角内,则相应修改 边界。 (8)若 I=J,则这个正方形不可视,计数器减一。 (9)转向 4),直到最后一个正方形。 (10)输出结果。 问题: 1)如何判断正方形相对原点的远近? 2)如何判断正方形是否可视? 3)如何修改总被遮范围? 总的复杂度为 O(n *log2(n)). 为避免不必要的误差,可以使用分数运算来比较角度的大小,而不是真正地计算斜率。 11.3.3 〖案例 3〗计算平面点集凸壳的算法 (1)设凸集中 y 坐标最小点为 p1,把 p1 同凸集中其他各点用线段连接,并计算这些 线段与水平线的夹角。然后按夹角大小及到 p1 的距离进行词典式分类,得到一个序列 p1, p2,。。。,pn,依次连接这些点,便得到一个多边形。P1 是凸壳的边界的起点,p2 与 pn 也 必是凸壳的顶点。Pn+1=p1。 (2)删去 p3,p4,。。。,pn-1 中不是凸壳顶点的点。 (3)顺序输出凸壳顶点。 Graham 是求解平面点集凸壳问题的最佳方法。复杂度为 o(nlogn)。 /*********************************************\ * * * 寻找凸包 graham 扫描法 * * * \*********************************************/ #include #include ·156· ACM 程序设计培训教程 #include #include #include #include #include #include #include #include #include "geometry.h" #define input "graham.in" //Input file name #define output "graham.out" //Output file name #define max_points 100 FILE *fin,*fout; int probN=0,n; TPoint PointSet[max_points],ch[max_points]; int read_case() { int i; if (feof(fin)) return 0; fscanf(fin,"%d",&n); if (n==0) return 0; for (i=0;i #define infinity 1e20 #define EP 1e-10 struct TPoint{ float x,y; }; struct TLineSeg{ TPoint a,b; }; //求平面上两点之间的距离 float distance(TPoint p1,TPoint p2) { return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))); } /******************************************************** ·158· ACM 程序设计培训教程 返回(P1-P0)*(P2-P0)的叉积。 若结果为正,则的顺时针方向; 若为 0 则共线; 若为负则的在逆时针方向; 可以根据这个函数确定两条线段在交点处的转向, 比如确定 p0p1 和 p1p2 在 p1 处是左转还是右转,只要求 (p2-p0)*(p1-p0),若<0 则左转,>0 则右转,=0 则共线 *********************************************************/ float multiply(TPoint p1,TPoint p2,TPoint p0) { return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); } void Graham_scan(TPoint PointSet[],TPoint ch[],int n,int &len) { int i,j,k=0,top=2; TPoint tmp; //选取 PointSet 中 y 坐标最小的点 PointSet[k],如果这样的点有多个,则取最左边的一个 for(i=1;i0) || ( (multiply(PointSet[j],PointSet[k],PointSet[0])==0) &&(distance(PointSet[0],PointSet[j])=0) top--; ch[++top]=PointSet[i]; } len=top+1; }

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 3 人已下载

下载文档

相关文档