0° ≤ β < 360°
判断点与多边形位置关系的铅垂线内点算法 判断点与多边形位置关系的铅垂线内点算法
(适用于带孔多边形 适用于带孔多边形) 适用于带孔多边形
基本思想:从待判别点引铅垂线， 基本思想:从待判别点引铅垂线，由该铅垂线 注意：是一条射线）与多边形交点个数的奇 （注意：是一条射线）与多边形交点个数的奇 偶性来判断点是否在多边形内 来判断点是否在多边形内。 偶性来判断点是否在多边形内。 若交点个数为奇数，点在多边形内； 若交点个数为奇数，点在多边形内； 若交点个数为偶数，则该点在多边形外。 若交点个数为偶数，则该点在究的重点问题是求线与面的相交。 线面关系研究的重点问题是求线与面的相交。 求线与面的相交 线段与多边形交线的算法 ：
第一步，求多边形的最小投影矩形。 第一步，求多边形的最小投影矩形。 第二步， 第二步，判断线段是否有端点在该最小投影矩形 若不在，结论为“线段与多边形相离” 中。若不在，结论为“线段与多边形相离”，算 法结束；否则，执行第三步。 法结束；否则，执行第三步。 第三步，顺次判断线段与多边形各边是否有交点， 第三步，顺次判断线段与多边形各边是否有交点， 若有交点，则求出并保存交点坐标。 若有交点，则求出并保存交点坐标。 第四步，对交点坐标排序：计算各交点与线段一 第四步，对交点坐标排序：计算各交点与线段一 端点的距离 的距离， 端点的距离，然后按照距离由小到大对交点编号 排序。 排序。 第五步，按规律连接各个交点， 第五步，按规律连接各个交点，得到位于多边形内部的 连接各个交点 交线。 交线。
判断点线侧位关系的意义？ 判断点线侧位关系的意义？
1.2 点、线关系的判别方法 点线关系判别的目的之一是确定点是否在线上。 点线关系判别的目的之一是确定点是否在线上。
p1
P2 B P6
P3
P4
A
P5
点线关系的判断（虚线为投影矩形） 图2-1 点线关系的判断（虚线为投影矩形）
1.3 点到线的距离计算
{ if(((PointXyz[j].x<x&&x<PointXyz[j+2].x)||(PointXyz[j+2].x<x&&x<PointXyz[j].x))&&PointXyz[j+2].y>y) //若前后相邻的两顶点在该顶点所做铅垂线分得异侧，则num++ 若前后相邻的两顶点在该顶点所做铅垂线分得异侧， 若前后相邻的两顶点在该顶点所做铅垂线分得异侧 num=num+1; else if(x==PointXyz[j+1].x&&x==PointXyz[j+2].x&&PointXyz[j+2].y>y) //若铅垂线与边部分重合 若铅垂线与边部分重合 { if((PointXyz[j+3].x<x&&x<PointXyz[j].x)||(PointXyz[j].x<x&&x<PointXyz[j+3].x)) num=num+1; } } } if(num%2==1) { MessageBox("点在多边形内！");} 点在多边形内！ 点在多边形内 else if(num%2==0) { MessageBox("点在多边形外！");} 点在多边形外！ 点在多边形外 }
部分源代码： 部分源代码：
void CDraw1View::judge2(float x, float y) { float xmax=PointXyz[0].x; float xmin=PointXyz[0].x; float ymin=PointXyz[0].y; float fy; //fy为待判断点与直线方程的交点的纵坐标 为待判断点与直线方程的交点的纵坐标 int num=0; //记录待判断点与直线方程的交点的数目 记录待判断点与直线方程的交点的数目 PointXyz[a].x=PointXyz[0].x; PointXyz[a].y=PointXyz[0].y; PointXyz[a+1].x=PointXyz[1].x;PointXyz[a+1].y=PointXyz[1].y; PointXyz[a+2].x=PointXyz[2].x; PointXyz[a+2].y=PointXyz[2].y; PointXyz[a+3].x=PointXyz[3].x; PointXyz[a+3].y=PointXyz[3].y;
3.2 点与多边形位置关系的计算
判断点与多边形位置关系的夹角求和算法
(只适用于简单多边形 对于带孔多边形的算法改进比较麻烦 只适用于简单多边形,对于带孔多边形的算法改进比较麻烦 只适用于简单多边形 对于带孔多边形的算法改进比较麻烦)
设有一简单n边形，其顶点可以表示为 设有一简单 边形，其顶点可以表示为Pi(xi,yi)， 边形 i=1,2…, ，另有待判别的独立点A。连接点A与多边 =1,2…,n，另有待判别的独立点A =1,2…, 形的各个顶点，计算其夹角和，且规定顺时针方向 形的各个顶点，计算其夹角和， 旋转的角度为正 逆时针方向旋转的角度为负 旋转的角度为正，逆时针方向旋转的角度为负。若 有
若满足： 若满足：
图2-5 点与三角形的位置关系
则点P位于三角形的内部，否则点 位 则点 位于三角形的内部，否则点P位 位于三角形的内部 于三角形的外部。 于三角形的外部。
void CTView::OnLButtonUp(UINT nFlags, CPoint point) { // TODO: Add your message handler code here and/or call default //CView::OnLButtonUp(nFlags, point); if(m_DrawCurrent==2) { float F1=f1(PointXyz[2].x,PointXyz[2].y); float F2=f2(PointXyz[0].x,PointXyz[0].y); float F3=f3(PointXyz[1].x,PointXyz[1].y); float F4=f1(float(mPointOrign.x),float(mPointOrign.y)); float F5=f2(float(mPointOrign.x),float(mPointOrign.y)); float F6=f3(float(mPointOrign.x),float(mPointOrign.y)); if(F1*F4>0 && F2*F5>0 && F3*F6>0) MessageBox(" 点在三角形内！ "); 点在三角形内！ 点在三角形外！ else MessageBox(" 点在三角形外！ "); ReleaseCapture(); } }
A P1
P2
P2 P1 A P3 P4
（b）
P3 P4
（a）
图2-12 铅垂线交于多边形的顶点
P2 P1 P1 A P3 P2
A P3
P6 P5
（a）
P4
P5
P4
（b）
图2-13 铅垂线与多边形的一边相重合
特殊情况的考虑： 特殊情况的考虑： 1. 交点位于多边形顶点 建立铅垂线的直线方程，判断该顶点前、 建立铅垂线的直线方程，判断该顶点前、后相邻 的两顶点是否在铅垂线的同侧，若在同侧， 的两顶点是否在铅垂线的同侧，若在同侧，Num不 变，否则Num加1。 2. 铅垂线与多边形的一条边重合 建立铅垂线的直线方程， 建立铅垂线的直线方程，判断与该边两端点相邻的 后两顶点是否在铅垂线的同侧，若在同侧， 前、后两顶点是否在铅垂线的同侧，若在同侧， Num不变 否则Num 不变， Num加 Num不变，否则Num加1。
点到线段的距离可能是该点与线段某一端点的距离， 点到线段的距离可能是该点与线段某一端点的距离， 某一端点的距离 也可能是点到线段的垂距 垂距。 也可能是点到线段的垂距。
p1 p1
A
p2 （a）
A
p2
（b）
图2-2 点与线段距离的两种情形
点到线的距离有最远距离和最近距离。 点到线的距离有最远距离和最近距离。
图2-4 折线的单调链划分及其投影矩形 折线自相交的判断与此基本一样. 折线自相交的判断与此基本一样
3.点面关系 3.点面关系
3.1点与三角形位置关系的计算 3.1点与三角形位置关系的计算 AB BC CA
f1 ( x, y ) = a1 x + b1 y + c1 f 2 ( x, y ) = a 2 x + b2 y + c2
1. 点线关系
点在线上
点线相离
研究重点：点与线段的侧位关系判断、 研究重点：点与线段的侧位关系判断、点与线 拓扑关系的判别方法及点到线的距离计算。 拓扑关系的判别方法及点到线的距离计算。
1.1 点线侧位关系判断
Ax 设有一条直线，其方程为： 设有一条直线，其方程为： + By + C = 0 ，则对于函 数 f ( x, y ) = Ax + By + C ，任取空间一点 m( x0 , y 0 ) ，有：
l6 l4 l3 l2 k1
第一步：生成单调链 此图中 第一步：生成单调链(此图中 为关于纵坐标的单调链) 为关于纵坐标的单调链
k2
L
l1 l5
K
k3
第二步： 第二步：计算每个单调链的 最小投影矩形 第三步： 第三步：两两判断最小投影 矩形是否相交,如相交 如相交,才判 矩形是否相交 如相交 才判 断其对应单调链是否相交. 断其对应单调链是否相交
f 3 ( x, y ) = a3 x + b3 y + c3
