📄 2.5.3包含判定算法.htm

📁 计算机图形学教程计算机图形学教程
💻 HTM
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les253.htm -->
<HTML><HEAD><TITLE>2</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY>
<H3 align=justify><B><FONT face=楷体_GB2312 size=4>2.5.3包含判定算法</FONT></B></H3>
<P align=justify><FONT face=楷体_GB2312 
size=4>在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下面主要讨论关于点的包含判定算法。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>（1）直线段，（2）圆锥曲线段（主要是圆弧），（3）参数曲线（主要是Bezier，B样条与NURBS曲线）。点与面的包含判定也类似地分为三种情况。下面分别讨论。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>1、点与直线段的包含判定</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>假设点坐标为P(x, y, 
z)，直线段端点为P<SUB>1</SUB>(x<SUB>1</SUB>, y<SUB>1</SUB>, 
z<SUB>1</SUB>)，P<SUB>2</SUB>(x<SUB>2</SUB>,y<SUB>2</SUB>,z<SUB>2</SUB>)，则点P到线段P<SUB>1</SUB>P<SUB>2</SUB>的距离的平方为</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>d<SUP>2</SUP>=(x-x<SUB>1</SUB>)<SUP>2</SUP>+(y-y<SUB>1</SUB>)<SUP>2</SUP>+(z-z<SUB>1</SUB>)<SUP>2</SUP>-[(x<SUB>2</SUB>-x<SUB>1</SUB>)(x-x<SUB>1</SUB>)+(y<SUB>2</SUB>-y<SUB>1</SUB>)(y-y<SUB>1</SUB>)+(z<SUB>2</SUB>-z<SUB>1</SUB>)(z-z<SUB>1</SUB>)]<SUP>2</SUP>/[(x<SUB>2</SUB>-x<SUB>1</SUB>)<SUP>2</SUP>+(y<SUB>2</SUB>-y<SUB>1</SUB>)<SUP>2</SUP>+(z<SUB>2</SUB>-z<SUB>1</SUB>)<SUP>2</SUP>]</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>当d<SUP>2</SUP>&lt;? 
<SUP>2</SUP>时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内。只要对坐标分量进行比较，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当x-x<SUB>1</SUB>与x-x<SUB>2</SUB>反号时，点P在线段的有效区间内。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>2、点与圆锥曲线段的包含判定</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>以圆弧为例，假设点的坐标为(x, y, 
z)，圆弧的中心为（x<SUB>0</SUB>, y<SUB>0</SUB>, z<SUB>0</SUB>），半径为r，起始角? 
<SUB>1</SUB>，终止角? <SUB>2</SUB>。这些角度都是相对于局部坐标系x轴而言。圆弧所在平面为</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>　　　　ax+by+cz+d=0</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>给定中心为（x<SUB>0</SUB>, 
y<SUB>0</SUB>），半径为r，起始角? <SUB>1</SUB>，终止角? <SUB>2</SUB>的圆弧，对平面上一点P（x, 
y），判断P是否在圆弧上，可分二步进行。第一步判断P是否在圆心为（x<SUB>0</SUB>, 
y<SUB>0</SUB>），半径为r的圆的圆周上，即下式是否成立：</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>　　　　<IMG height=29 
src="2.5.3包含判定算法.files/Image99.gif" width=197></FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>第二步判断P是否在有效的圆弧段内。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>3、点与参数曲线的包含判定</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>设点坐标为P(x, y, z)，参数曲线为Q(t)=(x(t), 
y(t), z(t))。点也参数曲线的求交计算包括三个步骤：</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>（1）计算参数t值，使P到Q(t)的距离最小；</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>（2）判断t是否在有效参数区间内（通常为[0，1]）；</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>（3）判断Q(t)与P的距离是否小于? 
。若（2），（3）步的判断均为“是”，则点在曲线上；否则点不在曲线上。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>第一步应计算t，使得|P-Q(t)|最小，</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>即 
R(t)=(P-Q(t))(P-Q(t))=|P-Q(t)|<SUP>2</SUP>最小</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>根据微积分知识，在该处R? (t)=0即</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>Q? (t)[P-Q(t)]=0</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>用数值方法解出t值，再代入曲线参数方程可求出曲线上对应点的坐标。第（2）、（3）步的处理比较简单，不再详述。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>4、点与平面区域的包含判定</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>设点坐标为P(x, y, 
z)，平面方程为ax+by+cz+d=0。则点到平面的距离为</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>　　　　d=<IMG height=45 
src="2.5.3包含判定算法.files/Image100.gif" width=113></FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>若d&lt;? 
，则认为点在平面上，否则认为点不在平面上。在造型系统中，通常使用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。下面以平面区域多边形为例，介绍有关算法。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，这里仅介绍常用的三种：叉积判断法、夹角之和检验法以及交点计数检验法。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>（1）叉积判断法</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>假设判断点为P<SUB>0</SUB>。多边形顶点按顺序排列为P<SUB>1</SUB>P<SUB>2</SUB>…P<SUB>n</SUB>。如图2.5.2所示。令V<SUB>i</SUB>=P<SUB>i</SUB>-P<SUB>0</SUB>, 
i=1, 2, …, n, V<SUB>n+1</SUB>=V<SUB>1</SUB>。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>那么，P<SUB>0</SUB>在多边形内的充要条件是叉积V<SUB>i? </SUB>V<SUB>i+1</SUB>(i=1, 2, …, 
n)的符号相同。叉积判断法仅适用于凸多边形。当多边形为凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面介绍的两种方法。</FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4><IMG height=268 
alt="2_5_2.gif (4875 bytes)" src="2.5.3包含判定算法.files/2_5_2.gif" 
width=607></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4>图2.5.2 叉积判断法</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>（2）夹角之和检验法</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>假设某平面上有点P<SUB>0</SUB>和多边形P<SUB>1</SUB>P<SUB>2</SUB>P<SUB>3</SUB>P<SUB>4</SUB>P<SUB>5</SUB>，如图2.5.3所示。将点P<SUB>0</SUB>分别与P<SUB>i</SUB>相连，构成向量V<SUB>i</SUB>=P-P<SUB>0</SUB>。假设角 
P<SUB>i</SUB>P<SUB>0</SUB>P<SUB>i+1</SUB>=? <SUB>i</SUB>。如果<IMG height=45 
src="2.5.3包含判定算法.files/Image101.gif" 
width=38>=0，则点P<SUB>0</SUB>在多边形之外，如图2.5.3(a)所示。如果<IMG height=45 
src="2.5.3包含判定算法.files/Image102.gif" 
width=38>=2π，则点P<SUB>0</SUB>在多边形之内，如图2.5.3(b)所示。a<SUB>i</SUB>可通过下列公式计算：令S<SUB>i</SUB>=V<SUB>i? 
</SUB>V<SUB>i+1</SUB>, C<SUB>i</SUB>=V<SUB>i</SUB>·V<SUB>i+1</SUB>，则tg(? 
<SUB>i</SUB>)=S<SUB>i</SUB>/C<SUB>i</SUB>，所以a<SUB>i</SUB>=arctg(S<SUB>i</SUB>/C<SUB>i</SUB>)且</FONT></P>
<P><FONT face=楷体_GB2312 size=4>a<SUB>i</SUB>的符号即代表角度的方向。</FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4><IMG height=236 
alt="2_5_3.gif (5201 bytes)" src="2.5.3包含判定算法.files/2_5_3.gif" 
width=529></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4>图2.5.3 夹角之和检验法</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>在多边形边数不太多（&lt;44）的情况下，可以采用下列近似公式计算? 
<SUB>i</SUB>。</FONT></P>
<P><FONT face=楷体_GB2312 size=4><IMG height=45 
src="2.5.3包含判定算法.files/Image103.gif" width=94>　　　　当 
|S<SUB>i</SUB>|≤|C<SUB>i</SUB>|</FONT></P>
<P><FONT face=楷体_GB2312 size=4><IMG height=45 
src="2.5.3包含判定算法.files/Image104.gif" width=122>　　当 
|S<SUB>i</SUB>|&gt;|C<SUB>i</SUB>|</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>其中d=0.0355573为常数。当<SUB>Σαi≥π</SUB></FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>时，可判P<SUB>0</SUB>在多边形内。当<SUB>Σαi＜π</SUB> 
时，可判P<SUB>0</SUB>在多边形外。证明略。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>（3）交点计数检验法</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作一射线至无穷远：</FONT><FONT 
face=System></P></FONT>
<P><FONT face=楷体_GB2312 size=4><IMG height=49 
src="2.5.3包含判定算法.files/Image105.gif" width=121></FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>求射线与多边形边的交点个数。若个数为奇数，则点在多边形内，否则，点在多边形外。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>如图2.5.4所示，射线a, 
c分别与多边形交于二点和四点，为偶数，故判断点A，C在多边形外。而射线b, d与多边形交三点和一点，为奇数，所以B，D在多边形内。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>当射线穿过多边形顶点时，必须特殊对待。如图2.5.4所示，射线f过顶点，若将交点计数为2，则会错误地判断F在多边形外。但是，若规定射线过顶点时，计数为1，则又会错误地判断点E在多边形内。正确的方法是，若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。按这种方法，E点计为2，所以在多边形外；F点计数为１，所以在多边形内。读者可以自己另取一些点来验证。</FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4><IMG height=216 
alt="2_5_4.gif (3218 bytes)" src="2.5.3包含判定算法.files/2_5_4.gif" 
width=287></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4>图2.5.4 交点计数法</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>5、点与二次曲面/参数曲面的包含判定</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>假设点坐标为P(x<SUB>0</SUB>, 
y<SUB>0</SUB>, z<SUB>0</SUB>)，二次曲面方程为Q(x, y, z)=0，则当|Q(x<SUB>0</SUB>, 
y<SUB>0</SUB>, z<SUB>0</SUB>)|&lt;? 
时，认为点在该二次曲面上，在造型系统中，通常使用裁剪的二次曲面。在这种情况下，还要判断点是否在有效范围内。裁剪的二次曲面通常用有理Bezier或有理B样条的参数空间上的闭合曲线来定义曲面的有效范围，故要把点所对应的参数空间的参数坐标计算出来，再判断该参数坐标是否在参数空间有效区域上。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4>6、点与三维形体的包含判定</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>判断点是否被三维形体所包含，可先用前面的方法判断点是否在三维形体的表面上，然后判断点是否在形体内部，其方法因形体不同而异。下面以凸多面体为例说明。</FONT></P>
<P align=justify><FONT face=楷体_GB2312 
size=4>设凸多面体某个面的平面方程为ax+by+cz+d=0，调整方程系数的符号，使当ax+by+cz+d&lt;0时，点(x,y,z)位于该平面两侧中包含该凸多面体的一侧。于是要检验一个点是否在凸多面体内部，只要检验是否它对凸多面体的每一个面均满足以上的不等式即可。</FONT></P>
<P>　</P>
<P><A href="http://www.ekany.com/wdg98/cg/contents/chapter2/les252.htm"><FONT 
face=楷体_GB2312>&lt;上一节〉</FONT></A><FONT face=楷体_GB2312>&nbsp;&nbsp;&nbsp; <A 
href="http://www.ekany.com/wdg98/cg/contents/chapter2/les254.htm">〈下一节〉</A> 
&nbsp;&nbsp;&nbsp; <A 
href="http://www.ekany.com/wdg98/cg/tutorial/chapter2/lesson2-5.htm">〈返回〉</A></FONT></P></BODY></HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -