libs/canvas/lookup_table.cc

   1 /*
   2     Copyright (C) 2011-2013 Paul Davis
   3     Author: Carl Hetherington <cth@carlh.net>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18 */
  19
  20 #include "canvas/lookup_table.h"
  21 #include "canvas/group.h"
  22
  23 using namespace std;
  24 using namespace ArdourCanvas;
  25
  26 LookupTable::LookupTable (Group const & group)
  27         : _group (group)
  28 {
  29
  30 }
  31
  32 LookupTable::~LookupTable ()
  33 {
  34
  35 }
  36
  37 DumbLookupTable::DumbLookupTable (Group const & group)
  38         : LookupTable (group)
  39 {
  40
  41 }
  42
  43 vector<Item *>
  44 DumbLookupTable::get (Rect const &)
  45 {
  46         list<Item *> const & items = _group.items ();
  47         vector<Item *> vitems;
  48         copy (items.begin(), items.end(), back_inserter (vitems));
  49         return vitems;
  50 }
  51
  52 vector<Item *>
  53 DumbLookupTable::items_at_point (Duple point) const
  54 {
  55         /* Point is in canvas coordinate system */
  56
  57         list<Item *> items = _group.items ();
  58         vector<Item *> vitems;
  59
  60         for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
  61                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
  62                 if (item_bbox) {
  63                         Rect canvas_bbox = (*i)->item_to_canvas (item_bbox.get ());
  64                         if (canvas_bbox.contains (point)) {
  65                                 vitems.push_back (*i);
  66                         }
  67                 }
  68         }
  69
  70         return vitems;
  71 }
  72
  73 OptimizingLookupTable::OptimizingLookupTable (Group const & group, int items_per_cell)
  74         : LookupTable (group)
  75         , _items_per_cell (items_per_cell)
  76         , _added (false)
  77 {
  78         list<Item*> const & items = _group.items ();
  79
  80         /* number of cells */
  81         int const cells = items.size() / _items_per_cell;
  82         /* hence number down each side of the table's square */
  83         _dimension = max (1, int (rint (sqrt ((double)cells))));
  84
  85         _cells = new Cell*[_dimension];
  86         for (int i = 0; i < _dimension; ++i) {
  87                 _cells[i] = new Cell[_dimension];
  88         }
  89
  90         /* our group's bounding box in its coordinates */
  91         boost::optional<Rect> bbox = _group.bounding_box ();
  92         if (!bbox) {
  93                 return;
  94         }
  95
  96         _cell_size.x = bbox.get().width() / _dimension;
  97         _cell_size.y = bbox.get().height() / _dimension;
  98         _offset.x = bbox.get().x0;
  99         _offset.y = bbox.get().y0;
 100
 101 //      cout << "BUILD bbox=" << bbox.get() << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n";
 102
 103         for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) {
 104
 105                 /* item bbox in its own coordinates */
 106                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
 107                 if (!item_bbox) {
 108                         continue;
 109                 }
 110
 111                 /* and in the group's coordinates */
 112                 Rect const item_bbox_in_group = (*i)->item_to_parent (item_bbox.get ());
 113
 114                 int x0, y0, x1, y1;
 115                 area_to_indices (item_bbox_in_group, x0, y0, x1, y1);
 116
 117                 /* XXX */
 118                 assert (x0 >= 0);
 119                 assert (y0 >= 0);
 120                 assert (x1 >= 0);
 121                 assert (y1 >= 0);
 122                 //assert (x0 <= _dimension);
 123                 //assert (y0 <= _dimension);
 124                 //assert (x1 <= _dimension);
 125                 //assert (y1 <= _dimension);
 126
 127                 if (x0 > _dimension) {
 128                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x0 - bbox.get().x0) << "\n";
 129                         x0 = _dimension;
 130                 }
 131                 if (x1 > _dimension) {
 132                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x1 - bbox.get().x1) << "\n";
 133                         x1 = _dimension;
 134                 }
 135                 if (y0 > _dimension) {
 136                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y0 - bbox.get().y0) << "\n";
 137                         y0 = _dimension;
 138                 }
 139                 if (y1 > _dimension) {
 140                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y1 - bbox.get().y1) << "\n";
 141                         y1 = _dimension;
 142                 }
 143
 144                 for (int x = x0; x < x1; ++x) {
 145                         for (int y = y0; y < y1; ++y) {
 146                                 _cells[x][y].push_back (*i);
 147                         }
 148                 }
 149         }
 150 }
 151
 152 void
 153 OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const
 154 {
 155         if (_cell_size.x == 0 || _cell_size.y == 0) {
 156                 x0 = y0 = x1 = y1 = 0;
 157                 return;
 158         }
 159
 160         Rect const offset_area = area.translate (-_offset);
 161
 162         x0 = floor (offset_area.x0 / _cell_size.x);
 163         y0 = floor (offset_area.y0 / _cell_size.y);
 164         x1 = ceil  (offset_area.x1 / _cell_size.x);
 165         y1 = ceil  (offset_area.y1 / _cell_size.y);
 166 }
 167
 168 OptimizingLookupTable::~OptimizingLookupTable ()
 169 {
 170         for (int i = 0; i < _dimension; ++i) {
 171                 delete[] _cells[i];
 172         }
 173
 174         delete[] _cells;
 175 }
 176
 177 void
 178 OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const
 179 {
 180         if (_cell_size.x == 0 || _cell_size.y == 0) {
 181                 x = y = 0;
 182                 return;
 183         }
 184
 185         Duple const offset_point = point - _offset;
 186
 187         x = floor (offset_point.x / _cell_size.x);
 188         y = floor (offset_point.y / _cell_size.y);
 189 }
 190
 191 vector<Item*>
 192 OptimizingLookupTable::items_at_point (Duple point) const
 193 {
 194         int x;
 195         int y;
 196         point_to_indices (point, x, y);
 197
 198         if (x >= _dimension) {
 199                 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
 200         }
 201
 202         if (y >= _dimension) {
 203                 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
 204         }
 205
 206         /* XXX: hmm */
 207         x = min (_dimension - 1, x);
 208         y = min (_dimension - 1, y);
 209
 210         assert (x >= 0);
 211         assert (y >= 0);
 212
 213         Cell const & cell = _cells[x][y];
 214         vector<Item*> items;
 215         for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
 216                 boost::optional<Rect> const item_bbox = (*i)->bounding_box ();
 217                 if (item_bbox) {
 218                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
 219                         if (parent_bbox.contains (point)) {
 220                                 items.push_back (*i);
 221                         }
 222                 }
 223         }
 224
 225         return items;
 226 }
 227
 228 /** @param area Area in our owning group's coordinates */
 229 vector<Item*>
 230 OptimizingLookupTable::get (Rect const & area)
 231 {
 232         list<Item*> items;
 233         int x0, y0, x1, y1;
 234         area_to_indices (area, x0, y0, x1, y1);
 235
 236         /* XXX: hmm... */
 237         x0 = min (_dimension - 1, x0);
 238         y0 = min (_dimension - 1, y0);
 239         x1 = min (_dimension, x1);
 240         y1 = min (_dimension, y1);
 241
 242         for (int x = x0; x < x1; ++x) {
 243                 for (int y = y0; y < y1; ++y) {
 244                         for (Cell::const_iterator i = _cells[x][y].begin(); i != _cells[x][y].end(); ++i) {
 245                                 if (find (items.begin(), items.end(), *i) == items.end ()) {
 246                                         items.push_back (*i);
 247                                 }
 248                         }
 249                 }
 250         }
 251
 252         vector<Item*> vitems;
 253         copy (items.begin (), items.end (), back_inserter (vitems));
 254
 255         return vitems;
 256 }
 257