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