Skip to content

Commit 6e0435a

Browse files
stopa85milkstopa85milk
committedMay 31, 2011
1. Use real builder-director pattern.
2. Replase QMap container to QVector, sort and bynary search. RAM saving at the same perfomance.
·
ltr-3_40Before-merge-new_vector_api
1 parent fc3104f commit 6e0435a

File tree

5 files changed

+108
-71
lines changed

5 files changed

+108
-71
lines changed
 

‎src/analysis/network/qgsgraphbuilder.cpp

Lines changed: 4 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -33,40 +33,14 @@ QgsGraphBuilder::~QgsGraphBuilder()
3333
delete mGraph;
3434
}
3535

36-
QgsPoint QgsGraphBuilder::addVertex( const QgsPoint& pt )
36+
void QgsGraphBuilder::addVertex( int, const QgsPoint& pt )
3737
{
38-
int id = pointId( pt );
39-
if ( id != -1 )
40-
return mGraph->vertex( id ).point();
41-
42-
QgsPoint newPoint = pt;
43-
if ( topologyTolerance() > 0 )
44-
{
45-
newPoint = QgsPoint( ceil( pt.x() / topologyTolerance() ),
46-
ceil( pt.y() / topologyTolerance() ) );
47-
}
48-
int newId = mGraph->addVertex( pt );
49-
50-
mPointMap[ newPoint ] = newId;
51-
return pt;
38+
mGraph->addVertex( pt );
5239
}
5340

54-
void QgsGraphBuilder::addArc( const QgsPoint& pt1, const QgsPoint& pt2, const QVector< QVariant >& prop )
41+
void QgsGraphBuilder::addArc( int pt1id, const QgsPoint&, int pt2id, const QgsPoint&, const QVector< QVariant >& prop )
5542
{
56-
int pt1_id = pointId( pt1 );
57-
int pt2_id = pointId( pt2 );
58-
if ( pt1_id == -1 )
59-
{
60-
// FIXME to QgsDebug
61-
std::cerr << "haven't vertex at (" << pt1.x() << ";" << pt1.y() << ")\n";
62-
return;
63-
}
64-
if ( pt2_id == -1 )
65-
{
66-
std::cerr << "haven't vertex at (" << pt2.x() << ";" << pt2.y() << ")\n";
67-
return;
68-
}
69-
mGraph->addEdge( pt1_id, pt2_id, prop );
43+
mGraph->addEdge( pt1id, pt2id, prop );
7044
}
7145

7246
QgsGraph* QgsGraphBuilder::graph()
@@ -75,21 +49,3 @@ QgsGraph* QgsGraphBuilder::graph()
7549
mGraph = NULL;
7650
return res;
7751
}
78-
79-
int QgsGraphBuilder::pointId( const QgsPoint& pt )
80-
{
81-
QgsPoint findPoint = pt;
82-
if ( topologyTolerance() > 0.0 )
83-
{
84-
findPoint = QgsPoint( ceil( pt.x() / topologyTolerance() ),
85-
ceil( pt.y() / topologyTolerance() ) ) ;
86-
}
87-
88-
std::map< QgsPoint, int, QgsPointCompare >::iterator it = mPointMap.find( findPoint );
89-
if ( it != mPointMap.end() )
90-
{
91-
return it->second;
92-
}
93-
94-
return -1;
95-
}

‎src/analysis/network/qgsgraphbuilder.h

Lines changed: 2 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -60,22 +60,16 @@ class ANALYSIS_EXPORT QgsGraphBuilder : public QgsGraphBuilderInterface
6060
/*
6161
* MANDATORY BUILDER PROPERTY DECLARATION
6262
*/
63-
virtual QgsPoint addVertex( const QgsPoint& pt );
63+
virtual void addVertex( int id, const QgsPoint& pt );
6464

65-
virtual void addArc( const QgsPoint& pt1, const QgsPoint& pt2, const QVector< QVariant >& prop );
65+
virtual void addArc( int pt1id, const QgsPoint& pt1, int pt2id, const QgsPoint& pt2, const QVector< QVariant >& prop );
6666

6767
/**
6868
* return QgsGraph result;
6969
*/
7070
QgsGraph* graph();
7171

7272
private:
73-
// return -1 if pt not found
74-
int pointId( const QgsPoint& pt );
75-
76-
QgsSpatialIndex mPointIndex;
77-
78-
std::map< QgsPoint, int, QgsPointCompare > mPointMap;
7973

8074
QgsGraph *mGraph;
8175
};

‎src/analysis/network/qgsgraphbuilderintr.h

Lines changed: 18 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -77,12 +77,25 @@ class ANALYSIS_EXPORT QgsGraphBuilderInterface
7777
return &mDa;
7878
}
7979

80-
//! add vertex
81-
virtual QgsPoint addVertex( const QgsPoint& pt )
82-
{ return pt; }
80+
/**
81+
* add vertex
82+
* @param id vertex identyficator
83+
* @param pt vertex coordinate
84+
* @note id and pt is a redundant interface. You can use coordinates or id for vertex identyfy
85+
*/
86+
virtual void addVertex( int id, const QgsPoint& pt )
87+
{ }
8388

84-
//! add arc
85-
virtual void addArc( const QgsPoint& pt1, const QgsPoint& pt2, const QVector< QVariant >& properties )
89+
/**
90+
* add arc
91+
* @param pt1id first vertex identificator
92+
* @param pt1 first vertex coordinate
93+
* @param pt2id second vertex identificator
94+
* @param pt2 second vertex coordinate
95+
* @param properties arc properties
96+
* @note pt1id, pt1 and pt2id, pt2 is a redundant interface. You can use vertex coordinates or their identificators.
97+
*/
98+
virtual void addArc( int pt1id, const QgsPoint& pt1, int pt2id, const QgsPoint& pt2, const QVector< QVariant >& properties )
8699
{ }
87100

88101
private:

‎src/analysis/network/qgslinevectorlayerdirector.cpp

Lines changed: 83 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,58 @@
3131

3232
//standard includes
3333
#include <limits>
34+
#include <algorithm>
35+
36+
class QgsPointCompare
37+
{
38+
public:
39+
QgsPointCompare( double tolerance ) :
40+
mTolerance( tolerance )
41+
{ }
42+
43+
bool operator()( const QgsPoint& p1, const QgsPoint& p2 ) const
44+
{
45+
if ( mTolerance <= 0 )
46+
return p1.x() == p2.x() ? p1.y() < p2.y() : p1.x() < p2.x();
47+
48+
double tx1 = ceil( p1.x()/mTolerance );
49+
double tx2 = ceil( p2.x()/mTolerance );
50+
if ( tx1 == tx2 )
51+
return ceil( p1.y()/mTolerance ) < ceil( p2.y()/mTolerance );
52+
return tx1 < tx2;
53+
}
54+
55+
private:
56+
double mTolerance;
57+
};
58+
59+
template <typename RandIter, typename Type, typename CompareOp > RandIter my_binary_search( RandIter begin, RandIter end, Type val, CompareOp comp)
60+
{
61+
// result if not found
62+
RandIter not_found = end;
63+
64+
while ( true )
65+
{
66+
RandIter avg = begin + (end-begin)/2;
67+
if ( begin == avg || end == avg )
68+
{
69+
if ( !comp( *begin, val ) && !comp( val, *begin ) )
70+
return begin;
71+
if ( !comp( *end, val ) && !comp( val, *end ) )
72+
return end;
73+
74+
return not_found;
75+
}
76+
if ( comp( val, *avg ) )
77+
end = avg;
78+
else if ( comp( *avg, val ) )
79+
begin = avg;
80+
else
81+
return avg;
82+
}
83+
84+
return not_found;
85+
}
3486

3587
QgsLineVectorLayerDirector::QgsLineVectorLayerDirector( const QString& layerId,
3688
int directionFieldId,
@@ -80,12 +132,16 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
80132
}
81133

82134
tiedPoint = QVector< QgsPoint >( additionalPoints.size(), QgsPoint( 0.0, 0.0 ) );
135+
83136
TiePointInfo tmpInfo;
84137
tmpInfo.mLength = std::numeric_limits<double>::infinity();
85138

86139
QVector< TiePointInfo > pointLengthMap( additionalPoints.size(), tmpInfo );
87140
QVector< TiePointInfo >::iterator pointLengthIt;
88141

142+
//Graph's points;
143+
QVector< QgsPoint > points;
144+
89145
// begin: tie points to the graph
90146
QgsAttributeList la;
91147
vl->select( la );
@@ -98,7 +154,9 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
98154
QgsPolyline::iterator pointIt;
99155
for ( pointIt = pl.begin(); pointIt != pl.end(); ++pointIt )
100156
{
101-
pt2 = builder->addVertex( ct.transform( *pointIt ) );
157+
pt2 = ct.transform( *pointIt );
158+
points.push_back( pt2 );
159+
102160
if ( !isFirstPoint )
103161
{
104162
int i = 0;
@@ -131,7 +189,6 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
131189
}
132190
emit buildProgress( ++step, featureCount );
133191
}
134-
135192
// end: tie points to graph
136193

137194
// add tied point to graph
@@ -140,10 +197,21 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
140197
{
141198
if ( tiedPoint[ i ] != QgsPoint( 0.0, 0.0 ) )
142199
{
143-
tiedPoint[ i ] = builder->addVertex( tiedPoint[ i ] );
144-
pointLengthMap[ i ].mTiedPoint = tiedPoint[ i ];
200+
points.push_back( tiedPoint [ i ] );
145201
}
146202
}
203+
204+
QgsPointCompare pointCompare( builder->topologyTolerance() );
205+
206+
qSort( points.begin(), points.end(), pointCompare );
207+
QVector< QgsPoint >::iterator tmp = std::unique( points.begin(), points.end() );
208+
points.resize( tmp - points.begin() );
209+
210+
for (i=0;i<points.size();++i)
211+
builder->addVertex( i, points[ i ] );
212+
213+
for ( i = 0; i < tiedPoint.size() ; ++i)
214+
tiedPoint[ i ] = *(my_binary_search( points.begin(), points.end(), tiedPoint[ i ], pointCompare ) );
147215

148216
{ // fill attribute list 'la'
149217
QgsAttributeList tmpAttr;
@@ -216,10 +284,10 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
216284
QgsPolyline::iterator pointIt;
217285
for ( pointIt = pl.begin(); pointIt != pl.end(); ++pointIt )
218286
{
219-
pt2 = builder->addVertex( ct.transform( *pointIt ) );
287+
pt2 = ct.transform( *pointIt );
288+
220289
if ( !isFirstPoint )
221290
{
222-
223291
std::map< double, QgsPoint > pointsOnArc;
224292
pointsOnArc[ 0.0 ] = pt1;
225293
pointsOnArc[ pt1.sqrDist( pt2 )] = pt2;
@@ -236,11 +304,16 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
236304
std::map< double, QgsPoint >::iterator pointsIt;
237305
QgsPoint pt1;
238306
QgsPoint pt2;
307+
int pt1idx = -1, pt2idx = -1;
239308
bool isFirstPoint = true;
240309
for ( pointsIt = pointsOnArc.begin(); pointsIt != pointsOnArc.end(); ++pointsIt )
241310
{
242311
pt2 = pointsIt->second;
243-
if ( !isFirstPoint )
312+
tmp = my_binary_search( points.begin(), points.end(), pt2, pointCompare );
313+
pt2 = *tmp;
314+
pt2idx = tmp - points.begin();
315+
316+
if ( !isFirstPoint && pt1 != pt2 )
244317
{
245318
double distance = builder->distanceArea()->measureLine( pt1, pt2 );
246319
QVector< QVariant > prop;
@@ -253,14 +326,15 @@ void QgsLineVectorLayerDirector::makeGraph( QgsGraphBuilderInterface *builder, c
253326
if ( directionType == 1 ||
254327
directionType == 3 )
255328
{
256-
builder->addArc( pt1, pt2, prop );
329+
builder->addArc( pt1idx, pt1, pt2idx, pt2, prop );
257330
}
258331
if ( directionType == 2 ||
259332
directionType == 3 )
260333
{
261-
builder->addArc( pt2, pt1, prop );
334+
builder->addArc( pt2idx, pt2, pt1idx, pt1, prop );
262335
}
263336
}
337+
pt1idx = pt2idx;
264338
pt1 = pt2;
265339
isFirstPoint = false;
266340
}

‎src/plugins/roadgraph/shortestpathwidget.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -282,7 +282,7 @@ bool RgShortestPathWidget::getPath( QgsGraph* shortestTree, QgsPoint& p1, QgsPoi
282282
QVector< double > pointCost(0,0.0);
283283

284284
int startVertexIdx = graph->findVertex( p1 );
285-
std::cout << " startVertexIdx " << startVertexIdx << "\n";
285+
286286
int criterionNum = 0;
287287
if ( mCriterionName->currentIndex() > 0 )
288288
criterionNum = 1;

0 commit comments

Comments
 (0)
Please sign in to comment.