summaryrefslogtreecommitdiffstats
path: root/src/toys/rtree-toy.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/toys/rtree-toy.cpp')
-rw-r--r--src/toys/rtree-toy.cpp573
1 files changed, 573 insertions, 0 deletions
diff --git a/src/toys/rtree-toy.cpp b/src/toys/rtree-toy.cpp
new file mode 100644
index 0000000..b7872fa
--- /dev/null
+++ b/src/toys/rtree-toy.cpp
@@ -0,0 +1,573 @@
+/*
+ * Copyright 2009 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.
+ */
+
+/*
+ initial toy for redblack trees
+*/
+
+
+#include <toys/path-cairo.h>
+#include <toys/toy-framework-2.h>
+
+#include <time.h>
+#include <vector>
+#include <sstream>
+#include <getopt.h>
+
+#include <2geom/orphan-code/rtree.h>
+#include "../2geom/orphan-code/rtree.cpp"
+
+
+//using std::vector;
+using namespace Geom;
+using namespace std;
+
+// make sure that in RTreeToy() constructor you assign the same number of colors
+// otherwise, they extra will be black :P
+const int no_of_colors = 8;
+const string search_str = "Mode: Search (Area: Click whitespace and Drag)";
+const string update_str = "Mode: Update (Click Bounding Box (dark gray) and Drag) NOT implemented";
+const string insert_str = "Mode: Insert (Click whitespace and Drag)" ;
+const string erase_str = "Mode: Delete (Click on Bounding Box (dark gray))";
+const string help_str = "'I': Insert, 'U': Update, 'S': Search, 'D': Delete";
+
+
+const char* program_name;
+
+class RTreeToy: public Toy
+{
+
+// PointSetHandle handle_set;
+// std::vector< Handle > rectangle_handles;
+ std::vector< RectHandle > rectangles;
+
+ Geom::Point starting_point; // during click and drag: start point of click
+ Geom::Point ending_point; // during click and drag: end point of click (release)
+ Geom::Point highlight_point; // not used
+
+ // colors we are going to use for different purposes
+ colour color_shape, color_shape_guide;
+ colour color_select_area, color_select_area_guide; // red(a=0.6), red
+
+ bool add_new_rect;
+ bool delete_rect;
+
+ Rect rect_chosen; // the rectangle of the search area
+ Rect dummy_draw; // the "helper" rectangle that is shown during the click and drag (before the mouse release)
+
+ // save the bounding boxes of the tree in here
+ std::vector< std::vector< Rect > > rects_level;
+ std::vector<colour> color_rtree_level;
+ unsigned drawBB_color;
+ bool drawBB_color_all;
+
+ enum the_modes {
+ INSERT_MODE = 0,
+ UPDATE_MODE,
+ DELETE_MODE,
+ SEARCH_MODE,
+ } mode; // insert/alter, search, delete modes
+ bool drawBB; // draw bounding boxes of RTree
+ string out_str, drawBB_str, drawBB_color_str;
+
+ // printing of the tree
+ //int help_counter; // the "x" of the label of each node
+ static const int label_size = 15 ; // size the label of each node
+
+ Geom::RTree rtree;
+
+ void * hit;
+ unsigned rect_id;
+
+
+ // used for the keys that switch between modes
+ enum menu_item_t
+ {
+ INSERT_I = 0,
+ UPDATE_U,
+ DELETE_D,
+ SEARCH_S,
+ BB_TOGGLE_T,
+ BB_DRAW_0,
+ BB_DRAW_1,
+ BB_DRAW_2,
+ BB_DRAW_3,
+ BB_DRAW_4,
+ BB_DRAW_5,
+ BB_DRAW_ALL_O,
+ TOTAL_ITEMS // this one must be the last item
+ };
+ static const char* menu_items[TOTAL_ITEMS];
+ static const char keys[TOTAL_ITEMS];
+
+
+
+ void draw( cairo_t *cr, std::ostringstream *notify, int width, int height, bool save, std::ostringstream *timer_stream ) override {
+ cairo_set_line_width( cr, 1 );
+ cairo_set_source_rgba( cr, color_shape );
+ cairo_stroke( cr );
+
+ // draw the shapes we save in the rtree
+ for(auto & rectangle : rectangles){
+ rectangle.draw( cr, true );
+ }
+ cairo_set_source_rgba( cr, color_shape );
+ cairo_stroke( cr );
+
+ // draw a rect if we did click & drag (so that we know what we are going to create)
+ if( add_new_rect ){
+ dummy_draw = Rect( starting_point, ending_point );
+ cairo_rectangle( cr, dummy_draw );
+ if( mode == INSERT_MODE ){
+ cairo_set_source_rgba( cr, color_shape_guide );
+ }
+ else if( mode == SEARCH_MODE ){
+ cairo_set_source_rgba( cr, color_select_area_guide );
+ }
+ cairo_stroke( cr );
+ }
+
+ // draw a rect for the search area
+ cairo_rectangle( cr, rect_chosen );
+ cairo_set_source_rgba( cr, color_select_area );
+ cairo_stroke( cr );
+
+ *notify << help_str << "\n"
+ << "'T': Bounding Boxes: " << drawBB_str << ", '0'-'" << no_of_colors << "', 'P': Show Layer: " << drawBB_color_str << "\n"
+ << out_str;
+
+ if( drawBB ){
+ for(unsigned color = 0 ; color < rects_level.size() ; color++ ){
+ if( drawBB_color == color || drawBB_color_all ){
+ for(auto & j : rects_level){
+ cairo_rectangle( cr, j );
+ }
+ cairo_set_source_rgba( cr, color_rtree_level[color] );
+ cairo_stroke( cr );
+ }
+ }
+ }
+
+ Toy::draw( cr, notify, width, height, save,timer_stream );
+ }
+
+ void mouse_moved( GdkEventMotion* e ) override{
+ if(add_new_rect &&
+ ( mode == INSERT_MODE || mode == SEARCH_MODE ) )
+ {
+ Toy::mouse_moved( e );
+ ending_point = Point( e->x, e->y );
+ }
+ }
+
+ void mouse_pressed( GdkEventButton* e ) override {
+ Toy::mouse_pressed( e );
+ if(e->button == 1){ // left mouse button
+ if( mode == INSERT_MODE ){
+ starting_point = Point( e->x, e->y );
+ ending_point = starting_point;
+ add_new_rect = true;
+ }
+ else if( mode == SEARCH_MODE ){
+ starting_point = Point( e->x, e->y );
+ ending_point = starting_point;
+ add_new_rect = true;
+ }
+ else if( mode == DELETE_MODE ) {
+ Geom::Point mouse(e->x, e->y);
+ unsigned i = 0;
+ for( i = 0; i < rectangles.size(); i++) {
+ hit = rectangles[i].hit(mouse);
+ if( hit ) {
+ break;
+ }
+ }
+ if( hit ){
+ // erase specific element
+ stringstream shape_id( rectangles[i].name );
+ unsigned shape_id_int;
+ shape_id >> shape_id_int;
+
+ rtree.erase( rectangles[i].pos, shape_id_int );
+ rectangles.erase( rectangles.begin() + i );
+// check_if_deleted( );
+// check_if_duplicates( );
+ delete_rect = true;
+ }
+ hit = NULL;
+ }
+ }
+ else if( e->button == 2 ){ //middle button
+ }
+ else if( e->button == 3 ){ //right button
+ }
+ }
+
+ void mouse_released( GdkEventButton* e ) override {
+ Toy::mouse_released( e );
+ if( e->button == 1 ) { //left mouse button
+ if( mode == INSERT_MODE ) {
+ if( add_new_rect ){
+ ending_point = Point( e->x, e->y );
+ RectHandle t( Rect(starting_point, ending_point), false );
+
+ std::stringstream out;
+ out << rect_id;;
+ t.name = out.str();
+ rectangles.push_back( t );
+ rect_id++;
+
+ insert_in_tree_the_last_rect();
+ find_rtree_subtrees_bounding_boxes( rtree );
+ add_new_rect = false;
+ }
+ }
+ else if( mode == SEARCH_MODE ){
+ if( add_new_rect ){
+ ending_point = Point( e->x, e->y );
+ rect_chosen = Rect( starting_point, ending_point );
+
+ std::vector< int > result(0);
+
+ if( rtree.root ){
+ rtree.search( rect_chosen, &result, rtree.root );
+ }
+ std::cout << "Search results: " << result.size() << std::endl;
+ for(int i : result){
+ std::cout << i << ", " ;
+ }
+ std::cout << std::endl;
+
+ add_new_rect = false;
+ }
+ }
+ else if( mode == DELETE_MODE ) { // mode: delete
+ if( delete_rect ){
+ delete_rect = false;
+ if( rtree.root ){
+ find_rtree_subtrees_bounding_boxes( rtree );
+ }
+ std::cout << " \nTree:\n" << std::endl;
+ rtree.print_tree( rtree.root, 0 );
+ std::cout << "...done\n" << std::endl;
+ }
+ }
+ }
+ else if( e->button == 2 ){ //middle button
+ }
+ else if( e->button == 3 ){ //right button
+ }
+ }
+
+
+ void key_hit( GdkEventKey *e ) override
+ {
+ char choice = std::toupper( e->keyval );
+ switch ( choice )
+ {
+ case 'I':
+ mode = INSERT_MODE;
+ out_str = insert_str;
+ break;
+ case 'S':
+ mode = SEARCH_MODE;
+ out_str = search_str;
+ break;
+ case 'D':
+ mode = DELETE_MODE;
+ out_str = erase_str;
+ break;
+ case 'U':
+ mode = UPDATE_MODE;
+ out_str = update_str;
+ break;
+ case 'T':
+ if( drawBB ){
+ drawBB = false;
+ drawBB_str = "OFF";
+ }
+ else{
+ drawBB = true;
+ drawBB_str = "ON";
+ }
+ break;
+ case 'P':
+ drawBB_color_all = true;
+ drawBB_color = 9;
+ drawBB_color_str = "all";
+ break;
+ case '0':
+ drawBB_color_all = false;
+ drawBB_color = 0;
+ drawBB_color_str = "0";
+ break;
+ case '1':
+ drawBB_color_all = false;
+ drawBB_color = 1;
+ drawBB_color_str = "1";
+ break;
+ case '2':
+ drawBB_color_all = false;
+ drawBB_color = 2;
+ drawBB_color_str = "2";
+ break;
+ case '3':
+ drawBB_color_all = false;
+ drawBB_color = 3;
+ drawBB_color_str = "3";
+ break;
+ case '4':
+ drawBB_color_all = false;
+ drawBB_color = 4;
+ drawBB_color_str = "4";
+ break;
+ case '5':
+ drawBB_color_all = false;
+ drawBB_color = 5;
+ drawBB_color_str = "5";
+ break;
+ case '6':
+ drawBB_color_all = false;
+ drawBB_color = 6;
+ drawBB_color_str = "6";
+ break;
+ case '7':
+ drawBB_color_all = false;
+ drawBB_color = 7;
+ drawBB_color_str = "7";
+ break;
+ }
+ redraw();
+ }
+
+
+ void insert_in_tree_the_last_rect(){
+ unsigned i = rectangles.size() - 1;
+ Rect r1 = rectangles[i].pos;
+
+ stringstream shape_id( rectangles[i].name );
+ unsigned shape_id_int;
+ shape_id >> shape_id_int;
+
+ // insert in R tree
+ rtree.insert( r1, shape_id_int );
+ std::cout << " \nTree:\n" << std::endl;
+ rtree.print_tree( rtree.root, 0 );
+ std::cout << "...done\n" << std::endl;
+ };
+
+
+ void find_rtree_subtrees_bounding_boxes( Geom::RTree tree ){
+ if( tree.root ){
+ // clear existing bounding boxes
+ for(auto & color : rects_level){
+ color.clear();
+ }
+ save_bb( tree.root, 0);
+ }
+ };
+
+ // TODO fix this.
+ void save_bb( Geom::RTreeNode* subtree_root, int depth )
+ {
+ if( subtree_root->children_nodes.size() > 0 ){
+
+ // descend in each one of the elements and call print_tree
+ for(auto & children_node : subtree_root->children_nodes){
+ Rect r1( children_node.bounding_box );
+ rects_level[ depth ].push_back( r1 );
+
+ if( depth == no_of_colors - 1 ){ // if we reached Nth levels of colors, roll back to color 0
+ save_bb( children_node.data, 0);
+ }
+ else{
+ save_bb( children_node.data, depth+1);
+ }
+ }
+ }
+ // else do nothing, entries are the rects themselves...
+ };
+
+
+
+public:
+ RTreeToy(unsigned rmin, unsigned rmax, char /*handlefile*/):
+ rectangles(0),
+ color_shape(0, 0, 0, 0.9), color_shape_guide(1, 0, 0, 1),
+ color_select_area(1, 0, 0, 0.6 ), color_select_area_guide(1, 0, 0, 1 ), //1, 0, 0, 1
+ add_new_rect( false ), delete_rect( false ),
+ rect_chosen(), dummy_draw(),
+ rects_level( no_of_colors ),
+ color_rtree_level( no_of_colors, colour(0, 0, 0, 0) ),
+ drawBB_color(9), drawBB_color_all(true),
+ mode( INSERT_MODE ), drawBB(true),
+ out_str( insert_str ),
+ drawBB_str("ON"), drawBB_color_str("all"),
+ rtree( rmin, rmax, QUADRATIC_SPIT ),
+ hit( 0 ), rect_id( 0 )
+ {
+ // only "bright" colors
+ color_rtree_level[0] = colour(0, 0.80, 1, 1); // cyan
+ color_rtree_level[1] = colour(0, 0.85, 0, 1); // green
+ color_rtree_level[2] = colour(0.75, 0, 0.75, 1); // purple
+ color_rtree_level[3] = colour(0, 0, 1, 1); // blue
+ color_rtree_level[4] = colour(1, 0.62, 0, 1); // orange
+ color_rtree_level[5] = colour(1, 0, 0.8, 1); // pink
+ color_rtree_level[6] = colour(0.47, 0.26, 0.12, 1);
+ color_rtree_level[7] = colour(1, 0.90, 0, 1); // yellow
+ }
+
+};
+
+
+
+int main(int argc, char **argv) {
+
+ char* min_arg = NULL;
+ char* max_arg = NULL;
+
+ int set_min_max = 0;
+
+ int c;
+
+ 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. */
+ {"min-nodes", required_argument, 0, 'n'},
+ {"max-nodes", required_argument, 0, 'm'},
+ {"help", no_argument, 0, 'h'},
+ {0, 0, 0, 0}
+ };
+ /* getopt_long stores the option index here. */
+ int option_index = 0;
+
+ c = getopt_long (argc, argv, "n:m:h",
+ long_options, &option_index);
+
+ /* Detect the end of the options. */
+ if (c == -1){
+ break;
+ }
+
+ switch (c)
+ {
+ case 'n':
+ min_arg = optarg;
+ set_min_max += 1;
+ break;
+
+
+ case 'm':
+ max_arg = optarg;
+ set_min_max += 2;
+ break;
+
+
+ case 'h':
+ std::cerr << "Usage: " << argv[0] << " options\n" << std::endl ;
+ std::cerr <<
+ " -n --min-nodes=NUMBER minimum number in node.\n" <<
+ " -m --max-nodes=NUMBER maximum number in node.\n" <<
+ " -h --help Print this help.\n" << std::endl;
+ exit(1);
+ break;
+
+
+ case '?':
+ /* getopt_long already printed an error message. */
+ break;
+
+ default:
+ abort ();
+ }
+ }
+
+ unsigned rmin = 0;
+ unsigned rmax = 0;
+
+ if( set_min_max == 3 ){
+ stringstream s1( min_arg );
+ s1 >> rmin;
+
+ stringstream s2( max_arg );
+ s2 >> rmax;
+ if( rmax <= rmin || rmax < 2 || rmin < 1 ){
+ std::cerr << "Rtree set to 2, 3" << std::endl ;
+ rmin = 2;
+ rmax = 3;
+ }
+ }
+ else{
+ std::cerr << "Rtree set to 2, 3 ." << std::endl ;
+ rmin = 2;
+ rmax = 3;
+ }
+
+
+ char handlefile = 'T';
+ std::cout << "rmin: " << rmin << " rmax:" << rmax << std::endl;
+ init(argc, argv, new RTreeToy( rmin, rmax, handlefile) );
+
+ return 0;
+}
+
+
+
+const char* RTreeToy::menu_items[] =
+{
+ "Insert / Alter Rectangle",
+ "Search Rectangle",
+ "Delete Reactangle",
+ "Toggle"
+};
+
+const char RTreeToy::keys[] =
+{
+ 'I', 'U', 'S', 'D', 'T',
+ '0', '1', '2', '3', '4', '5', 'P'
+};
+
+
+
+
+
+
+/*
+intersection test
+ Rect r1( Point(100, 100), Point(150, 150)),
+ r2( Point(200, 200), Point(250, 250)),
+ r3( Point(50, 50), Point(100, 100));
+ OptRect a_intersection_b;
+ a_intersection_b = intersect( r1, r2 );
+ std::cout << "r1, r2 " << a_intersection_b.empty() << std::endl;
+ a_intersection_b = intersect( r1, r3 );
+ std::cout << "r1, r3 " << a_intersection_b.empty() << std::endl;
+*/
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-11 23:48:23 +0000