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