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/lookup_table.h"
21 #include "canvas/group.h"
24 using namespace ArdourCanvas;
26 LookupTable::LookupTable (Group const & group)
32 LookupTable::~LookupTable ()
37 DumbLookupTable::DumbLookupTable (Group const & group)
44 DumbLookupTable::get (Rect const &)
46 list<Item *> const & items = _group.items ();
47 vector<Item *> vitems;
48 copy (items.begin(), items.end(), back_inserter (vitems));
52 /* XXX: what coordinate system is the point in? parent of our group I think */
54 DumbLookupTable::items_at_point (Duple point) const
56 list<Item *> items = _group.items ();
57 vector<Item *> vitems;
59 for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
60 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
62 Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
63 if (parent_bbox.contains (point)) {
64 vitems.push_back (*i);
72 OptimizingLookupTable::OptimizingLookupTable (Group const & group, int items_per_cell)
74 , _items_per_cell (items_per_cell)
77 list<Item*> const & items = _group.items ();
80 int const cells = items.size() / _items_per_cell;
81 /* hence number down each side of the table's square */
82 _dimension = max (1, int (rint (sqrt (cells))));
84 _cells = new Cell*[_dimension];
85 for (int i = 0; i < _dimension; ++i) {
86 _cells[i] = new Cell[_dimension];
89 /* our group's bounding box in its coordinates */
90 boost::optional<Rect> bbox = _group.bounding_box ();
95 _cell_size.x = bbox.get().width() / _dimension;
96 _cell_size.y = bbox.get().height() / _dimension;
97 _offset.x = bbox.get().x0;
98 _offset.y = bbox.get().y0;
100 // cout << "BUILD bbox=" << bbox.get() << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n";
102 for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) {
104 /* item bbox in its own coordinates */
105 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
110 /* and in the group's coordinates */
111 Rect const item_bbox_in_group = (*i)->item_to_parent (item_bbox.get ());
114 area_to_indices (item_bbox_in_group, x0, y0, x1, y1);
121 //assert (x0 <= _dimension);
122 //assert (y0 <= _dimension);
123 //assert (x1 <= _dimension);
124 //assert (y1 <= _dimension);
126 if (x0 > _dimension) {
127 cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x0 - bbox.get().x0) << "\n";
130 if (x1 > _dimension) {
131 cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x1 - bbox.get().x1) << "\n";
134 if (y0 > _dimension) {
135 cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y0 - bbox.get().y0) << "\n";
138 if (y1 > _dimension) {
139 cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y1 - bbox.get().y1) << "\n";
143 for (int x = x0; x < x1; ++x) {
144 for (int y = y0; y < y1; ++y) {
145 _cells[x][y].push_back (*i);
152 OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const
154 if (_cell_size.x == 0 || _cell_size.y == 0) {
155 x0 = y0 = x1 = y1 = 0;
159 Rect const offset_area = area.translate (-_offset);
161 x0 = floor (offset_area.x0 / _cell_size.x);
162 y0 = floor (offset_area.y0 / _cell_size.y);
163 x1 = ceil (offset_area.x1 / _cell_size.x);
164 y1 = ceil (offset_area.y1 / _cell_size.y);
167 OptimizingLookupTable::~OptimizingLookupTable ()
169 for (int i = 0; i < _dimension; ++i) {
177 OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const
179 if (_cell_size.x == 0 || _cell_size.y == 0) {
184 Duple const offset_point = point - _offset;
186 x = floor (offset_point.x / _cell_size.x);
187 y = floor (offset_point.y / _cell_size.y);
191 OptimizingLookupTable::items_at_point (Duple point) const
195 point_to_indices (point, x, y);
197 if (x >= _dimension) {
198 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
201 if (y >= _dimension) {
202 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
206 x = min (_dimension - 1, x);
207 y = min (_dimension - 1, y);
212 Cell const & cell = _cells[x][y];
214 for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
215 boost::optional<Rect> const item_bbox = (*i)->bounding_box ();
217 Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
218 if (parent_bbox.contains (point)) {
219 items.push_back (*i);
227 /** @param area Area in our owning group's coordinates */
229 OptimizingLookupTable::get (Rect const & area)
233 area_to_indices (area, x0, y0, x1, y1);
236 x0 = min (_dimension - 1, x0);
237 y0 = min (_dimension - 1, y0);
238 x1 = min (_dimension, x1);
239 y1 = min (_dimension, y1);
241 for (int x = x0; x < x1; ++x) {
242 for (int y = y0; y < y1; ++y) {
243 for (Cell::const_iterator i = _cells[x][y].begin(); i != _cells[x][y].end(); ++i) {
244 if (find (items.begin(), items.end(), *i) == items.end ()) {
245 items.push_back (*i);
251 vector<Item*> vitems;
252 copy (items.begin (), items.end (), back_inserter (vitems));