1 /*
2 * Copyright 2010 Evangelos Katsikaros <vkatsikaros at yahoo dot gr>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it either under the terms of the GNU Lesser General Public
6 * License version 2.1 as published by the Free Software Foundation
7 * (the "LGPL") or, at your option, under the terms of the Mozilla
8 * Public License Version 1.1 (the "MPL"). If you do not alter this
9 * notice, a recipient may use your version of this file under either
10 * the MPL or the LGPL.
11 *
12 * You should have received a copy of the LGPL along with this library
13 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15 * You should have received a copy of the MPL along with this library
16 * in the file COPYING-MPL-1.1
17 *
18 * The contents of this file are subject to the Mozilla Public License
19 * Version 1.1 (the "License"); you may not use this file except in
20 * compliance with the License. You may obtain a copy of the License at
21 * http://www.mozilla.org/MPL/
22 *
23 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
24 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
25 * the specific language governing rights and limitations.
26 */
27
28 #include <2geom/toys/toy-framework-2.h>
29
30 #include <sstream>
31 #include <getopt.h>
32
33 #include <SpatialIndex.h>
34 #include <glib.h>
35 //#include <glib/gtypes.h>
36
37 using namespace Geom;
38
39 // cmd argument stuff
40 char* arg_area_limit = NULL;
41 bool arg_area_limit_set = false;
42 bool arg_debug = false;
43
44 int limit = 0;
45
46 // spatial index ID management
47 SpatialIndex::id_type indexID;
48
49 // list of rectangles
50 GList *items = NULL;
51
52 // tree of rectangles
53 SpatialIndex::ISpatialIndex *tree;
54
55 SpatialIndex::id_type test_indexID;
56
57 void add_rectangle( int x, int y );
58
59 /* Simple Visitor used to search the tree. When Data is encountered
60 * we are supposed to call the render function of the Data
61 * */
62 class SearchVisitor : public SpatialIndex::IVisitor {
63 public:
64
visitNode(const SpatialIndex::INode & n)65 void visitNode(const SpatialIndex::INode& n){
66 }
67
visitData(const SpatialIndex::IData & d)68 void visitData(const SpatialIndex::IData& d){
69 /* this prototype: do nothing
70 * otherwise, render on buffer
71 * */
72 }
73
visitData(std::vector<const SpatialIndex::IData * > & v)74 void visitData(std::vector<const SpatialIndex::IData*>& v) {
75 }
76 };
77
78
79 /* we use the this visitor after each insertion in the tree
80 * The purpose is to validate that everything was stored properly
81 * and test the GList pointer storage. It has no other functional
82 * purpose.
83 * */
84 class TestSearchVisitor : public SpatialIndex::IVisitor {
85 public:
86
visitNode(const SpatialIndex::INode & n)87 void visitNode(const SpatialIndex::INode& n) {
88 }
89
visitData(const SpatialIndex::IData & d)90 void visitData(const SpatialIndex::IData& d){
91 if( test_indexID == d.getIdentifier() ){
92 byte* pData = 0;
93 uint32_t cLen = sizeof(GList*);
94 d.getData(cLen, &pData);
95 //do something...
96 GList* gl = reinterpret_cast<GList*>(pData);
97 Geom::Rect *member_data = (Geom::Rect *)gl->data;
98 double lala = member_data->bottom();
99 std::cout << " Tree: " << lala << std::endl;
100
101 delete[] pData;
102 }
103 }
104
visitData(std::vector<const SpatialIndex::IData * > & v)105 void visitData(std::vector<const SpatialIndex::IData*>& v) {
106 }
107 };
108
109
main(int argc,char ** argv)110 int main(int argc, char **argv) {
111
112 int c;
113
114 //--------------------------------------------------------------------------
115 // read cmd options
116 while (1) {
117 static struct option long_options[] =
118 {
119 /* These options set a flag. */
120 /* These options don't set a flag.
121 We distinguish them by their indices. */
122 {"area-limit", required_argument, 0, 'l'},
123 {"help", no_argument, 0, 'h'},
124 {"debug", no_argument, 0, 'd'},
125 {0, 0, 0, 0}
126 };
127 /* getopt_long stores the option index here. */
128 int option_index = 0;
129
130 c = getopt_long (argc, argv, "l:h:d",
131 long_options, &option_index);
132
133 /* Detect the end of the options. */
134 if (c == -1){
135 break;
136 }
137
138 switch (c)
139 {
140 case 'l':
141 arg_area_limit = optarg;
142 arg_area_limit_set = true;
143 break;
144 case 'h':
145 std::cerr << "Usage: " << argv[0] << " options\n" << std::endl ;
146 std::cerr <<
147 " -l --area-limit=NUMBER minimum number in node.\n" <<
148 " -d --debug Enable debug info (list/tree related).\n" <<
149 " -h --help Print this help.\n" << std::endl;
150 exit(1);
151 break;
152 case 'd':
153 arg_debug = true;
154 break;
155 case '?':
156 /* getopt_long already printed an error message. */
157 break;
158
159 default:
160 abort ();
161 }
162 }
163
164 // use some of the cmd options
165 if( arg_area_limit_set ) {
166 std::stringstream s1( arg_area_limit );
167 s1 >> limit;
168 }
169 else {
170 limit = 100;
171 }
172 // end cmd options
173 //--------------------------------------------------------------------------
174
175
176 double plow[2], phigh[2];
177 // spatial index memory storage manager
178 SpatialIndex::IStorageManager *mem_mngr;
179 // initialize spatial indexing stuff
180 mem_mngr = SpatialIndex::StorageManager::createNewMemoryStorageManager();
181 // fillFactor, indexCapacity, leafCapacity, dimensionality=2, variant=R*, indexIdentifier
182 tree = SpatialIndex::RTree::createNewRTree(*mem_mngr, 0.7, 25, 25, 2, SpatialIndex::RTree::RV_RSTAR, indexID);
183
184 //-------------------------------------------
185 /* generate items. add_rectangle() stores them in both list and tree
186 * add rect every (20, 20).
187 * In area ((0,0), (1000, 1000)) add every (100,100)
188 * */
189 for( int x_coord = -limit; x_coord <= limit; x_coord += 20 ) {
190 for( int y_coord = -limit; y_coord <= limit; y_coord += 20 ) {
191 if( x_coord >= 0 && x_coord <= 1000 &&
192 y_coord >= 0 && y_coord <= 1000 )
193 {
194 if( x_coord % 100 == 0 && y_coord % 100 == 0) {
195 add_rectangle( x_coord, y_coord );
196 }
197 else{
198 add_rectangle( x_coord, y_coord );
199 }
200 }
201 else{
202 add_rectangle( x_coord, y_coord );
203 }
204
205 }
206 }
207 std::cout << "Area of objects: ( -" << limit
208 << ", -" << limit
209 << " ), ( " << limit
210 << ", " << limit
211 << " )" << std::endl;
212 std::cout << "Number of Objects (indexID): " << indexID << std::endl;
213 // std::cout << "GListElements: " << g_list_length << std::endl;
214
215 //-------------------------------------------
216 // Traverse list
217 Geom::Point sa_start = Point( 0, 0 );
218 Geom::Point sa_end = Point( 1000, 1000 );
219 Geom::Rect search_area = Rect( sa_start, sa_end );
220
221 Timer list_timer;
222 list_timer.ask_for_timeslice();
223 list_timer.start();
224
225 for (GList *list = items; list; list = list->next) {
226 Geom::Rect *child = (Geom::Rect *)list->data;
227 if ( search_area.intersects( *child ) )
228 {
229 /* this prototype: do nothing
230 * otherwise, render on buffer
231 * */
232 }
233 }
234 Timer::Time the_list_time = list_timer.lap();
235
236 std::cout << std::endl;
237 std::cout << "GList (full scan): " << the_list_time << std::endl;
238
239 //-------------------------------------------
240 // Search tree - good case
241 Timer tree_timer;
242 tree_timer.ask_for_timeslice();
243 tree_timer.start();
244
245 /* We search only the (0,0), (1000, 1000) where the items are less dense.
246 * We expect a good performance versus the list
247 * */
248 // TODO IMPORTANT !!! check the plow, phigh
249 // plow[0] = x1; plow[1] = y1;
250 // phigh[0] = x2; phigh[1] = y2;
251
252 plow[0] = 0;
253 plow[1] = 0;
254 phigh[0] = 1000;
255 phigh[1] = 1000;
256
257 SpatialIndex::Region search_region = SpatialIndex::Region(plow, phigh, 2);
258 SearchVisitor vis = SearchVisitor();
259 tree->intersectsWithQuery( search_region, vis );
260
261 Timer::Time the_tree_time = tree_timer.lap();
262 std::cout << "Rtree (good): " << the_tree_time << std::endl;
263
264
265 //-------------------------------------------
266 // Search tree - worst case
267 Timer tree_timer_2;
268 tree_timer_2.ask_for_timeslice();
269 tree_timer_2.start();
270
271 /* search the whole area, so all items are returned */
272 plow[0] = -limit - 100;
273 plow[1] = -limit - 100;
274 phigh[0] = limit + 100;
275 phigh[1] = limit + 100;
276
277 SpatialIndex::Region search_region_2 = SpatialIndex::Region(plow, phigh, 2);
278 SearchVisitor vis_2 = SearchVisitor();
279 tree->intersectsWithQuery( search_region_2, vis_2 );
280
281 Timer::Time the_tree_time_2 = tree_timer_2.lap();
282 std::cout << "Rtree (full scan): " << the_tree_time_2 << std::endl;
283
284 return 0;
285 }
286
287
288
289 /* Adds rectangles in a GList and a SpatialIndex rtree
290 * */
add_rectangle(int x,int y)291 void add_rectangle( int x, int y ) {
292
293 Geom::Point starting_point = Point( x, y );
294 Geom::Point ending_point = Point( x + 10, y + 10 );
295 Geom::Rect rect_to_add = Rect( starting_point, ending_point );
296 items = g_list_append( items, &rect_to_add );
297
298 if( arg_debug ) {
299 // fetch the last rect from the list
300 Geom::Rect *member_data = (Geom::Rect *)( g_list_last( items ) )->data;
301 double lala = member_data->bottom();
302 std::cout << "List (" << indexID << "): " << lala;
303 }
304
305 /* Create a SpatialIndex region
306 * plow = left-bottom corner
307 * phigh = top-right corner
308 * [0] = dimension X
309 * [1] = dimension Y
310 * */
311 double plow[2], phigh[2];
312
313 plow[0] = rect_to_add.left() ;
314 plow[1] = rect_to_add.bottom();
315 phigh[0] = rect_to_add.right();
316 phigh[1] = rect_to_add.top();
317
318 SpatialIndex::Region r = SpatialIndex::Region(plow, phigh, 2);
319 /* Store Glist pointer size and GList pointer as the associated data
320 * In inkscape this can be used to directly call render hooked functions
321 * from SPCanvasItems
322 * */
323 tree->insertData( sizeof(GList*), reinterpret_cast<const byte*>( g_list_last( items ) ), r, indexID);
324
325 // tree->insertData(0, 0, r, indexID);
326 /* not used. Store zero size and a null pointer as the associated data.
327 * indexId is used to retrieve from a mapping each rect
328 * (example a hash map, or the indexID is also vector index)
329 * */
330
331 if( arg_debug ) {
332 test_indexID = indexID;
333 /* every time we add a rect, search all the tree to find the last
334 * inserted ID. This is not performance-wise good (rtree only good for
335 * spatial queries) this is just used for debugging reasons
336 * */
337 plow[0] = -limit - 100;
338 plow[1] = -limit - 100;
339 phigh[0] = limit + 100;
340 phigh[1] = limit + 100;
341
342 SpatialIndex::Region test_search_region = SpatialIndex::Region(plow, phigh, 2);
343 TestSearchVisitor test_vis = TestSearchVisitor();
344 // search the tree for the region. Visitor implements the search function hooks
345 tree->intersectsWithQuery( test_search_region, test_vis );
346 }
347
348 indexID++;
349 }
350
351
352 /*
353 Local Variables:
354 mode:c++
355 c-file-style:"stroustrup"
356 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)(c-basic-offset . 4))
357 indent-tabs-mode:nil
358 fill-column:99
359 End:
360 */
361 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
362