Adding upstream version 1.3.upstream/1.3upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 361 insertions, 0 deletions

diff --git a/tests/rtree-performance-test.cpp b/tests/rtree-performance-test.cpp
new file mode 100644
index 0000000..cf4bcd7
--- /dev/null
+++ b/tests/rtree-performance-test.cpp
@@ -0,0 +1,361 @@
+/*
+ * Copyright 2010  Evangelos Katsikaros <vkatsikaros at yahoo dot gr>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+#include <2geom/toys/toy-framework-2.h>
+
+#include <sstream>
+#include <getopt.h>
+
+#include <SpatialIndex.h>
+#include <glib.h>
+//#include <glib/gtypes.h>
+
+using namespace Geom;
+
+// cmd argument stuff
+char* arg_area_limit = NULL;
+bool arg_area_limit_set = false;
+bool arg_debug = false;
+
+int limit = 0;
+
+// spatial index ID management
+SpatialIndex::id_type indexID;
+
+// list of rectangles
+GList *items = NULL;
+
+// tree of rectangles
+SpatialIndex::ISpatialIndex *tree;
+
+SpatialIndex::id_type test_indexID;
+
+void add_rectangle( int x, int y );
+
+/* Simple Visitor used to search the tree. When Data is encountered
+ * we are supposed to call the render function of the Data
+ * */
+class SearchVisitor : public SpatialIndex::IVisitor {
+public:
+        
+    void visitNode(const SpatialIndex::INode& n){
+    }
+            
+    void visitData(const SpatialIndex::IData& d){
+        /* this prototype: do nothing
+         * otherwise, render on buffer
+         * */
+    }
+        
+    void visitData(std::vector<const SpatialIndex::IData*>& v) {
+    }
+};
+
+
+/* we use the this visitor after each insertion in the tree
+ * The purpose is to validate that everything was stored properly
+ * and test the GList pointer storage. It has no other functional
+ * purpose.
+ * */
+class TestSearchVisitor : public SpatialIndex::IVisitor {
+public:
+        
+    void visitNode(const SpatialIndex::INode& n) {
+    }
+        
+    void visitData(const SpatialIndex::IData& d){
+        if( test_indexID == d.getIdentifier() ){
+            byte* pData = 0;
+            uint32_t cLen = sizeof(GList*);
+            d.getData(cLen, &pData);
+            //do something...
+            GList* gl = reinterpret_cast<GList*>(pData);
+            Geom::Rect *member_data = (Geom::Rect *)gl->data;
+            double lala = member_data->bottom();            
+            std::cout << "   Tree: " << lala << std::endl;
+            
+            delete[] pData;           
+        }
+    }
+        
+    void visitData(std::vector<const SpatialIndex::IData*>& v) {
+    }
+};
+
+
+int main(int argc, char **argv) {
+   
+    int c;
+
+    //--------------------------------------------------------------------------
+    // read cmd options
+    while (1) {
+        static struct option long_options[] =
+            {
+                /* These options set a flag. */
+                /* These options don't set a flag.
+                   We distinguish them by their indices. */
+                {"area-limit",	required_argument,	0, 'l'},
+                {"help",		no_argument,		0, 'h'},
+                {"debug",	no_argument,	0, 'd'},
+                {0, 0, 0, 0}
+            };
+        /* getopt_long stores the option index here. */
+        int option_index = 0;
+    
+        c = getopt_long (argc, argv, "l:h:d",
+                         long_options, &option_index);
+
+        /* Detect the end of the options. */
+        if (c == -1){
+            break;
+        }
+    
+        switch (c)
+        {
+            case 'l':
+                arg_area_limit = optarg;
+                arg_area_limit_set = true;
+                break;
+            case 'h':
+                std::cerr << "Usage:  " << argv[0] << " options\n" << std::endl ;
+                std::cerr << 
+                    "  -l  --area-limit=NUMBER  minimum number in node.\n" <<
+                    "  -d  --debug              Enable debug info (list/tree related).\n" <<
+                    "  -h  --help               Print this help.\n" << std::endl;
+                exit(1);
+                break;
+            case 'd':
+                arg_debug = true;
+                break;                
+            case '?':
+                /* getopt_long already printed an error message. */
+                break;
+        
+            default:
+                abort ();
+        }
+    }
+
+    // use some of the cmd options
+    if(  arg_area_limit_set  ) {
+        std::stringstream s1( arg_area_limit );
+        s1 >> limit;
+    }
+    else {
+        limit = 100;
+    }
+    // end cmd options
+    //--------------------------------------------------------------------------
+
+
+    double plow[2], phigh[2];
+    // spatial index memory storage manager
+    SpatialIndex::IStorageManager *mem_mngr;
+    // initialize spatial indexing stuff
+    mem_mngr = SpatialIndex::StorageManager::createNewMemoryStorageManager();
+    // fillFactor, indexCapacity, leafCapacity, dimensionality=2, variant=R*, indexIdentifier
+    tree = SpatialIndex::RTree::createNewRTree(*mem_mngr, 0.7, 25, 25, 2, SpatialIndex::RTree::RV_RSTAR, indexID);    
+
+    //-------------------------------------------
+    /* generate items. add_rectangle() stores them in both list and tree
+     * add rect every (20, 20).
+     * In area ((0,0), (1000, 1000)) add every (100,100)
+     * */
+    for( int x_coord = -limit; x_coord <= limit; x_coord += 20 ) {
+        for( int y_coord = -limit; y_coord <= limit; y_coord += 20 ) {
+            if( x_coord >= 0 && x_coord <= 1000 &&
+                y_coord >= 0 && y_coord <= 1000 )
+            {
+                if( x_coord % 100 == 0 && y_coord % 100 == 0) {
+                    add_rectangle( x_coord, y_coord );
+                }
+                else{
+                    add_rectangle( x_coord, y_coord );
+                }
+            }
+            else{
+                add_rectangle( x_coord, y_coord );
+            }
+        
+        }
+    }
+    std::cout << "Area of objects: ( -" << limit
+              << ", -" << limit
+              << " ), ( " << limit
+              << ", " << limit
+              << " )" << std::endl;
+    std::cout << "Number of Objects (indexID): " << indexID << std::endl;
+    // std::cout << "GListElements: " << g_list_length << std::endl;
+   
+    //-------------------------------------------
+    // Traverse list
+    Geom::Point sa_start = Point( 0, 0 );
+    Geom::Point sa_end = Point( 1000, 1000 );
+    Geom::Rect search_area = Rect( sa_start, sa_end );
+
+    Timer list_timer;
+    list_timer.ask_for_timeslice();
+    list_timer.start();
+    
+    for (GList *list = items; list; list = list->next) {
+        Geom::Rect *child = (Geom::Rect *)list->data;
+        if ( search_area.intersects( *child ) )
+        {
+            /* this prototype: do nothing
+             * otherwise, render on buffer
+             * */
+        }          
+    }  
+    Timer::Time the_list_time = list_timer.lap();
+    
+    std::cout << std::endl;
+    std::cout << "GList (full scan): " << the_list_time << std::endl;
+    
+    //-------------------------------------------
+    // Search tree - good case
+    Timer tree_timer;
+    tree_timer.ask_for_timeslice();
+    tree_timer.start();
+
+    /* We search only the (0,0), (1000, 1000) where the items are less dense.
+     * We expect a good performance versus the list
+     * */
+    // TODO IMPORTANT !!! check the plow, phigh
+    // plow[0] = x1; plow[1] = y1;
+    // phigh[0] = x2; phigh[1] = y2;
+
+    plow[0] = 0;
+    plow[1] = 0;
+    phigh[0] = 1000;
+    phigh[1] = 1000;
+    
+    SpatialIndex::Region search_region = SpatialIndex::Region(plow, phigh, 2);
+    SearchVisitor vis = SearchVisitor();
+    tree->intersectsWithQuery( search_region, vis );
+    
+    Timer::Time the_tree_time = tree_timer.lap();
+    std::cout << "Rtree (good): " << the_tree_time << std::endl;
+
+
+    //-------------------------------------------
+    // Search tree - worst case
+    Timer tree_timer_2;
+    tree_timer_2.ask_for_timeslice();
+    tree_timer_2.start();
+
+    /* search the whole area, so all items are returned */
+    plow[0] = -limit - 100;
+    plow[1] = -limit - 100;
+    phigh[0] = limit + 100;
+    phigh[1] = limit + 100;
+    
+    SpatialIndex::Region search_region_2 = SpatialIndex::Region(plow, phigh, 2);
+    SearchVisitor vis_2 = SearchVisitor();
+    tree->intersectsWithQuery( search_region_2, vis_2 );
+    
+    Timer::Time the_tree_time_2 = tree_timer_2.lap();
+    std::cout << "Rtree (full scan): " << the_tree_time_2 << std::endl;
+    
+    return 0;
+}
+
+
+
+/* Adds rectangles in a GList and a SpatialIndex rtree
+ * */
+void add_rectangle( int x, int y ) {
+    
+    Geom::Point starting_point = Point( x, y );
+    Geom::Point ending_point = Point( x + 10, y + 10 );
+    Geom::Rect rect_to_add = Rect( starting_point, ending_point );
+    items = g_list_append( items, &rect_to_add );
+
+    if( arg_debug ) {
+        // fetch the last rect from the list
+        Geom::Rect *member_data = (Geom::Rect *)( g_list_last( items ) )->data;
+        double lala = member_data->bottom();
+        std::cout << "List (" << indexID << "): "  << lala;
+    }
+
+    /* Create a SpatialIndex region
+     * plow = left-bottom corner
+     * phigh = top-right corner
+     * [0] = dimension X
+     * [1] = dimension Y
+     * */    
+    double plow[2], phigh[2];    
+
+    plow[0] = rect_to_add.left() ;
+    plow[1] = rect_to_add.bottom();    
+    phigh[0] = rect_to_add.right();
+    phigh[1] = rect_to_add.top();
+    
+    SpatialIndex::Region r = SpatialIndex::Region(plow, phigh, 2);
+    /* Store Glist pointer size and GList pointer as the associated data
+     * In inkscape this can be used to directly call render hooked functions
+     * from SPCanvasItems
+     * */
+    tree->insertData( sizeof(GList*), reinterpret_cast<const byte*>( g_list_last( items ) ), r, indexID);
+
+    // tree->insertData(0, 0, r, indexID);
+    /* not used. Store zero size and a null pointer as the associated data.
+     * indexId is used to retrieve from a mapping each rect
+     * (example a hash map, or the indexID is also vector index)
+     * */
+
+    if( arg_debug ) {
+        test_indexID = indexID;
+        /* every time we add a rect, search all the tree to find the last
+         * inserted ID. This is not performance-wise good (rtree only good for
+         * spatial queries) this is just used for debugging reasons
+         * */
+        plow[0] = -limit - 100;
+        plow[1] = -limit - 100;
+        phigh[0] = limit + 100;
+        phigh[1] = limit + 100;
+    
+        SpatialIndex::Region test_search_region = SpatialIndex::Region(plow, phigh, 2);
+        TestSearchVisitor test_vis = TestSearchVisitor();
+        // search the tree for the region. Visitor implements the search function hooks
+        tree->intersectsWithQuery( test_search_region, test_vis );
+    }
+
+    indexID++;
+}
+
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)(c-basic-offset . 4))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :