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 const & point) const
  54 {
  55         /* Point is in canvas coordinate system */
  56
  57         list<Item *> const & items (_group.items ());
  58         vector<Item *> vitems;
  59
  60         for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
  61
  62                 if ((*i)->covers (point)) {
  63                         // std::cerr << "\t\t" << (*i)->whatami() << '/' << (*i)->name << " covers " << point << std::endl;
  64                         vitems.push_back (*i);
  65                 }
  66         }
  67
  68         return vitems;
  69 }
  70
  71 bool
  72 DumbLookupTable::has_item_at_point (Duple const & point) const
  73 {
  74         /* Point is in canvas coordinate system */
  75
  76         list<Item *> const & items (_group.items ());
  77         vector<Item *> vitems;
  78
  79         for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
  80
  81                 if (!(*i)->visible()) {
  82                         continue;
  83                 }
  84
  85                 if ((*i)->covers (point)) {
  86                         // std::cerr << "\t\t" << (*i)->whatami() << '/' << (*i)->name << " covers " << point << std::endl;
  87                         return true;
  88
  89                 }
  90         }
  91
  92         return false;
  93 }
  94
  95 OptimizingLookupTable::OptimizingLookupTable (Group const & group, int items_per_cell)
  96         : LookupTable (group)
  97         , _items_per_cell (items_per_cell)
  98         , _added (false)
  99 {
 100         list<Item*> const & items = _group.items ();
 101
 102         /* number of cells */
 103         int const cells = items.size() / _items_per_cell;
 104         /* hence number down each side of the table's square */
 105         _dimension = max (1, int (rint (sqrt ((double)cells))));
 106
 107         _cells = new Cell*[_dimension];
 108         for (int i = 0; i < _dimension; ++i) {
 109                 _cells[i] = new Cell[_dimension];
 110         }
 111
 112         /* our group's bounding box in its coordinates */
 113         boost::optional<Rect> bbox = _group.bounding_box ();
 114         if (!bbox) {
 115                 return;
 116         }
 117
 118         _cell_size.x = bbox.get().width() / _dimension;
 119         _cell_size.y = bbox.get().height() / _dimension;
 120         _offset.x = bbox.get().x0;
 121         _offset.y = bbox.get().y0;
 122
 123 //      cout << "BUILD bbox=" << bbox.get() << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n";
 124
 125         for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) {
 126
 127                 /* item bbox in its own coordinates */
 128                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
 129                 if (!item_bbox) {
 130                         continue;
 131                 }
 132
 133                 /* and in the group's coordinates */
 134                 Rect const item_bbox_in_group = (*i)->item_to_parent (item_bbox.get ());
 135
 136                 int x0, y0, x1, y1;
 137                 area_to_indices (item_bbox_in_group, x0, y0, x1, y1);
 138
 139                 /* XXX */
 140                 assert (x0 >= 0);
 141                 assert (y0 >= 0);
 142                 assert (x1 >= 0);
 143                 assert (y1 >= 0);
 144                 //assert (x0 <= _dimension);
 145                 //assert (y0 <= _dimension);
 146                 //assert (x1 <= _dimension);
 147                 //assert (y1 <= _dimension);
 148
 149                 if (x0 > _dimension) {
 150                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x0 - bbox.get().x0) << "\n";
 151                         x0 = _dimension;
 152                 }
 153                 if (x1 > _dimension) {
 154                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x1 - bbox.get().x1) << "\n";
 155                         x1 = _dimension;
 156                 }
 157                 if (y0 > _dimension) {
 158                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y0 - bbox.get().y0) << "\n";
 159                         y0 = _dimension;
 160                 }
 161                 if (y1 > _dimension) {
 162                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y1 - bbox.get().y1) << "\n";
 163                         y1 = _dimension;
 164                 }
 165
 166                 for (int x = x0; x < x1; ++x) {
 167                         for (int y = y0; y < y1; ++y) {
 168                                 _cells[x][y].push_back (*i);
 169                         }
 170                 }
 171         }
 172 }
 173
 174 void
 175 OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const
 176 {
 177         if (_cell_size.x == 0 || _cell_size.y == 0) {
 178                 x0 = y0 = x1 = y1 = 0;
 179                 return;
 180         }
 181
 182         Rect const offset_area = area.translate (-_offset);
 183
 184         x0 = floor (offset_area.x0 / _cell_size.x);
 185         y0 = floor (offset_area.y0 / _cell_size.y);
 186         x1 = ceil  (offset_area.x1 / _cell_size.x);
 187         y1 = ceil  (offset_area.y1 / _cell_size.y);
 188 }
 189
 190 OptimizingLookupTable::~OptimizingLookupTable ()
 191 {
 192         for (int i = 0; i < _dimension; ++i) {
 193                 delete[] _cells[i];
 194         }
 195
 196         delete[] _cells;
 197 }
 198
 199 void
 200 OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const
 201 {
 202         if (_cell_size.x == 0 || _cell_size.y == 0) {
 203                 x = y = 0;
 204                 return;
 205         }
 206
 207         Duple const offset_point = point - _offset;
 208
 209         x = floor (offset_point.x / _cell_size.x);
 210         y = floor (offset_point.y / _cell_size.y);
 211 }
 212
 213 vector<Item*>
 214 OptimizingLookupTable::items_at_point (Duple const & point) const
 215 {
 216         int x;
 217         int y;
 218         point_to_indices (point, x, y);
 219
 220         if (x >= _dimension) {
 221                 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
 222         }
 223
 224         if (y >= _dimension) {
 225                 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
 226         }
 227
 228         /* XXX: hmm */
 229         x = min (_dimension - 1, x);
 230         y = min (_dimension - 1, y);
 231
 232         assert (x >= 0);
 233         assert (y >= 0);
 234
 235         Cell const & cell = _cells[x][y];
 236         vector<Item*> items;
 237         for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
 238                 boost::optional<Rect> const item_bbox = (*i)->bounding_box ();
 239                 if (item_bbox) {
 240                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
 241                         if (parent_bbox.contains (point)) {
 242                                 items.push_back (*i);
 243                         }
 244                 }
 245         }
 246
 247         return items;
 248 }
 249
 250 bool
 251 OptimizingLookupTable::has_item_at_point (Duple const & point) const
 252 {
 253         int x;
 254         int y;
 255         point_to_indices (point, x, y);
 256
 257         if (x >= _dimension) {
 258                 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
 259         }
 260
 261         if (y >= _dimension) {
 262                 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
 263         }
 264
 265         /* XXX: hmm */
 266         x = min (_dimension - 1, x);
 267         y = min (_dimension - 1, y);
 268
 269         assert (x >= 0);
 270         assert (y >= 0);
 271
 272         Cell const & cell = _cells[x][y];
 273         vector<Item*> items;
 274         for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
 275                 boost::optional<Rect> const item_bbox = (*i)->bounding_box ();
 276                 if (item_bbox) {
 277                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
 278                         if (parent_bbox.contains (point)) {
 279                                 return true;
 280                         }
 281                 }
 282         }
 283
 284         return false;
 285 }
 286
 287 /** @param area Area in our owning group's coordinates */
 288 vector<Item*>
 289 OptimizingLookupTable::get (Rect const & area)
 290 {
 291         list<Item*> items;
 292         int x0, y0, x1, y1;
 293         area_to_indices (area, x0, y0, x1, y1);
 294
 295         /* XXX: hmm... */
 296         x0 = min (_dimension - 1, x0);
 297         y0 = min (_dimension - 1, y0);
 298         x1 = min (_dimension, x1);
 299         y1 = min (_dimension, y1);
 300
 301         for (int x = x0; x < x1; ++x) {
 302                 for (int y = y0; y < y1; ++y) {
 303                         for (Cell::const_iterator i = _cells[x][y].begin(); i != _cells[x][y].end(); ++i) {
 304                                 if (find (items.begin(), items.end(), *i) == items.end ()) {
 305                                         items.push_back (*i);
 306                                 }
 307                         }
 308                 }
 309         }
 310
 311         vector<Item*> vitems;
 312         copy (items.begin (), items.end (), back_inserter (vitems));
 313
 314         return vitems;
 315 }
 316