Quantum GIS API Documentation  1.8
src/analysis/network/qgslinevectorlayerdirector.cpp
Go to the documentation of this file.
```00001 /***************************************************************************
00002  *   Copyright (C) 2010 by Sergey Yakushev                                 *
00003  *   yakushevs <at> list.ru                                                *
00004  *                                                                         *
00005  *                                                                         *
00006  *   This program is free software; you can redistribute it and/or modify  *
00008  *   the Free Software Foundation; either version 2 of the License, or     *
00009  *   (at your option) any later version.                                   *
00010  ***************************************************************************/
00011
00017 #include "qgslinevectorlayerdirector.h"
00018 #include "qgsgraphbuilderintr.h"
00019
00020 // Qgis includes
00021 #include <qgsvectorlayer.h>
00022 #include <qgsvectordataprovider.h>
00023 #include <qgspoint.h>
00024 #include <qgsgeometry.h>
00025 #include <qgsdistancearea.h>
00026
00027 // QT includes
00028 #include <QString>
00029 #include <QtAlgorithms>
00030
00031 //standard includes
00032 #include <limits>
00033 #include <algorithm>
00034
00035 class QgsPointCompare
00036 {
00037   public:
00038     QgsPointCompare( double tolerance ) :
00039         mTolerance( tolerance )
00040     {  }
00041
00042     bool operator()( const QgsPoint& p1, const QgsPoint& p2 ) const
00043     {
00044       if ( mTolerance <= 0 )
00045         return p1.x() == p2.x() ? p1.y() < p2.y() : p1.x() < p2.x();
00046
00047       double tx1 = ceil( p1.x() / mTolerance );
00048       double tx2 = ceil( p2.x() / mTolerance );
00049       if ( tx1 == tx2 )
00050         return ceil( p1.y() / mTolerance ) < ceil( p2.y() / mTolerance );
00051       return tx1 < tx2;
00052     }
00053
00054   private:
00055     double mTolerance;
00056 };
00057
00058 template <typename RandIter, typename Type, typename CompareOp > RandIter my_binary_search( RandIter begin, RandIter end, Type val, CompareOp comp )
00059 {
00061   RandIter not_found = end;
00062
00063   while ( true )
00064   {
00065     RandIter avg = begin + ( end - begin ) / 2;
00066     if ( begin == avg || end == avg )
00067     {
00068       if ( !comp( *begin, val ) && !comp( val, *begin ) )
00069         return begin;
00070       if ( !comp( *end, val ) && !comp( val, *end ) )
00071         return end;
00072
00073       return not_found;
00074     }
00075     if ( comp( val, *avg ) )
00076       end = avg;
00077     else if ( comp( *avg, val ) )
00078       begin = avg;
00079     else
00080       return avg;
00081   }
00082
00083   return not_found;
00084 }
00085
00086 struct TiePointInfo
00087 {
00088   QgsPoint mTiedPoint;
00089   double mLength;
00090   QgsPoint mFirstPoint;
00091   QgsPoint mLastPoint;
00092 };
00093
00094 bool TiePointInfoCompare( const TiePointInfo& a, const TiePointInfo& b )
00095 {
00096   if ( a.mFirstPoint == b.mFirstPoint )
00097     return a.mLastPoint.x() == b.mLastPoint.x() ? a.mLastPoint.y() < b.mLastPoint.y() : a.mLastPoint.x() < b.mLastPoint.x();
00098
00099   return a.mFirstPoint.x() == b.mFirstPoint.x() ? a.mFirstPoint.y() < b.mFirstPoint.y() : a.mFirstPoint.x() < b.mFirstPoint.x();
00100 }
00101
00102 QgsLineVectorLayerDirector::QgsLineVectorLayerDirector( QgsVectorLayer *myLayer,
00103     int directionFieldId,
00104     const QString& directDirectionValue,
00105     const QString& reverseDirectionValue,
00106     const QString& bothDirectionValue,
00107     int defaultDirection
00108                                                       )
00109 {
00110   mVectorLayer            = myLayer;
00111   mDirectionFieldId       = directionFieldId;
00112   mDirectDirectionValue   = directDirectionValue;
00113   mReverseDirectionValue  = reverseDirectionValue;
00114   mDefaultDirection       = defaultDirection;
00115   mBothDirectionValue     = bothDirectionValue;
00116 }
00117
00118 QgsLineVectorLayerDirector::~QgsLineVectorLayerDirector()
00119 {
00120
00121 }
00122
00123 QString QgsLineVectorLayerDirector::name() const
00124 {
00125   return QString( "Vector line" );
00126 }
00127
00128 void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, const QVector< QgsPoint >& additionalPoints,
00129     QVector< QgsPoint >& tiedPoint ) const
00130 {
00131   QgsVectorLayer *vl = mVectorLayer;
00132
00133   if ( vl == NULL )
00134     return;
00135
00136   int featureCount = ( int ) vl->featureCount() * 2;
00137   int step = 0;
00138
00139   QgsCoordinateTransform ct;
00140   ct.setSourceCrs( vl->crs() );
00141   if ( builder->coordinateTransformationEnabled() )
00142   {
00143     ct.setDestCRS( builder->destinationCrs() );
00144   }
00145   else
00146   {
00147     ct.setDestCRS( vl->crs() );
00148   }
00149
00150   tiedPoint = QVector< QgsPoint >( additionalPoints.size(), QgsPoint( 0.0, 0.0 ) );
00151
00152   TiePointInfo tmpInfo;
00153   tmpInfo.mLength = std::numeric_limits<double>::infinity();
00154
00155   QVector< TiePointInfo > pointLengthMap( additionalPoints.size(), tmpInfo );
00156   QVector< TiePointInfo >::iterator pointLengthIt;
00157
00158   //Graph's points;
00159   QVector< QgsPoint > points;
00160
00161   // begin: tie points to the graph
00162   QgsAttributeList la;
00163   vl->select( la );
00164   QgsFeature feature;
00165   while ( vl->nextFeature( feature ) )
00166   {
00167     QgsMultiPolyline mpl;
00168     if ( feature.geometry()->wkbType() == QGis::WKBMultiLineString )
00169       mpl = feature.geometry()->asMultiPolyline();
00170     else if ( feature.geometry()->wkbType() == QGis::WKBLineString )
00171       mpl.push_back( feature.geometry()->asPolyline() );
00172
00173     QgsMultiPolyline::iterator mplIt;
00174     for ( mplIt = mpl.begin(); mplIt != mpl.end(); ++mplIt )
00175     {
00176       QgsPoint pt1, pt2;
00177       bool isFirstPoint = true;
00178       QgsPolyline::iterator pointIt;
00179       for ( pointIt = mplIt->begin(); pointIt != mplIt->end(); ++pointIt )
00180       {
00181         pt2 = ct.transform( *pointIt );
00182         points.push_back( pt2 );
00183
00184         if ( !isFirstPoint )
00185         {
00186           int i = 0;
00187           for ( i = 0; i != additionalPoints.size(); ++i )
00188           {
00189             TiePointInfo info;
00190             if ( pt1 == pt2 )
00191             {
00192               info.mLength = additionalPoints[ i ].sqrDist( pt1 );
00193               info.mTiedPoint = pt1;
00194             }
00195             else
00196             {
00197               info.mLength = additionalPoints[ i ].sqrDistToSegment( pt1.x(), pt1.y(),
00198                              pt2.x(), pt2.y(), info.mTiedPoint );
00199             }
00200
00201             if ( pointLengthMap[ i ].mLength > info.mLength )
00202             {
00203               info.mTiedPoint = info.mTiedPoint ;
00204               info.mFirstPoint = pt1;
00205               info.mLastPoint = pt2;
00206
00207               pointLengthMap[ i ] = info;
00208               tiedPoint[ i ] = info.mTiedPoint;
00209             }
00210           }
00211         }
00212         pt1 = pt2;
00213         isFirstPoint = false;
00214       }
00215     }
00216     emit buildProgress( ++step, featureCount );
00217   }
00218   // end: tie points to graph
00219
00220   // add tied point to graph
00221   int i = 0;
00222   for ( i = 0; i < tiedPoint.size(); ++i )
00223   {
00224     if ( tiedPoint[ i ] != QgsPoint( 0.0, 0.0 ) )
00225     {
00226       points.push_back( tiedPoint [ i ] );
00227     }
00228   }
00229
00230   QgsPointCompare pointCompare( builder->topologyTolerance() );
00231
00232   qSort( points.begin(), points.end(), pointCompare );
00233   QVector< QgsPoint >::iterator tmp = std::unique( points.begin(), points.end() );
00234   points.resize( tmp - points.begin() );
00235
00236
00237   for ( i = 0;i < points.size();++i )
00238     builder->addVertex( i, points[ i ] );
00239
00240   for ( i = 0; i < tiedPoint.size() ; ++i )
00241     tiedPoint[ i ] = *( my_binary_search( points.begin(), points.end(), tiedPoint[ i ], pointCompare ) );
00242
00243   qSort( pointLengthMap.begin(), pointLengthMap.end(), TiePointInfoCompare );
00244
00245   { // fill attribute list 'la'
00246     QgsAttributeList tmpAttr;
00247     if ( mDirectionFieldId != -1 )
00248     {
00249       tmpAttr.push_back( mDirectionFieldId );
00250     }
00251
00252     QList< QgsArcProperter* >::const_iterator it;
00253     QgsAttributeList::const_iterator it2;
00254
00255     for ( it = mProperterList.begin(); it != mProperterList.end(); ++it )
00256     {
00257       QgsAttributeList tmp = ( *it )->requiredAttributes();
00258       for ( it2 = tmp.begin(); it2 != tmp.end(); ++it2 )
00259       {
00260         tmpAttr.push_back( *it2 );
00261       }
00262     }
00263     qSort( tmpAttr.begin(), tmpAttr.end() );
00264
00265     int lastAttrId = -1;
00266     for ( it2 = tmpAttr.begin(); it2 != tmpAttr.end(); ++it2 )
00267     {
00268       if ( *it2 == lastAttrId )
00269       {
00270         continue;
00271       }
00272
00273       la.push_back( *it2 );
00274
00275       lastAttrId = *it2;
00276     }
00277   } // end fill attribute list 'la'
00278
00279   // begin graph construction
00280   vl->select( la );
00281   while ( vl->nextFeature( feature ) )
00282   {
00283     QgsAttributeMap attr = feature.attributeMap();
00284     int directionType = mDefaultDirection;
00285     QgsAttributeMap::const_iterator it;
00286     // What direction have feature?
00287     for ( it = attr.constBegin(); it != attr.constEnd(); ++it )
00288     {
00289       if ( it.key() != mDirectionFieldId )
00290       {
00291         continue;
00292       }
00293       QString str = it.value().toString();
00294       if ( str == mBothDirectionValue )
00295       {
00296         directionType = 3;
00297       }
00298       else if ( str == mDirectDirectionValue )
00299       {
00300         directionType = 1;
00301       }
00302       else if ( str == mReverseDirectionValue )
00303       {
00304         directionType = 2;
00305       }
00306     }
00307
00308     // begin features segments and add arc to the Graph;
00309     QgsMultiPolyline mpl;
00310     if ( feature.geometry()->wkbType() == QGis::WKBMultiLineString )
00311       mpl = feature.geometry()->asMultiPolyline();
00312     else if ( feature.geometry()->wkbType() == QGis::WKBLineString )
00313       mpl.push_back( feature.geometry()->asPolyline() );
00314
00315     QgsMultiPolyline::iterator mplIt;
00316     for ( mplIt = mpl.begin(); mplIt != mpl.end(); ++mplIt )
00317     {
00318       QgsPoint pt1, pt2;
00319
00320       bool isFirstPoint = true;
00321       QgsPolyline::iterator pointIt;
00322       for ( pointIt = mplIt->begin(); pointIt != mplIt->end(); ++pointIt )
00323       {
00324         pt2 = ct.transform( *pointIt );
00325
00326         if ( !isFirstPoint )
00327         {
00328           std::map< double, QgsPoint > pointsOnArc;
00329           pointsOnArc[ 0.0 ] = pt1;
00330           pointsOnArc[ pt1.sqrDist( pt2 )] = pt2;
00331
00332           TiePointInfo t;
00333           t.mFirstPoint = pt1;
00334           t.mLastPoint  = pt2;
00335           pointLengthIt = my_binary_search( pointLengthMap.begin(), pointLengthMap.end(), t, TiePointInfoCompare );
00336
00337           if ( pointLengthIt != pointLengthMap.end() )
00338           {
00339             QVector< TiePointInfo >::iterator it;
00340             for ( it = pointLengthIt; it - pointLengthMap.begin() >= 0; --it )
00341             {
00342               if ( it->mFirstPoint == pt1 && it->mLastPoint == pt2 )
00343               {
00344                 pointsOnArc[ pt1.sqrDist( it->mTiedPoint )] = it->mTiedPoint;
00345               }
00346             }
00347             for ( it = pointLengthIt + 1; it != pointLengthMap.end(); ++it )
00348             {
00349               if ( it->mFirstPoint == pt1 && it->mLastPoint == pt2 )
00350               {
00351                 pointsOnArc[ pt1.sqrDist( it->mTiedPoint )] = it->mTiedPoint;
00352               }
00353             }
00354           }
00355
00356           std::map< double, QgsPoint >::iterator pointsIt;
00357           QgsPoint pt1;
00358           QgsPoint pt2;
00359           int pt1idx = -1, pt2idx = -1;
00360           bool isFirstPoint = true;
00361           for ( pointsIt = pointsOnArc.begin(); pointsIt != pointsOnArc.end(); ++pointsIt )
00362           {
00363             pt2 = pointsIt->second;
00364             tmp = my_binary_search( points.begin(), points.end(), pt2, pointCompare );
00365             pt2 = *tmp;
00366             pt2idx = tmp - points.begin();
00367
00368             if ( !isFirstPoint && pt1 != pt2 )
00369             {
00370               double distance = builder->distanceArea()->measureLine( pt1, pt2 );
00371               QVector< QVariant > prop;
00372               QList< QgsArcProperter* >::const_iterator it;
00373               for ( it = mProperterList.begin(); it != mProperterList.end(); ++it )
00374               {
00375                 prop.push_back(( *it )->property( distance, feature ) );
00376               }
00377
00378               if ( directionType == 1 ||
00379                    directionType == 3 )
00380               {
00381                 builder->addArc( pt1idx, pt1, pt2idx, pt2, prop );
00382               }
00383               if ( directionType == 2 ||
00384                    directionType == 3 )
00385               {
00386                 builder->addArc( pt2idx, pt2, pt1idx, pt1, prop );
00387               }
00388             }
00389             pt1idx = pt2idx;
00390             pt1 = pt2;
00391             isFirstPoint = false;
00392           }
00393         } // if ( !isFirstPoint )
00394         pt1 = pt2;
00395         isFirstPoint = false;
00396       } // for (it = pl.begin(); it != pl.end(); ++it)
00397     }
00398     emit buildProgress( ++step, featureCount );
00399   } // while( vl->nextFeature(feature) )
00400 } // makeGraph( QgsGraphBuilderInterface *builder, const QVector< QgsPoint >& additionalPoints, QVector< QgsPoint >& tiedPoint )
00401
```