Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Added vertex/edge in tolerance queries
  • Loading branch information
wonder-sk committed Jan 20, 2015
1 parent e05de3f commit 81bb124
Show file tree
Hide file tree
Showing 3 changed files with 100 additions and 17 deletions.
63 changes: 55 additions & 8 deletions src/core/qgspointlocator.cpp
Expand Up @@ -302,8 +302,8 @@ class QgsPointLocator_VisitorVertexEdge : public IVisitor
: mLayer( vl ), mVertexTree( vertexTree ), mNNQuery( true ), mOrigPt( origPt ), mList( list ) {}

//! constructor for range queries
QgsPointLocator_VisitorVertexEdge( QgsVectorLayer* vl, bool vertexTree, const QgsRectangle& origRect, QgsPointLocator::MatchList& list )
: mLayer( vl ), mVertexTree( vertexTree ), mNNQuery( false ), mOrigRect( origRect ), mList( list ) {}
QgsPointLocator_VisitorVertexEdge( QgsVectorLayer* vl, bool vertexTree, const QgsRectangle& origRect, QgsPointLocator::MatchList& list, const QgsPoint* distToPoint = 0 )
: mLayer( vl ), mVertexTree( vertexTree ), mNNQuery( false ), mOrigRect( origRect ), mList( list ), mDistToPoint( distToPoint ) {}

void visitNode( const INode& n ) { Q_UNUSED( n ); }
void visitData( std::vector<const IData*>& v ) { Q_UNUSED( v ); }
Expand Down Expand Up @@ -334,9 +334,17 @@ class QgsPointLocator_VisitorVertexEdge : public IVisitor
else
{
// range query
// distance + point do not make sense here... keep them empty
// distance + point make sense only if mDistToPoint is specified
dist = 0;
if ( !mVertexTree )
if ( mVertexTree )
{
if ( mDistToPoint )
{
pt = QgsPoint( dd.m_region.m_pLow[0], dd.m_region.m_pLow[1] );
dist = sqrt( pt.sqrDist( *mDistToPoint ) );
}
}
else
{
// need to check if the edge actually intersects the region
SpatialIndex::Region r( rect2region( mOrigRect ) );
Expand All @@ -347,6 +355,8 @@ class QgsPointLocator_VisitorVertexEdge : public IVisitor
return;
edgePoints[0].set( pStart[0], pStart[1] );
edgePoints[1].set( pEnd[0], pEnd[1] );
if ( mDistToPoint )
dist = sqrt( mDistToPoint->sqrDistToSegment( pStart[0], pStart[1], pEnd[0], pEnd[1], pt ) );
}
}
QgsPointLocator::Type t = mVertexTree ? QgsPointLocator::Vertex : QgsPointLocator::Edge;
Expand All @@ -361,6 +371,7 @@ class QgsPointLocator_VisitorVertexEdge : public IVisitor
QgsPoint mOrigPt; // only for NN queries
QgsRectangle mOrigRect; // only for range queries
QgsPointLocator::MatchList& mList;
const QgsPoint* mDistToPoint; // optionally for range queries
};


Expand Down Expand Up @@ -682,8 +693,34 @@ QgsPointLocator::MatchList QgsPointLocator::nearestEdges( const QgsPoint& point,
return lst;
}

QgsPointLocator::MatchList QgsPointLocator::verticesInTolerance( const QgsPoint& point, double tolerance )
{
QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
MatchList lst = verticesInRect( rect, &point );
// make sure that only matches strictly within the tolerance are returned
// (the intersection with rect may yield matches outside of tolerance)
while ( !lst.isEmpty() && lst.last().distance() > tolerance )
lst.removeLast();
return lst;
}

QgsPointLocator::MatchList QgsPointLocator::edgesInTolerance( const QgsPoint& point, double tolerance )
{
QgsRectangle rect( point.x() - tolerance, point.y() - tolerance, point.x() + tolerance, point.y() + tolerance );
MatchList lst = edgesInRect( rect, &point );
// make sure that only matches strictly within the tolerance are returned
// (the intersection with rect may yield matches outside of tolerance)
while ( !lst.isEmpty() && lst.last().distance() > tolerance )
lst.removeLast();
return lst;
}

static bool matchDistanceLessThan( const QgsPointLocator::Match& m1, const QgsPointLocator::Match& m2 )
{
return m1.distance() < m2.distance();
}

QgsPointLocator::MatchList QgsPointLocator::verticesInRect( const QgsRectangle& rect )
QgsPointLocator::MatchList QgsPointLocator::verticesInRect( const QgsRectangle& rect, const QgsPoint* distToPoint )
{
if ( !mRTreeVertex )
{
Expand All @@ -693,13 +730,18 @@ QgsPointLocator::MatchList QgsPointLocator::verticesInRect( const QgsRectangle&
}

MatchList lst;
QgsPointLocator_VisitorVertexEdge visitor( mLayer, true, rect, lst );
QgsPointLocator_VisitorVertexEdge visitor( mLayer, true, rect, lst, distToPoint );
mRTreeVertex->intersectsWithQuery( rect2region( rect ), visitor );

// if there is no distToPoint, all distances are zero, so no need to sort
if ( distToPoint )
qSort( lst.begin(), lst.end(), matchDistanceLessThan );

return lst;
}


QgsPointLocator::MatchList QgsPointLocator::edgesInRect( const QgsRectangle& rect )
QgsPointLocator::MatchList QgsPointLocator::edgesInRect( const QgsRectangle& rect, const QgsPoint* distToPoint )
{
if ( !mRTreeEdge )
{
Expand All @@ -709,8 +751,13 @@ QgsPointLocator::MatchList QgsPointLocator::edgesInRect( const QgsRectangle& rec
}

MatchList lst;
QgsPointLocator_VisitorVertexEdge visitor( mLayer, false, rect, lst );
QgsPointLocator_VisitorVertexEdge visitor( mLayer, false, rect, lst, distToPoint );
mRTreeEdge->intersectsWithQuery( rect2region( rect ), visitor );

// if there is no distToPoint, all distances are zero, so no need to sort
if ( distToPoint )
qSort( lst.begin(), lst.end(), matchDistanceLessThan );

return lst;
}

Expand Down
21 changes: 13 additions & 8 deletions src/core/qgspointlocator.h
Expand Up @@ -159,14 +159,19 @@ class QgsPointLocator : public QObject

// intersection queries

inline MatchList verticesInRect( const QgsPoint& point, double tolerance )
{
return verticesInRect( QgsRectangle( point.x() - tolerance, point.y() - tolerance,
point.x() + tolerance, point.y() + tolerance ) );
}

MatchList verticesInRect( const QgsRectangle& rect );
MatchList edgesInRect( const QgsRectangle& rect );
//! find nearest vertices to the specified point - sorted by distance
//! will return matches up to distance given by tolerance
MatchList verticesInTolerance( const QgsPoint& point, double tolerance );
//! find nearest edges to the specified point - sorted by distance
//! will return matches up to distance given by tolerance
MatchList edgesInTolerance( const QgsPoint& point, double tolerance );

//! find vertices within given rectangle
//! if distToPoint is given, the matches will be sorted by distance to that point
MatchList verticesInRect( const QgsRectangle& rect, const QgsPoint* distToPoint = 0 );
//! find edges within given rectangle
//! if distToPoint is given, the matches will be sorted by distance to that point
MatchList edgesInRect( const QgsRectangle& rect, const QgsPoint* distToPoint = 0 );

// point-in-polygon query

Expand Down
33 changes: 32 additions & 1 deletion tests/src/core/testqgspointlocator.cpp
Expand Up @@ -112,7 +112,38 @@ class TestQgsPointLocator : public QObject
QCOMPARE( mInvalid.count(), 0 );
}

// TODO: intersection tests
void testVerticesInTolerance()
{
QgsPointLocator loc( mVL );
QgsPointLocator::MatchList lst = loc.verticesInTolerance( QgsPoint( 1, 0 ), 2 );
QCOMPARE( lst.count(), 4 );
QCOMPARE( lst[0].point(), QgsPoint( 1, 0 ) );
QCOMPARE( lst[0].distance(), 0. );
QCOMPARE( lst[1].point(), QgsPoint( 1, 1 ) );
QCOMPARE( lst[1].distance(), 1. );
QCOMPARE( lst[2].point(), QgsPoint( 0, 1 ) );
QCOMPARE( lst[2].distance(), sqrt( 2 ) );

QgsPointLocator::MatchList lst2 = loc.verticesInTolerance( QgsPoint( 1, 0 ), 1 );
QCOMPARE( lst2.count(), 2 );
}

void testEdgesInTolerance()
{
QgsPointLocator loc( mVL );
QgsPointLocator::MatchList lst = loc.edgesInTolerance( QgsPoint( 0, 0 ), 2 );
QCOMPARE( lst.count(), 3 );
QCOMPARE( lst[0].point(), QgsPoint( 0.5, 0.5 ) );
QCOMPARE( lst[0].distance(), sqrt( 2 ) / 2 );
QVERIFY( lst[1].point() == QgsPoint( 0, 1 ) || lst[1].point() == QgsPoint( 1, 0 ) );
QCOMPARE( lst[1].distance(), 1. );
QVERIFY( lst[2].point() == QgsPoint( 0, 1 ) || lst[2].point() == QgsPoint( 1, 0 ) );
QCOMPARE( lst[2].distance(), 1. );

QgsPointLocator::MatchList lst2 = loc.edgesInTolerance( QgsPoint( 0, 0 ), 0.9 );
QCOMPARE( lst2.count(), 1 );
}


void testLayerUpdates()
{
Expand Down

0 comments on commit 81bb124

Please sign in to comment.