diff options
Diffstat (limited to 'libs/canvas/lookup_table.cc')
-rw-r--r-- | libs/canvas/lookup_table.cc | 316 |
1 files changed, 316 insertions, 0 deletions
diff --git a/libs/canvas/lookup_table.cc b/libs/canvas/lookup_table.cc new file mode 100644 index 0000000000..f88531537a --- /dev/null +++ b/libs/canvas/lookup_table.cc @@ -0,0 +1,316 @@ +/* + Copyright (C) 2011-2013 Paul Davis + Author: Carl Hetherington <cth@carlh.net> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*/ + +#include "canvas/lookup_table.h" +#include "canvas/group.h" + +using namespace std; +using namespace ArdourCanvas; + +LookupTable::LookupTable (Group const & group) + : _group (group) +{ + +} + +LookupTable::~LookupTable () +{ + +} + +DumbLookupTable::DumbLookupTable (Group const & group) + : LookupTable (group) +{ + +} + +vector<Item *> +DumbLookupTable::get (Rect const &) +{ + list<Item *> const & items = _group.items (); + vector<Item *> vitems; + copy (items.begin(), items.end(), back_inserter (vitems)); + return vitems; +} + +vector<Item *> +DumbLookupTable::items_at_point (Duple const & point) const +{ + /* Point is in canvas coordinate system */ + + list<Item *> const & items (_group.items ()); + vector<Item *> vitems; + + for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) { + + if ((*i)->covers (point)) { + // std::cerr << "\t\t" << (*i)->whatami() << '/' << (*i)->name << " covers " << point << std::endl; + vitems.push_back (*i); + } + } + + return vitems; +} + +bool +DumbLookupTable::has_item_at_point (Duple const & point) const +{ + /* Point is in canvas coordinate system */ + + list<Item *> const & items (_group.items ()); + vector<Item *> vitems; + + for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) { + + if (!(*i)->visible()) { + continue; + } + + if ((*i)->covers (point)) { + // std::cerr << "\t\t" << (*i)->whatami() << '/' << (*i)->name << " covers " << point << std::endl; + return true; + + } + } + + return false; +} + +OptimizingLookupTable::OptimizingLookupTable (Group const & group, int items_per_cell) + : LookupTable (group) + , _items_per_cell (items_per_cell) + , _added (false) +{ + list<Item*> const & items = _group.items (); + + /* number of cells */ + int const cells = items.size() / _items_per_cell; + /* hence number down each side of the table's square */ + _dimension = max (1, int (rint (sqrt ((double)cells)))); + + _cells = new Cell*[_dimension]; + for (int i = 0; i < _dimension; ++i) { + _cells[i] = new Cell[_dimension]; + } + + /* our group's bounding box in its coordinates */ + boost::optional<Rect> bbox = _group.bounding_box (); + if (!bbox) { + return; + } + + _cell_size.x = bbox.get().width() / _dimension; + _cell_size.y = bbox.get().height() / _dimension; + _offset.x = bbox.get().x0; + _offset.y = bbox.get().y0; + +// cout << "BUILD bbox=" << bbox.get() << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n"; + + for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) { + + /* item bbox in its own coordinates */ + boost::optional<Rect> item_bbox = (*i)->bounding_box (); + if (!item_bbox) { + continue; + } + + /* and in the group's coordinates */ + Rect const item_bbox_in_group = (*i)->item_to_parent (item_bbox.get ()); + + int x0, y0, x1, y1; + area_to_indices (item_bbox_in_group, x0, y0, x1, y1); + + /* XXX */ + assert (x0 >= 0); + assert (y0 >= 0); + assert (x1 >= 0); + assert (y1 >= 0); + //assert (x0 <= _dimension); + //assert (y0 <= _dimension); + //assert (x1 <= _dimension); + //assert (y1 <= _dimension); + + if (x0 > _dimension) { + cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x0 - bbox.get().x0) << "\n"; + x0 = _dimension; + } + if (x1 > _dimension) { + cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x1 - bbox.get().x1) << "\n"; + x1 = _dimension; + } + if (y0 > _dimension) { + cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y0 - bbox.get().y0) << "\n"; + y0 = _dimension; + } + if (y1 > _dimension) { + cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y1 - bbox.get().y1) << "\n"; + y1 = _dimension; + } + + for (int x = x0; x < x1; ++x) { + for (int y = y0; y < y1; ++y) { + _cells[x][y].push_back (*i); + } + } + } +} + +void +OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const +{ + if (_cell_size.x == 0 || _cell_size.y == 0) { + x0 = y0 = x1 = y1 = 0; + return; + } + + Rect const offset_area = area.translate (-_offset); + + x0 = floor (offset_area.x0 / _cell_size.x); + y0 = floor (offset_area.y0 / _cell_size.y); + x1 = ceil (offset_area.x1 / _cell_size.x); + y1 = ceil (offset_area.y1 / _cell_size.y); +} + +OptimizingLookupTable::~OptimizingLookupTable () +{ + for (int i = 0; i < _dimension; ++i) { + delete[] _cells[i]; + } + + delete[] _cells; +} + +void +OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const +{ + if (_cell_size.x == 0 || _cell_size.y == 0) { + x = y = 0; + return; + } + + Duple const offset_point = point - _offset; + + x = floor (offset_point.x / _cell_size.x); + y = floor (offset_point.y / _cell_size.y); +} + +vector<Item*> +OptimizingLookupTable::items_at_point (Duple const & point) const +{ + int x; + int y; + point_to_indices (point, x, y); + + if (x >= _dimension) { + cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n"; + } + + if (y >= _dimension) { + cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n"; + } + + /* XXX: hmm */ + x = min (_dimension - 1, x); + y = min (_dimension - 1, y); + + assert (x >= 0); + assert (y >= 0); + + Cell const & cell = _cells[x][y]; + vector<Item*> items; + for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) { + boost::optional<Rect> const item_bbox = (*i)->bounding_box (); + if (item_bbox) { + Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ()); + if (parent_bbox.contains (point)) { + items.push_back (*i); + } + } + } + + return items; +} + +bool +OptimizingLookupTable::has_item_at_point (Duple const & point) const +{ + int x; + int y; + point_to_indices (point, x, y); + + if (x >= _dimension) { + cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n"; + } + + if (y >= _dimension) { + cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n"; + } + + /* XXX: hmm */ + x = min (_dimension - 1, x); + y = min (_dimension - 1, y); + + assert (x >= 0); + assert (y >= 0); + + Cell const & cell = _cells[x][y]; + vector<Item*> items; + for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) { + boost::optional<Rect> const item_bbox = (*i)->bounding_box (); + if (item_bbox) { + Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ()); + if (parent_bbox.contains (point)) { + return true; + } + } + } + + return false; +} + +/** @param area Area in our owning group's coordinates */ +vector<Item*> +OptimizingLookupTable::get (Rect const & area) +{ + list<Item*> items; + int x0, y0, x1, y1; + area_to_indices (area, x0, y0, x1, y1); + + /* XXX: hmm... */ + x0 = min (_dimension - 1, x0); + y0 = min (_dimension - 1, y0); + x1 = min (_dimension, x1); + y1 = min (_dimension, y1); + + for (int x = x0; x < x1; ++x) { + for (int y = y0; y < y1; ++y) { + for (Cell::const_iterator i = _cells[x][y].begin(); i != _cells[x][y].end(); ++i) { + if (find (items.begin(), items.end(), *i) == items.end ()) { + items.push_back (*i); + } + } + } + } + + vector<Item*> vitems; + copy (items.begin (), items.end (), back_inserter (vitems)); + + return vitems; +} + |