文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 第八章 数论算法及计算几何算法
侵权投诉

第八章 数论算法及计算几何算法

236 两条辅助线段与线段u的叉积,如果这两个叉积同号,说明线段v的两个端点在线段u的同侧,即线段v不跨立线段u。同理,可确定线段u是否跨立线段v。

跨立实验算法描述:

bool intersect2(LINESEG u,LINESEG v) {

return((multiply(v.s,u.e,u.s)*multiply(v.e,u.e,u.s)>0)||(multiply(u.s,v.e,v.s)*multiply(u.e,v.e,v.s)>0)); }

判断两条线段是否相交算法描述如下:

void intersect(LINESEG u,LINESEG v) {

if(intersect1(u,v))

cout<<" 两条线段不相交"<<endl; else if(intersect2(u,v))

cout<<"两条线段不相交"<<endl; else

cout<<"两条线段相交"<<endl; }

4.确定任意一对线段相交

该问题讨论对应给定的一个线段集合,确定其中任意两条线段是否相交。该算法输入由若干条线段组成的集合,若这组线段中存在任意一对线段相交,则返回true;否则,返回false。为了使问题简化,可做如下两点假设:

(1)线段集合中的所有线段都不是竖直的; (2)未有三条输入线段相交于同一点的情形。

算法假设一条垂直扫描线沿X轴方向从左到右顺序移动、穿过已知的若干线段。移动过程中,每遇到一个线段端点,它就将穿过扫描线的所有线段放入一个动态数据结构中,并利用它们之间的关系进行排序,核查是否有相交点存在。

由于不存在垂直的输入线段,所以如果任何输入线段与给定的垂直扫描线相交,只能有一个交点。此时,将与垂直扫描线相交的线段按交点的y坐标值单调递增存放在一个序列T中。当线段的左端点遇到扫描线时,线段就进入序列T;当其右端点遇到扫描线时便随之离开序列T。

显然,随着垂直扫描先由左至右平移,T序列中线段的数量及线段的相对位置将会发生变化。主要是因为:

(1)扫描线遇到某线段的左端点时,该线段进人T序列;遇到某线段的右端点时,该线段离开T序列;

(2)扫描线穿过两线段交点前后的某区域时,它们在T序列的位置将对换。也就是说,两条线段在交点前后的某区域内在T序列中是相邻的。

因此,该算法要求安排两个集合,一个是T序列,另一个是扫描线的一系列位置,即线段端点位置,并且要标记端点为线段的左端点还是线段的右端点。遇到左端点时将线段插入序列T中,并考察与其相邻的线段是否相交;遇到右端点时将线段从序列T中删除,此时考察被删除线段的左右两条线段是否相交。

算法描述如下:

bool any_intersect(LINESEG s[]) // s中存储输入线段集合 {

上一页第12页

热门文档

相关文档

  • 第8章 数论算法及计算几何算法

    第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...

  • 第8章 数论算法及计算几何算法

    第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...

  • 第8章 数论算法及计算几何算法

    第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...

  • 数论和计算几何

    数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...

  • 数论和计算几何

    第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...

  • 离散数论-第八章

    离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...

  • 第二章 贪心法

    第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...

  • 进化算法EA

    [编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...

  • 第8章 几何运算

    三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...

  • 第一章 算法及基础知识

    224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email