2 Copyright (C) 2011-2013 Paul Davis
3 Author: Carl Hetherington <cth@carlh.net>
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.
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.
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.
20 #include "canvas/item.h"
21 #include "canvas/lookup_table.h"
24 using namespace ArdourCanvas;
26 LookupTable::LookupTable (Item const & item)
32 LookupTable::~LookupTable ()
37 DumbLookupTable::DumbLookupTable (Item const & item)
44 DumbLookupTable::get (Rect const &area)
46 list<Item *> const & items = _item.items ();
47 vector<Item *> vitems;
49 for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
50 Rect item_bbox = (*i)->bounding_box ();
51 if (!item_bbox) continue;
52 Rect item = (*i)->item_to_window (item_bbox);
53 if (item.intersection (area)) {
54 vitems.push_back (*i);
58 copy (items.begin(), items.end(), back_inserter (vitems));
64 DumbLookupTable::items_at_point (Duple const & point) const
66 /* Point is in window coordinate system */
68 list<Item *> const & items (_item.items ());
69 vector<Item *> vitems;
71 for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
73 if ((*i)->covers (point)) {
74 // std::cerr << "\t\t" << (*i)->whatami() << '/' << (*i)->name << " covers " << point << std::endl;
75 vitems.push_back (*i);
83 DumbLookupTable::has_item_at_point (Duple const & point) const
85 /* Point is in window coordinate system */
87 list<Item *> const & items (_item.items ());
88 vector<Item *> vitems;
90 for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
92 if (!(*i)->visible()) {
96 if ((*i)->covers (point)) {
97 // std::cerr << "\t\t" << (*i)->whatami() << '/' << (*i)->name << " covers " << point << std::endl;
106 OptimizingLookupTable::OptimizingLookupTable (Item const & item, int items_per_cell)
108 , _items_per_cell (items_per_cell)
111 list<Item*> const & items = _item.items ();
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))));
118 _cells = new Cell*[_dimension];
119 for (int i = 0; i < _dimension; ++i) {
120 _cells[i] = new Cell[_dimension];
123 /* our item's bounding box in its coordinates */
124 Rect bbox = _item.bounding_box ();
129 _cell_size.x = bbox.width() / _dimension;
130 _cell_size.y = bbox.height() / _dimension;
134 // cout << "BUILD bbox=" << bbox << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n";
136 for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) {
138 /* item bbox in its own coordinates */
139 Rect item_bbox = (*i)->bounding_box ();
144 /* and in the item's coordinates */
145 Rect const item_bbox_in_item = (*i)->item_to_parent (item_bbox);
148 area_to_indices (item_bbox_in_item, x0, y0, x1, y1);
155 //assert (x0 <= _dimension);
156 //assert (y0 <= _dimension);
157 //assert (x1 <= _dimension);
158 //assert (y1 <= _dimension);
160 if (x0 > _dimension) {
161 cout << "WARNING: item outside bbox by " << (item_bbox_in_item.x0 - bbox.x0) << "\n";
164 if (x1 > _dimension) {
165 cout << "WARNING: item outside bbox by " << (item_bbox_in_item.x1 - bbox.x1) << "\n";
168 if (y0 > _dimension) {
169 cout << "WARNING: item outside bbox by " << (item_bbox_in_item.y0 - bbox.y0) << "\n";
172 if (y1 > _dimension) {
173 cout << "WARNING: item outside bbox by " << (item_bbox_in_item.y1 - bbox.y1) << "\n";
177 for (int x = x0; x < x1; ++x) {
178 for (int y = y0; y < y1; ++y) {
179 _cells[x][y].push_back (*i);
186 OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const
188 if (_cell_size.x == 0 || _cell_size.y == 0) {
189 x0 = y0 = x1 = y1 = 0;
193 Rect const offset_area = area.translate (-_offset);
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);
201 OptimizingLookupTable::~OptimizingLookupTable ()
203 for (int i = 0; i < _dimension; ++i) {
211 OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const
213 if (_cell_size.x == 0 || _cell_size.y == 0) {
218 Duple const offset_point = point - _offset;
220 x = floor (offset_point.x / _cell_size.x);
221 y = floor (offset_point.y / _cell_size.y);
225 OptimizingLookupTable::items_at_point (Duple const & point) const
229 point_to_indices (point, x, y);
231 if (x >= _dimension) {
232 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
235 if (y >= _dimension) {
236 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
240 x = min (_dimension - 1, x);
241 y = min (_dimension - 1, y);
246 Cell const & cell = _cells[x][y];
248 for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
249 Rect const item_bbox = (*i)->bounding_box ();
251 Rect parent_bbox = (*i)->item_to_parent (item_bbox);
252 if (parent_bbox.contains (point)) {
253 items.push_back (*i);
262 OptimizingLookupTable::has_item_at_point (Duple const & point) const
266 point_to_indices (point, x, y);
268 if (x >= _dimension) {
269 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
272 if (y >= _dimension) {
273 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
277 x = min (_dimension - 1, x);
278 y = min (_dimension - 1, y);
283 Cell const & cell = _cells[x][y];
285 for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
286 Rect const item_bbox = (*i)->bounding_box ();
288 Rect parent_bbox = (*i)->item_to_parent (item_bbox);
289 if (parent_bbox.contains (point)) {
298 /** @param area Area in our owning item's coordinates */
300 OptimizingLookupTable::get (Rect const & area)
304 area_to_indices (area, x0, y0, x1, y1);
307 x0 = min (_dimension - 1, x0);
308 y0 = min (_dimension - 1, y0);
309 x1 = min (_dimension, x1);
310 y1 = min (_dimension, y1);
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);
322 vector<Item*> vitems;
323 copy (items.begin (), items.end (), back_inserter (vitems));