空间度量算法

1空间度量算法

《地理信息系统算法基础》2本讲内容1.直线和距离2.角度量算3.多边形面积的量算

31.直线和距离关于两点间距离的定义，使用标准的欧几里得距离L2，它基于毕达哥拉斯定理。对一个n维的矢量v=(v1，v2，…，vn)，它的长度|v|为对于P(p1，p2，…，pn)和Q(q1，q2,…，qn)两点间距离为41.直线和距离1.1直线1.2直线方程1.3点到直线的距离

51.1直线最初的直线：给出直线上的不同的两点P0和P1，定义了一条有限的从P0到P1的线段。延伸这条线段的任意一个端点会得到无限长的射线。现在所理解的直线：同时延长两个端点则将得到一条概念上的无限长的直线。直线L也可以通过一个点和方向来定义：令P0是L上的一点，vL是一个非零矢量，vL给出了直线的方向。设定vL=(P1-P0)，或给出P0和vL

，可以选择P1=P0+vL为直线上的第二个点。如果vL被规范化为单位矢量，uL=vL/|vL|那么它的每个系数就是L的各个方向角的余弦。

61.1直线在n维中，令θi(i=1,…,n)是L和第i个坐标轴ai的夹角（例如，在二维中，a1是x轴，a2是y轴）。那么矢量vL=(vi)，其中vi=cosθi,i=1,…,n，是L的一个方向矢量。

在二维中，如图6.1所示，如果θ是L与x轴的夹角，那么cosθ2=sinθ，并且vi=(cosθ1,cosθ2)=(cosθ,sinθ)是L的一个单位方向矢量。因为cos2θ+sin2θ=1。同样，对于任意维，各个方向余弦的平方和为1，即71.2直线方程直线可以使用方程来定义，方程中的未知数是点的坐标。

二维显式方程：最先接触到的，它在计算机软件中并不是最灵活的。

隐式方程更有用些，并且很容易将显式方程转化为隐式方程。隐式方程的前两个系数定义了一个矢量nL=(a，b)，这个矢量垂直于直线L。对于直线L上的任意两个点P0=(x0，y0)、P1=(x1，y1)，有nL·vL=(a,b)·(P1-P0)=a(x1-x0)+b(y1-y0)=f(P1)-f(P0)=0。给定一个直线L的法线矢量nL=(a，b)和L上的一个点P0，法线式的隐式方程为nL·(P-P0)=ax+by-nL·P0=0。如果a2+b2=1则称这个方程是规范化的，并且n是一个单位法线矢量。

81.2直线方程隐式或显式方程定义二维中的一条直线，三维中定义了一个平面，在n维中，它定义了一个(n-1)维的超平面。在任意n维的空间中，参数方程是有效的并且是最通用的。对于一个用两点P0和P1定义的并且带有方向矢量vL的直线，其方程有以下几种写法：P(t)=P0+tvL=P0+t(Pl–P0)=(1-t)P0+tP1式中，t为实数。在这个表达中，P(0)=P0,P(1)=P1，P(t)(0<t<1)是线段P0P1上的一点，其中t=d[P0,P(t)]/d(P0,P1)。因此P(1/2)=(P0+P1)/2是线段的中点。进一步看，如果t<0，那么P(t)位于线段之外，并且是在P0一边；如果t>1，P(t)也位于线段之外，但在P1—边，见图6.2。91.2直线方程三种方程表示形式中相互转换：例如，已知二维直线上的两点P0=(x0，y0)，P1=(x1，y1），我们可以根据这两点生成一个隐式的方程。由于vL=(xv，yv)=P1-P0=(x1-x0，y1-y0)是直线的方向矢量，因为nL·vL=0，可得直线L的法线矢量nL=(-yv，xv)=(y0-y1，x1-x0)。那么，直线L的一个隐式方程为(y0-y1)x+(x1-x0)y+(x0y1-x1y0)=0式中x和y的系数就是nL中的各个组成部分。101.2直线方程在二维中，θ是直线L与x轴的夹角，vL=(cosθ,sinθ)是单位方向矢量，因此nL=(-sinθ，cosθ)是一个单位法线矢量。如果P0=(x0，y0)是直线L上的某个点，那么一个规范化的L的方程为：-xsinθ+ysinθ+(x0sinθ-y0cosθ)=0因为sin2θ+cos2θ=1。再进一步，参数方程为P(t)=(x0+tcosθ，y0+tsinθ)111.3点到直线的距离

通常所说的距离指的是直线L和任意一个点P的最短距离d(P,L)。基点：过点作直线的垂线，垂线和直线的交点称为基点。如果L是一个有限的线段，那么P在L上的基点可能在线段之外，这就需要一个不同的计算最短距离的方法。（1）点到直线的垂直距离（2）点到射线或线段的距离12（1）点到直线的垂直距离①.两点定义的直线②.二维隐式方程定义的直线③.参数方程定义的直线13①.两点定义的直线

在二维和三维中，当L是通过两个点P0、P1给出的，可以使用矢量积直接计算出点P到L的距离。若是二维的，令第三个坐标Z=0即变为三维中。两个三维矢量的矢量积的模等于两矢量构成的平行四边形的面积，因为|v×w|=|v||w||sinθ|，其中θ是两个矢量v和w的夹角。14①.两点定义的直线但是，平行四边形的面积也等于底和高的乘积。令vL=P0P1=(P1-P0)、w=P0P=(P-P0)，如图6.3所示，这样点P到直线L的距离就是底P0P1的高。|vL×w|=Area(平行四边形(vL,w))=|vL|d(P,L)d(P,L)=|vL×w|/|vL|=|uL×w|式中，uL=vL/|vL|为直线L的单位方向矢量。若要计算多个点到同一条直线的距离，则首先计算uL是最高效的。15①.两点定义的直线对一个嵌入三维中的二维的情况，点P=(x，y，0)矢量积变为距离公式则变为特点：（1）没有计算分子的绝对值，计算出的结果是带有符号的距离，正的表示P点在直线的一边，负的表示在直线另一边。（2）分子的形式与直线隐式方程的形式相似。16②.二维隐式方程定义的直线直线L是很容易通过隐式方程f(x，y)=ax+by+c=0来定义。对于任意二维点P=（x，y），距离d(P，L)可以直接用这个方程计算出。矢量nL=（a，b）是直线L的法线矢量，利用nL即可计算任意点P到L的距离。首先在L上任意选一点P0，然后将矢量P0P投影到nL，如图6.4所示。17②.二维隐式方程定义的直线具体如下：（1）因为a和b不同时为零，设a≠0，则P0=(-c/a，0)位于直线L上；相反，如果a=0，则b≠0，则P0=(0，-c/b)，最后的结果是相同的。（2）对在L上的任意点P0有：nL·P0P=|nL||P0P|cosθ=|nL|d(P,L)。（3）对选定的点P0还有：nL·P0P=(a,b）•(x+c/a，y)=ax+by+c=f(x，y)=f(P)等于(2)。

18②.二维隐式方程定义的直线最后得出公式

用|nL|除f(x,y)的每个系数，使隐式方程规范化，即|nL|=1。这样则得出非常高效的公式d(P,L)=f(p)=ax+by+c，当a2+b2=1。对每个距离计算，这个公式只用了2次乘法运算和2次加法运算。

19②.二维隐式方程定义的直线

在二维中，若需要计算多个点到同一条直线L的距离，那么先得到规格化的隐式方程，然后使用这个公式。

只是比较距离(寻找离直线最近或最远的点），不需要规范化。因为它只是通过乘以一个常数因子来改变距离的值。当θ为L与x轴的夹角并且P0=(x0，y0)是L上的点，那么规范化后的隐式方程有：a=-sinθ，b=cosθ,和c=x0sinθ-y0cosθ。20③.参数方程定义的直线在n维空间中，已知直线L的参数方程为P(t)=P0+t(P1-P0)，P为任意n维空间中的任意一点。为了计算点P到直线L的距离d(P,L)，从点P作直线L的垂线，交于点P(b)。则向量P0P(b)是矢量P0P在线段P0P1上的投影，如图6.5所示。设vL=(P1-P0）和W=(P-P0)，则得到21③.参数方程定义的直线d(P,L)=|P-P(b)|=|w-bvL|=|w-(w·uL)uL|式中，uL为直线L的单位方向矢量。这个公式很适于在n维空间中使用，同时在计算基点P(b)也很有用。在三维空间中，和矢量积公式同样高效。但在二维中，当P(b)不是必须时，隐式公式的方法更好，尤其是计算多个点到同一条直线的距离。22(2).点到射线或线段的距离射线以某个点P0为起点，沿某个方向无限延伸。它可以用参数方程P(t)表达，其中t>0、P(0)=P0是射线的起点。一个有限的线段由一条直线上两端点P0、P1间的所有点组成。同样也可以用参数方程P(t)表达，其中P(0)=P0、P(1)=P1为两个端点，并且点P(t)(0≤t≤1)是线段上的点。计算点到射线或线段的距离与点到直线的距离的不同点是，点P到直线L的垂线与L的交点可能位于射线或线段之外。在这种情况下，实际的最短距离是点P到射线的起点的距离(图6.6)或是线段的某个端点的距离(图6.7)。23(2).点到射线或线段的距离

对于图6.6，只有一个选择，就是计算P到射线端点的距离；而对于一条线段，则必须判断哪一个端点离P更近。可以分别计算点到两个端点的距离，然后取最短的，但这不是最高效的办法，见图6.7。而且，同时要判断点P在直线L上的基点，是否在线段外。24(2).点到射线或线段的距离简便的方法：先判断与哪个端点的距离近，然后计算。具体方法：考虑P0P1、P0P的夹角，P1P、P0P1的夹角，如果其中有个角为90°，则对应的线段的端点就是P在L上的基点P(b)。如果不是直角，P的基点必然落在端点的一边或另一边，要看角是锐角还是钝角，如图6.8和图6.9所示。

可以通过计算矢量的数量积是正的、负的还是零来判断。最终得出应该计算点P到P0还是到P1的距离，或者是P到直线L的垂直距离。这些技术可以用到n维空间中。两个夹角的测试，可以只用两个数量积运算，即w0·v和v·v，同时w0·v和v·v是求P点在直线L上的基点的P(b)的参数b的分子和分母，这样可以依次测试和计算。25(2).点到射线或线段的距离

在二维中，如果我们要计算多个点到同一条射线或线段的距离，使用一个规范化的隐式方程来做一个最初的判断，一个点P到L是否有一个新的最小的距离的测试，还是很高效的。26(2).点到射线或线段的距离计算点P与线段L（P0，P1）距离的流程：计算点P在射线上的基点PbIfPb在线段内按照点到直线的距离公式计算最小距离Else

判断P与P0、P1哪个距离较小计算较小的距离272.角度量算（1）求直线a0x+b0y+c=0与直线a1x+b1y+c=0的夹角公式为当a0b1-a1b0=0，则两条直线平行。当a0a1+b0b1=0，则两条直线垂直。（2）求矢量A(xa，ya，za）（二维情形时A（xa，ya)，这里指的是三维情形）与矢量B(xb，yb，zb）的夹角。矢量A、B的点积表示为：a•b=xaxb+yayb+zazb，则两个矢量的夹角为

cosθ=(a•b)/(|a||b|)283.多边形面积的量算3.1三角形面积量算3.2四边形面积量算3.3任意二维平面多边形面积量算3.4任意三维平面多边形面积量算293.1三角形面积量算(1).古代的三角形(2).现代的三角形30(1).古代的三角形平行四边形(包括矩形和正方形)的面积等于平行四边形的底和高的乘积。两个相同三角形合在一起构成一个平行四边形，这样三角形的面积是三角形的底和高乘积的一半，如图6.10所示。平行四边形：A=bh三角形：A=bh/231(1).古代的三角形欧几里得法：三角形的高通常都需要通过计算顶点到边的垂直距离来获得。例如，如果知道一个三角形两条边a、b的长度和边a、b的夹角，采用三角函数，三角形的边b上的高h=asinθ，因此三角形的面积为(图6.11)A=(absinθ)/232(1).古代的三角形Heron公式：海伦得出的通过三条边计算三角形面积的公式（图6.12)，即式中，a、b、c为边的长度；s为周长的一半。通过代数变换，产生以下公式

这个公式中只需要边长的平方，这样则避免了通过三角形的三个顶点坐标计算边长时而产生的开平方运算。33(1).古代的三角形典型方法：确定一个三角形条件是：已知两个角和一个边，如图6.13所示。知道了三角形的两个角即知道了第三个角，因此，假定角θ和φ是边b的两个相邻的角。那么，面积公式如下古代三角形的特点：均利用边角关系计算面积。34(2).现代的三角形在三维空间中，平行四边形和三角形的面积可以表示为两个矢量边的矢量积的模|v×w|=|v||w||sinθ|的一半，其中θ是矢量v和w的夹角，因此，对于一个由顶点v0、v1、v2构成的三维三角形(图6.14)，令v=v1-v0、w=v2-v0,得到：35(2).现代的三角形一个二维矢量可以认为是三维中的第三个维被设为0的三维矢量(图6.15)，故可以计算二维的矢量的叉积，并且用它计算面积。给出三角形的顶点，vi=(xi,yi)=(xi,yi,0)，其中i=0,1,2,可以计算36(2).现代的三角形计箅出的矢量的模是三角形面积的两倍。但是，不计算绝对值而是让面积带有符号也是很有用的这里，vi=（xi，yi）37(2).现代的三角形这个面积公式非常高效，不需要计算开方根或三角函数计算，只是2次乘法运算和5次加法运算，可能还需一个除2运算(有时可以避免)。注意：若v0、v1、v2是逆时针排列，面积是正数；若v0、v1、v2是顺时针排列，面积则是负数。因此，面积计算可以用来判断三角形顶点的排列方向。有符号的面积可以用来判断点v2在方向线段v0v1的左边(正的)还是右边(负的）。因此，面积计算是个非常有用的基本公式，并且有个如此高效的计算公式。383.2四边形面积量算历史：希腊人将正方形、长方形、平行四边形、梯形挑出特殊对待。然后，对任意四边形会构造一个面积相等的平行四边形或正方形。平行四边形的面积等于底和高的乘积。但是，没有给出一个通用的计算公式。印度人婆罗摩笈多对Heron的三角形面积公式进行扩展，用来计算四边形的面积。但是，这个公式仅对共圆四边形有效，共圆四边形是指四个顶点都在某个圆上的四边形。393.2四边形面积量算这个公式非常对称。如果某个边的长度为0，设d=0，则四边形即变成了三角形(这个三角形的三个顶点也在某个圆上），这个公式就退化成Heron公式了。对于一个共圆四边形，令其四个边的长度为：a、b、c、d，s=（a+b+c+d)/2。那么，共圆四边形的面积公式为403.2四边形面积量算在现在的线性代数中，平面平行四边形的面积是两个邻接边的矢量积的模(图6.16)，因此，对任意三维平面四边形v0v1v2v3，有A(v0v1v2v3)=|(v1-v0)×(v3-v0)|

在二维中，顶点vi=(xi,yi)=(xi,yi,0)。其中i=0,1,2,3，面积公式变为这同样是个有符号的面积。①413.2四边形面积量算VarignonParallelogram：1731年，PierreVarignon发现对于任意一个四边形，取四个边的中点为顶点，构成一个新的四边形，这个四边形是个平行四边形，而且其面积是原始的四边形的面积的一半。对一个任意四边形，可以通过VarignonParallelogram计算其面积。对于任意四边形v0v1v2v3，令其四条边中点构成的平行四边形为M0M1M2M3，如图6.17所示。②423.2四边形面积量算由基本的几何学知识可以知道，三角形v0v1v2中，中点线M0M1平行于底v0v2

。所以，M0M1//M3M2同样，M0M3//M3M2，M0M1M2M3是平行四边形。433.2四边形面积量算四边形面积等于四边形的两个对角线的矢量积的模。这个公式可以用于任意的三维平面四边形。当这个公式在二维中使用时，则变成如下面积公式：这个公式用于任意四边形很高效，就像用于任意三角形的公式那么高效，只用了2次乘法和5次加法运算。对于简单四边形，当顶点逆时针排列时面积是正数；顺时针时面积是负数。③443.2四边形面积量算它也可以用于非简单四边形，等于四边形的两个边界区域的面积之差。例如，I(图6.18)是非简单四边形v0v1v2v3的自相交点，有453.3任意二维平面多边形面积量算一个二维多边形可以被分解为多个三角形。对计算面积而言，有一个非常容易的分解简单多边形(不自相交）的方法。如图6.19所示，令一个多边形Ω的顶点为Vi=(xi,yi)，i=0，…，n，vn=v0。P为一任意点，对多边形的每个边ViVi+1与点P构成三角形△i=△PViVi+1。则多边形的面积为所有三角形的符号面积之和。有463.3任意二维平面多边形面积量算

注意：对于一个逆时针多边形，当点P在边ViVi+1的左边，并且位于多边形内，则△i的面积是正的；相反，当点P在边ViVi+1的右边，并且位于多边形外部，则△i的面积是负的。如果是一个顺时针多边形，则符号相反，并且内部的三角形面积为负的。

473.3任意二维平面多边形面积量算在上面的图中，三角形△2=△PV2V3和△n-1=△PVn-1V0的面积是正的。但是很容易观察到，△2和△n-1只有一部分是在多边形内部，有一部分在外部。另一方面，三角形么△0和△1的面积是负的，这样就抵消了面积为正数的三角形在多边形外部的那部分面积。最终，外部的面积会被全部抵消掉。483.3任意二维平面多边形面积量算可以通过设定特定的点P和扩展条件，使公式更清楚。选P=(0，0)(图6.20)，每个三角形的面积简化为2A(△i)=(xiyi+1-xi+1yi)。这样就产生了这里，Vi=(xi,yi)。493.3任意二维平面多边形面积量算只需少许的代数运算。第二和第三个求和公式等价与第一公式。对一个有n个顶点的多边形。第一个公式用了2n次乘法运算和(2n-1)次加法运算；第二个公式用了n次乘法运算和(3n-1)次加法运算；第三个只用了n次乘法运算和(2n-1)次加法运算。所以，第三个公式是最高效的，但是为了避免计算imodn，必须将多边形的顶点数组升为Vn+1=V1。503.3任意二维平面多边形面积量算这个计算对于一个多边形会产生一个符号面积，当顶点是逆时针排列时面积是正的，顺时针时面积是负的。因此，面积计算可以判断多边形的整体方向。高效的方法判断多边形的方向方法：最简单的是找到最右边的最低的顶点，然后判断进入这个顶点和离开这个点的边的方向。这个判断可以通过检查离开边的最后顶点是否在进入边的左边，左边即意味着是逆时针。513.4任意三维平面多边形面积量算(1).经典算法(2).四边形分解(3).投影到二维平面52(1).经典算法前面已展示了一个三维的三角形△V0V1V2的面积为它的两个边的矢量积的模的一半，即|V0V1×V0V2|/2。经典的计算三维多边形的标准公式：其扩展了三角形的矢量积公式，其来自于斯托克斯定理。接下来展示如何从三维的三角形分解得到这个公式，使其在几何上更直观。53(1).经典算法

如图6.21所示，一个一般的三维平面多边形Ω包含顶点Vi=(xi，yi，zi)其中i=0，…，n，Vn=V0。所有的顶点都在一个相同的三维平面π上，n为平面的单位法线矢量。类似在二维空间中，令P是一个任意的三维点(并不要求在平面π上）；对Ω的每个边ei=ViVi+1，构成三维三角形△i=△PViVi+1。接下来要找到这些三角形面积的和与多边形Ω的面积之间的关系54(1).经典算法设已有的是一个以多边形为底，P为顶点的锥形。需要将这些三角形的边投影到平面π上。计算经过投影的三角形的符号面积。如果我们能够这样做，那么经过投影的面积的总和等于平面多边形的面积。55(1).经典算法如图6.22所示为了能够这样做，首先，对每个三角形△i关联一个面积矢量ai=1/2(PVi×PVi+1)这个面积矢量垂直于三角形△i，并且面积矢量的模等于三角形的面积。然后，作点P到平面π的垂线，交平面于点P0，则投影过的三角形为Ti=P0ViVi+1。作边ei=ViVi+1的垂线P0Bi交边于点Bi。56(1).经典算法因为，PP0垂直于ei，三个点PP0Bi定义的平面与ei垂直，并且PBi是点P到边e的垂线。所以，|PBi|是三角形△i的高，并且|P0Bi|是三角形Ti的高