GIS中要素的捕捉以及C++实现

长平狐 发布于 2013/12/25 17:25
阅读 122
收藏 0

这篇文章早在去年就写出来了,但是由于当时毕业论文有一段是直接引用了我的这篇文章,怕引起查重的麻烦就删掉了,在此,重新挂出来和大家一起分享。

要素的选择,也称为要素的捕捉,在CAD、计算机图形学和地理信息系统中占据着相当重要的作用。比如,用户要根据鼠标在屏幕上的点击判断出选择的是哪一个点、线和面,这是经常碰到的操作。这种操作可以很方便的进行要素的一些属性信息查看,要素的操作等等。

下面就分别说一些针对点、线和面的不同形状要素的选取。

点:点的捕捉就是计算点与点之间的距离,为了加快搜索速度,可以设置一个以当前的点为中心,一个合适的距离向四周扩散构成一个正方形进行搜索,然后根据搜索得到的结果集进行距离计算。但是计算距离必然会引起开方根运算,这样肯定会引起计算时间的加长。可以有x和y两个轴方向上的距离绝对值代替距离,只要fabs(y2-y1)<eps并且fabs(x2-x1)<eps就满足搜索的条件。这样就实现了点的捕捉。

线:线的捕捉可以首先理解为点与折线的最短距离的计算。点与折线段的距离可以先分解为点与线段的距离,然后求出这些距离的最小值。这样看起来还像不错,但是效率太低,计算量大,不适合做大规模数据的搜索。现在我们首先看点与线段的距离,也许有人会说,你傻啊,这不是很简单吗,就只要按照点与直线的距离求出距离就可以了吗?很遗憾的告诉你,可惜定义不是这样的。一般的解决办法如下:先求出线段起始点到这点的向量在线段始末点组成的向量上的投影proj,然后根据投影和线段的长度做比较,小于0,直接求出这点与线段起始点的距离作为最近距离。如果0<proj<length(AB),则垂线距离作为最短距离。如果proj> =length(AB),则求出这点与线段终点之间的距离作为最短距离。

代码如下:

double Point2Segment(const OGRPoint &point,OGRPoint& pt0,OGRPoint& pt1)
{
 OGRPoint vecD(pt1.getX()-pt0.getX(),
  pt1.getY()-pt0.getY());  //线段的向量
 OGRPoint vecP(point.getX()-pt0.getX(),point.getY()-pt0.getY());//点到线段起始点的向量
 double valueD = sqrt(vecD.getX()*vecD.getX()+vecD.getY()*vecD.getY());
 double valueP = sqrt(vecP.getX()*vecP.getX()+vecP.getY()*vecP.getY());
 double dotMultiplay = vecD.getX()*vecP.getX()+vecD.getY()*vecP.getY();

 double t = dotMultiplay/valueD;  //计算向量的投影

 //如果线段开始点接近点point
 if (t <= 0)
 {
  return valueP;
 }

 //如果线段结束点接近点point
 if (t >= valueD)
 {
  OGRPoint vecP(point.getX()-pt1.getX(),point.getY()-pt1.getY());
  return sqrt(vecP.getX()*vecP.getX()+vecP.getY()*vecP.getY());
 }

 //返回垂足距离
 return valueP - t*t/valueD;
}

第二步是求出点到所有线段的最小值。这个一次求出然后比较就可以了。可能大部分人会这么干,但我想说的是编程不只是实现功能,还要优化算法以及自己写过的代码。这里可以进行如下的优化:在每一条线段的搜索过程中,记录下上一次记录的最小的距离值,可以以当前点为矩形中心点,以上一次记录的最小距离向四周扩散组成一个矩形,这个矩形我暂且叫它安全矩形,如果某一个线段在这个矩形内或者与这个矩形相交,那么可以进行距离计算。如果不满足条件,则舍弃进入下一条线段的判断。这样就可以省去很多不必要的计算工作。

代码如下:

double Point2LineString(const OGRPoint& point,OGRLineString* poString)
{
 double distance = 65535;
 for (int i = 0; i < poString->getNumPoints()-1; i ++)
 {
  OGRPoint pt0, pt1;
  poString->getPoint(i,&pt0);
  poString->getPoint(i+1,&pt1);

  //此处这个矩形作为搜索的一个工具
  OGREnvelope envSearch;
  envSearch.MinX = point.getX()-distance;
  envSearch.MaxX = point.getX()+distance;
  envSearch.MinY = point.getY()-distance;
  envSearch.MaxY = point.getY()+distance;
  OGREnvelope envSegment; //线段所在的矩形
  envSegment.MinX = min(pt0.getX(),pt1.getX());
  envSegment.MaxX = max(pt0.getX(),pt1.getX());
  envSegment.MinY = min(pt0.getY(),pt1.getY());
  envSegment.MaxY = max(pt0.getY(),pt1.getY());

  //包含在或者与搜索矩形相交的线段才考虑求距离
  if (envSearch.Contains(envSegment) ||
   envSearch.Intersects(envSegment))
  {
   double dist = Point2Segment(point,pt0,pt1);
   if (distance >= dist)
   {
    distance = dist;
   }
  }
 }

 return distance;
}

第三步:根据建立的空间索引进行搜索,找出符号条件的要素,然后再逐个比较距离大小,最后看是否小于阈值,在此需要转换为屏幕距离再作比较。

多边形(面):见我的另一篇博文(点与多边形关系(改进射线法))。

大家还有什么更好的优化方案可以一起进行探讨。


原文链接:http://blog.csdn.net/zhouxuguang236/article/details/9964903
加载中
返回顶部
顶部