GIS中的计算几何

news/2024/7/8 6:08:30 标签: 算法, 图形, 网络, c

cle class="baidu_pl">

cle_content" class="article_content clearfix">

content_views" class="htmledit_views">

GIS中的计算几何

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">陈玉进李泉南京跬步科技有限公司（http://www.creable.cn）

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">GIS是一个class="tags" href="/tags/TuXing.html" title=图形>图形系统࿰c;必然会涉及到几何学的理论应用࿰c;比如࿰c;class="tags" href="/tags/TuXing.html" title=图形>图形可视化࿰c;空间拓扑分析࿰c;GISclass="tags" href="/tags/TuXing.html" title=图形>图形编辑等都需要用到几何。向量几何是用代数的方法来研究几何问题࿰c;首先࿰c;请大家翻一翻高等数学里有关向量的章节࿰c;熟悉一下几个重要的概念：向量、向量的模、向量的坐标表示、向量的加减运算、向量的点积、向量的叉积࿰c;以及这些概念的几何意义...下面我们将用这些基本概念来解答GIS中一些几何问题。

cm 16.5pt 21.25pt; text-indent: -21.25pt; mso-list: l1 level1 lfo2;">1 点和线的关系

点是否在线段上࿰c;这样的判断在class="tags" href="/tags/TuXing.html" title=图形>图形编辑࿰c;拓扑判断(比如࿰c;GPS跟踪点是否跑在线上)需要用到这样的判断。通常的想法是：先求线段的直线方程࿰c;再判断点是否符合这条直线方程࿰c;如果符合࿰c;还要判断点是否在线段所在的矩形区域(MBR)内࿰c;以排除延长线上的可能性࿰c;如果不符合࿰c;则点不在线段上。这种思路是可行的࿰c;但效率不高࿰c;涉及到建立方程࿰c;解方程。借助向量的叉积（也叫向量的向量积࿰c;结果还是向量࿰c;有方向的）可以很容易的判断。设向量a=(Xa,Ya,Za)cerun: yes;"> b=(Xb,Yb,Zb)cerun: yes;"> 向量叉积a X b如下：

class="blogimg" src="http://hiphotos.baidu.com/geochenyj/pic/item/40293faf27411af2fbed50e7.jpg" border="0" alt="" />

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%; text-align: center;" align="center">二维向量叉积的模 |a X b|=|a|*|b|*sinα=|Xa*Yb-Ya*Xb| （α是向量a,b之间的夹角）࿰c;向量叉积模的几何意义是以向量a,b为邻边的平行四边形的面积。可以推测：如果两向量共线࿰c;向量叉积模(所代表的

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%; text-align: center;" align="center">平行四边形的面积) 为零则cerun: yes;"> cerun: yes;">

|a X b|=|a|*|b|*sinα=|Xa*Yb-Ya*Xb|=0, 否则不共线࿰c;叉积的模为非零࿰c;根据这样条件可以很轻松的判断点和线的关系࿰c;避免了建立方程和解方程的麻烦。

class="blogimg" src="http://hiphotos.baidu.com/geochenyj/pic/item/853bdc1293b392c7c3fd78e0.jpg" border="0" alt="" />

class="MsoNormal" style="margin: 0cm 0cm 0pt; line-height: 150%;"> 向量叉积的模|AB X AC|=0即可判断C点在AB所确定的直线上࿰c;再结合C点是否在AB所在的MBR范围内࿰c;就可以最终确定C是否在AB线段上。关于点和线段的其他关系࿰c;都可以通过叉积的求得࿰c;比如判断点在线的哪一侧࿰c;右手法则࿰c;可以通过a X b= (Xa*Yb-Ya*Xb)*k中的（Xa*Yb-Ya*Xb）正负来判断。留给大家思考࿰c;很简单的࿰c;呵呵…

cm 16.5pt 21.25pt; text-indent: -21.25pt; mso-list: l1 level1 lfo2;">2 线和线的关系

判断两条线段是否相交࿰c;在很多拓扑判断和class="tags" href="/tags/TuXing.html" title=图形>图形编辑 ( 比如࿰c;线的打断来构建拓扑࿰c;编辑线对象࿰c;叠置分析࿰c;面与面关系的判断等 ) 中都需要用到线线相交的判断࿰c;如果两条线段相交࿰c;一条线段的两端点必然位于另一条线段的两侧（不考虑退化情况࿰c;也就是一条线段的端点在另一条线段上࿰c;这个很容易判断）

class="blogimg" src="http://hiphotos.baidu.com/geochenyj/pic/item/1368c84bae4322f982025ce1.jpg" border="0" alt="" />

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">两向量的叉积a X b= (Xa*Yb-Ya*Xb)*k ࿰c;分别判断AB X AC的方向与AB X AD的方向是否异号࿰c;再判断CD X CA 的方向与CD X CB的方向是否异号࿰c;即可判断两线段是否相交。

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">退化情况࿰c;即一条线的端点落在另一条线上。运用”点是否在线段上”的方法来判定。详细区分留给大家思考。呵呵…

利用向量的方向还可以判断线段的转向࿰c;这个在道路导航中有所应用：

class="blogimg" src="http://hiphotos.baidu.com/geochenyj/pic/item/1b18ad95ac12fc42d1135ee2.jpg" border="0" alt="" />

cm 16.5pt 21.25pt; text-indent: -21.25pt; mso-list: l1 level1 lfo2;">3 点和面的关系

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">在各种拓扑判断中（比如࿰c;面对象的选取࿰c;包含关系的判断等）需要判断一个点是否位于某个面内࿰c;经典的方法就是“垂线法”࿰c;在直角坐标系中࿰c;从这个点向X轴作射线࿰c;判断射线与多边形的交点个数（不考虑退化情况࿰c;退化情况下࿰c;判断点或者射线与多边形端点或者边的关系）࿰c;如果为奇数࿰c;则点在面内࿰c;为偶数࿰c;则点在面外。

cm 16.5pt 21.25pt; text-indent: -21.25pt; mso-list: l1 level1 lfo2;">4 线和面的关系

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">线面关系的判断相对比较复杂࿰c;线在面内࿰c;线和面相交࿰c;相离࿰c;相接等关系。线段在面内࿰c;第一个必要条件是࿰c;线段的两个端点都要在内。但由于多边形可能为凹࿰c;所以这不能成为判断的充分条件࿰c;于是有第二个必要条件线段与多边形的边࿰c;没有内部交点。

线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交࿰c;还必须判断两相邻交点之间的线段是否包含于多边形内部࿰c;如果在面内࿰c;则线段在面内࿰c;否则不在面内。

class="blogimg" src="http://hiphotos.baidu.com/geochenyj/pic/item/c cdf7ed5c50e8c cd51da4bf1.jpg" border="0" alt="" />

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">所以࿰c;class="tags" href="/tags/SuanFa.html" title=算法>算法思路如下（本class="tags" href="/tags/SuanFa.html" title=算法>算法引用class="tags" href="/tags/WangLuo.html" title=网络>网络上一篇文章）：

class="MsoNormal" style="margin: 0cm 0cm 0pt 84pt; text-indent: -26.25pt; mso-char-indent-count: -2.5; mso-para-margin-left: 5.5gd;">cerun: yes;">     if 线段PQ的端点不都在多边形内
        then return false;
    点集pointSet初始化为空;
      for 多边形的每条边s
        do if 线段的某个端点在s上
             then 将该端点加入pointSet;
           else if s的某个端点在线段PQ上
             then 将该端点加入pointSet;
           else if s和线段PQ相交 color: gray;">// color: gray;">这时候已经可以肯定是内交了
             then return false;
    将pointSet中的点按照X-Y坐标排序;
      for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
        do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
             then return false;
      return true;
cial-character: line-break;" />
cial-character: line-break;" />

class="MsoNormal" style="margin: 0cm 0cm 0pt;">注：X-Y坐标排序࿰c;X坐标小的排在前面࿰c;对于X坐标相同的点࿰c;Y坐标小的排在前面࿰c;这种排序准则也是为了保证水平和垂直情况的判断正确。

class="MsoNormal" style="margin: 0cm 0cm 0pt 21pt; text-indent: -21pt; mso-list: l2 level1 lfo3;">1. 点在面内࿰c;线段相交情况的判断见上面的思路。

class="MsoNormal" style="margin: 0cm 0cm 0pt 21pt; text-indent: -21pt; mso-list: l2 level1 lfo3;">2. 这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n࿰c;所以最多是常数级的复杂度࿰c;几乎可以忽略不计。因此class="tags" href="/tags/SuanFa.html" title=算法>算法的时间复杂度也是O(n)。

class="MsoNormal" style="margin: 0cm 0cm 0pt 21pt; text-indent: -21pt; mso-list: l2 level1 lfo3;">3. 有了线段和面的关系࿰c;再判断折线与面的关系࿰c;也就可以for循环࿰c;同理进行判断了࿰c;但时间复杂度将是O(n^2)。后面将介绍一种时间复杂度为O(nlogn)的”平面扫描class="tags" href="/tags/SuanFa.html" title=算法>算法”。

class="MsoNormal" style="margin: 0cm 0cm 0pt 84.75pt; text-indent: -63pt; mso-char-indent-count: -6.0; mso-para-margin-left: 2.07gd;">

cm 16.5pt 21.25pt; text-indent: -21.25pt; mso-list: l1 level1 lfo2;">5 面和面的关系

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">面面的空间关系࿰c;可能要更复杂一些࿰c;在拓扑判断࿰c;多边形叠置分析࿰c;面对象的编辑中࿰c;有着广泛的应用。这个将在以后的章节中介绍一种时间复杂度为O（nlogn）的class="tags" href="/tags/SuanFa.html" title=算法>算法“平面扫描class="tags" href="/tags/SuanFa.html" title=算法>算法”。

cm 16.5pt 21.25pt; text-indent: -21.25pt; mso-list: l1 level1 lfo2;">6 点到线段的距离

点到线段的距离࿰c;在各种测量࿰c;拓扑判断 ( 比如࿰c;线对象的选取中需要比较距离 ) 中都需要用到。大家对点到直线的距离࿰c;都很熟悉࿰c;那点到线段距离又该如何计算呢？

class="blogimg" src="http://hiphotos.baidu.com/geochenyj/pic/item/831ff20a782d741695ca6bfc.jpg" border="0" alt="" />

问题的关键是判断 a 、 r 的角度࿰c;向量的点积能判断一个角是钝角还是锐角࿰c;先复习一下向量的点积࿰c;也叫向量的数量积 , 结果是一个数࿰c;没有方向。设向量 a=(Xa,Ya,Za)cerun: yes;"> b=(Xb,Yb,Zb)cerun: yes;">

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">a . b=|a|*|b|*cosα=Xa*Xb+Ya*Yb+Za*Zb 向量点积的几何意义是࿰c;高中物理中࿰c;求作用力在一个方向上所作的功。如果a . b>0࿰c;则α为锐角࿰c;a . b<0,则α钝角。

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">熟悉了利用向量的点积来判断角度࿰c;AC·AB 判断夹角a࿰c;BA·BC判断夹角r࿰c;即可确定三种情况中࿰c;具体是哪一种。至于第一种情况࿰c;求点到垂足的距离࿰c;可以饶开建立方程求垂足࿰c;再求两点距离的思路࿰c;因为建立方程运算是复杂的࿰c;多耗了CPU资源。利用向量叉积的几何意义来求࿰c;向量的叉积表示以两向量为邻边的平行四边形的面积࿰c;|AC X AB|为⊿ABC的面积的两倍࿰c;求平行四边形的高,只要用面积除以底边AB的长度。即࿰c;高CD的长度=|AC X AB|/distance(AB)。

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">

class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21.85pt; line-height: 150%;">这些复杂的几何判断࿰c;都将在空间索引的过滤下࿰c;在少量数据集(侯选集)上进行。计算几何class="tags" href="/tags/SuanFa.html" title=算法>算法࿰c;通常是比较复杂࿰c;比较耗CPU资源࿰c;而且还要考虑各种退化情况࿰c;在这里࿰c;并不试图向大家穷举各种情况࿰c;只想起一个抛砖引玉的作用࿰c; 或许还有人会有这样的疑虑：有没考虑“投影”的问题？关于投影将在相应的章节中给予解释࿰c;但有一点是可以肯定的࿰c;空间分析、计算几何class="tags" href="/tags/SuanFa.html" title=算法>算法࿰c;都是在平面直角坐标系下运算的࿰c;不会在球面上。