📄 2.5.5 凸包计算.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les255.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><A name=2.5.5凸包计算><B><FONT face=楷体_GB2312 size=4>2.5.5
凸包计算</FONT></B></A></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><FONT
size=4>包围盒是一种特殊而又十分常用的凸包。二维的包围盒是二维平面上的一个矩形，它的两条边分别与两条坐标轴x，y平行，可以表示为两个不等式：x<SUB>min</SUB>≤x≤x<SUB>max</SUB>，y<SUB>min</SUB>≤y≤y<SUB>max</SUB>；三维空间中的包围盒是一个长方体，其长、宽、高分别与三条坐标轴平行，表示为三个不等式：x<SUB>min</SUB>≤x≤x<SUB>max</SUB>，y<SUB>min</SUB>≤y≤y<SUB>max</SUB>，z<SUB>min</SUB>≤z≤z<SUB>max</SUB>。两个包围盒相交的充要条件是它们在每一个坐标轴方向上都相交。由于判定两个包围盒的相交情况比较容易，所以包围盒成为最常用的一种凸包。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312
size=4>求多边形或多面体的包围盒是相当简便的。只要遍历其所有顶点，就可以找出多边形或多面体在各个坐标轴方向上的最大、最小坐标值，从而确定包围盒。对于已近似化为多边形或多面体的含有曲线曲面的几何体，也可以用同样的方法求出包围盒。对于一般的几何形体，则要根据其具体性质来求取其包围盒。</FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>在进行含有曲线、曲面的几何体的求交时，常常先求取它们的一个凸多边形或凸多面体的凸包，由于凸多边形和凸多面体间的求交相对简单，可以节省一定的计算量。例如，Bezier、B样条和NURBS曲线曲面具有凸包性质，其控制多边形或控制网格是其本身的凸包。在进行此类曲线曲面的求交计算时，就常先用其控制多边形或控制网格求交。</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4> 一般的凸包的求法因具体情况而异，下面举一个求圆弧凸包的例子。设圆弧段的圆方程为</FONT> <FONT
size=4>(x-x<SUB>0</SUB>)<SUP>2</SUP>+(y-y<SUB>0</SUB>)<SUP>2</SUP>=r<SUP>2</SUP>，圆弧起始角为?
<SUB>1</SUB>，终止角为? <SUB>2</SUB>。对圆弧计算凸包如图2.5.5所示。先根据起始角? <SUB>1</SUB>与终止角?
<SUB>2</SUB>求出相应的弧端点坐标P<SUB>1</SUB>，P<SUB>2</SUB>，进而求出弧的弦中点P<SUB>m</SUB>=(P<SUB>1</SUB>+P<SUB>2</SUB>)/2。再用（q
<SUB>1</SUB>+q <SUB>2</SUB><FONT face=宋体
size=3>）</FONT>/2的正、余弦或下式计算弧中点P<SUB>c</SUB>：</FONT></FONT></P>
<P align=justify><FONT face=楷体_GB2312 size=4> <IMG height=45
src="2.5.5 凸包计算.files/Image106.gif" width=141></FONT></P>
<P align=justify><FONT face=楷体_GB2312><FONT
size=4>则该弧的包围盒顶点为P<SUB>1</SUB>，P<SUB>1</SUB>+（P<SUB>c</SUB>-P<SUB>m</SUB>），P<SUB>2</SUB>+（P<SUB>c</SUB>-P<SUB>m</SUB>）,
P<SUB>2</SUB>。</FONT></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4><IMG height=171
alt="2_5_5.gif (2283 bytes)" src="2.5.5 凸包计算.files/2_5_5.gif"
width=216></FONT></P>
<P align=center><FONT face=楷体_GB2312 size=4>图2.5.5 圆弧的凸包</FONT></P>
<P><B><FONT size=4><FONT
face=楷体_GB2312>
</FONT></FONT></B><FONT size=4> </FONT> <FONT
face=Arial size=5><B></P></B></FONT>
<P><A href="http://www.ekany.com/wdg98/cg/contents/chapter2/les254.htm"><FONT
face=楷体_GB2312><上一节〉</FONT></A><FONT face=楷体_GB2312> <A
href="http://www.ekany.com/wdg98/cg/contents/chapter2/les261.htm">〈下一节〉</A>
<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 + -