Point locator: Use just one R-tree for indexing instead of three R-trees

The maintenance of three R-trees was too complicated, using a lot of memory and the performance benefit was questionable :) The approach with just one R-tree leads to much simpler code Removed k-NN queries in the process - they were not used in QGIS code. They can be reintroduced later, but there is not much use for them right now...
qgis · Jan 20, 2015 · dbe830b · dbe830b
1 parent 0ea6a3d
commit dbe830b
Show file tree

Hide file tree

Showing 5 changed files with 557 additions and 666 deletions.
diff --git a/python/core/qgspointlocator.sip b/python/core/qgspointlocator.sip
@@ -16,13 +16,8 @@ class QgsPointLocator : QObject
 
     enum Type { Invalid, Vertex, Edge, Area, All };
 
-    /** Prepare the indexes for given or-ed combination of query types (Vertex, Edge, Area).
-     *  If not initialized explicitly, index of particular type will be inited when first such query is issued.
-     */
-    void init( int types = All, bool force = false );
-
-    //! check whether index for given query type exists
-    bool hasIndex( Type t ) const;
+    /** Prepare the index for queries. Does nothing if the index already exists */
+    void init();
 
     struct Match
     {
@@ -54,8 +49,6 @@ class QgsPointLocator : QObject
 
       QgsFeatureId featureId() const;
 
-      void replaceIfBetter( const QgsPointLocator::Match& m, double maxDistance );
-
       //! Only for a valid edge match - obtain endpoints of the edge
       void edgePoints( QgsPoint& pt1 /Out/, QgsPoint& pt2 /Out/ ) const;
     };
@@ -70,41 +63,19 @@ class QgsPointLocator : QObject
       virtual bool acceptMatch( const QgsPointLocator::Match& match ) = 0;
     };
 
-    // 1-NN queries
-
-    //! find nearest vertex to the specified point
-    QgsPointLocator::Match nearestVertex( const QgsPoint& point );
-
-    //! find nearest edge to the specified point
-    QgsPointLocator::Match nearestEdge( const QgsPoint& point );
-
-    // k-NN queries
-
-    //! find nearest vertices to the specified point - sorted by distance
-    //! will return up to maxMatches matches
-    MatchList nearestVertices( const QgsPoint& point, int maxMatches );
-    //! find nearest edges to the specified point - sorted by distance
-    MatchList nearestEdges( const QgsPoint& point, int maxMatches );
-
     // intersection queries
 
-    //! Find nearest vertices to the specified point - sorted by distance.
-    //! Will return matches up to distance given by tolerance.
+    //! Find nearest vertex to the specified point - up to distance specified by tolerance
     //! Optional filter may discard unwanted matches.
-    MatchList verticesInTolerance( const QgsPoint& point, double tolerance, QgsPointLocator::MatchFilter* filter = 0 );
-    //! Find nearest edges to the specified point - sorted by distance.
-    //! Will return matches up to distance given by tolerance.
-    //! Optional filter may discard unwanted matches.
-    MatchList edgesInTolerance( const QgsPoint& point, double tolerance, QgsPointLocator::MatchFilter* filter = 0 );
-
-    //! Find vertices within given rectangle.
-    //! If distToPoint is given, the matches will be sorted by distance to that point.
+    Match nearestVertex( const QgsPoint& point, double tolerance, QgsPointLocator::MatchFilter* filter = 0 );
+    //! Find nearest edges to the specified point - up to distance specified by tolerance
     //! Optional filter may discard unwanted matches.
-    MatchList verticesInRect( const QgsRectangle& rect, const QgsPoint* distToPoint = 0, QgsPointLocator::MatchFilter* filter = 0 );
-    //! Find edges within given rectangle.
-    //! If distToPoint is given, the matches will be sorted by distance to that point.
+    Match nearestEdge( const QgsPoint& point, double tolerance, QgsPointLocator::MatchFilter* filter = 0 );
+    //! Find edges within a specified recangle
     //! Optional filter may discard unwanted matches.
-    MatchList edgesInRect( const QgsRectangle& rect, const QgsPoint* distToPoint = 0, QgsPointLocator::MatchFilter* filter = 0 );
+    MatchList edgesInRect( const QgsRectangle& rect, QgsPointLocator::MatchFilter* filter = 0 );
+    //! Override of edgesInRect that construct rectangle from a center point and tolerance
+    MatchList edgesInRect( const QgsPoint& point, double tolerance, QgsPointLocator::MatchFilter* filter = 0 );
 
     // point-in-polygon query