- 1、本文档共15页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
计算几何资料集
计算几何资料集
本文档对应的程序库:点击下载
1.1????? 矢量
1.1.1?? 矢量的定义
如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点,我们可以把它称为矢量(vector)p2。因此在实际使用时,矢量的定义可以和顶点结构一样,而有向线段的定义需要建立在顶点的结构之上。而线段的定义可以和有向线段相同,只是在使用时可以不考虑起点和终点。注意我们现在考虑的几何结构都是二维的,所以点(矢量)、有向线段(线段)也被定义为二维。
//点结构
struct TPoint
{
double x, y;
TPoint(double a=0, double b=0) { x=a; y=b;}//这里为了使用方便,加入构造函数,不用担心,在C++的结构体中,可以插入函数定义。它和class的区别在于其内部的函数都是public类型的。
};
?
//线段结构
struct TLineSeg
{
TPoint s, e;
TLineSeg(TPoint a, TPoint b) { s=a; e=b;}
TLineSeg(){}
};
1.1.2?? 矢量加减
矢量的加减对应于三角形法则:
设两个二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则:
????????? 矢量加法定义: P + Q = ( x1 + x2 , y1 + y2 );即上图中的R
????????? 矢量减法定义为: P - Q = ( x1 - x2 , y1 - y2 )。即上图中的S
显然有性质:
????????? P + Q = Q + P;
????????? P - Q = - ( Q - P )。
下面我们定义两个函数用于矢量的加减:
//矢量相加
TPoint Add(TPoint a, TPoint b)
{
return(TPoint(a.x+b.x,a.y+b.y));
}
?
//矢量相减
TPoint Subtract(TPoint a, TPoint b)
{
return(TPoint(a.x-b.x,a.y-b.y));
}
1.1.3?? 矢量叉积
计算矢量叉积是与直线和线段相关算法的核心部分。设矢量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共线,但可能同向也可能反向。
下面是两个矢量叉积的函数:
/**************************************************************************
r=multiply(p1,p2),得到两个矢量p1,p2的叉积
r0:p1(前者)在p2(后者)的顺时针方向;
r=0:p1,p2共向;
r0:p1在p2的逆时针方向
举个简单的例子,看笛卡尔坐标系下x轴和y轴,分别选(1,0)和(0,1),得叉积为10,x在y的顺时针方向,即y到x是顺时针方向
***************************************************************************/
double Multiply(TPoint p1, TPoint p2)
{
return(p1.x*p2.y-p2.x*p1.y);
}
1.2??? 点、线段、矩形、多边形、圆之间的关系
1.2.1?? 折线段的拐向判断
折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:
????????? 若(p1 - p0)×(p2 - p0) 0,则p0p1在p1点拐向右侧后得到p1p2。
????????? 若(p1 - p0)×(p2
文档评论(0)