52 #include <boost/unordered_map.hpp>
67 MinimumDistance(
const int& cluster_index,
const int& nearest_neighbour_index,
const double& distance);
72 int getClusterIndex()
const;
77 int getNearestNeighbourIndex()
const;
124 template <
typename Metric>
136 typedef boost::unordered::unordered_multimap<int, MultisetIterator>::const_iterator
NNIterator;
149 const std::vector<double>& data_y,
const std::vector<int>& properties_A,
150 const std::vector<int>& properties_B, std::vector<double> grid_spacing_x,
151 std::vector<double> grid_spacing_y) :
153 grid_(grid_spacing_x, grid_spacing_y)
155 init_(data_x, data_y, properties_A, properties_B);
167 const std::vector<double>& data_y, std::vector<double> grid_spacing_x,
168 std::vector<double> grid_spacing_y) :
170 grid_(grid_spacing_x, grid_spacing_y)
173 std::vector<int> properties_A(data_x.size(), -1);
174 std::vector<int> properties_B(data_x.size(), -1);
175 init_(data_x, data_y, properties_A, properties_B);
199 int cluster_index1 = smallest_distance_it->getClusterIndex();
200 int cluster_index2 = smallest_distance_it->getNearestNeighbourIndex();
205 std::map<int, GridBasedCluster>::iterator cluster1_it =
clusters_.find(cluster_index1);
206 std::map<int, GridBasedCluster>::iterator cluster2_it =
clusters_.find(cluster_index2);
209 const std::vector<int>& points1 = cluster1.
getPoints();
210 const std::vector<int>& points2 = cluster2.
getPoints();
211 std::vector<int> new_points;
212 new_points.reserve(points1.size() + points2.size());
213 new_points.insert(new_points.end(), points1.begin(), points1.end());
214 new_points.insert(new_points.end(), points2.begin(), points2.end());
216 double new_x = (cluster1.
getCentre().
getX() * points1.size() + cluster2.
getCentre().
getX() * points2.size()) / (points1.size() + points2.size());
217 double new_y = (cluster1.
getCentre().
getY() * points1.size() + cluster2.
getCentre().
getY() * points2.size()) / (points1.size() + points2.size());
238 throw Exception::InvalidValue(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION,
"Property A of both clusters not the same. ",
"A");
244 std::vector<int> new_B;
245 new_B.reserve(B1.size() + B2.size());
246 new_B.insert(new_B.end(), B1.begin(), B1.end());
247 new_B.insert(new_B.end(), B2.begin(), B2.end());
253 clusters_.insert(std::make_pair(cluster_index1, new_cluster));
255 std::set<int> clusters_to_be_updated;
256 clusters_to_be_updated.insert(cluster_index1);
263 std::pair<NNIterator, NNIterator> nn_range =
reverse_nns_.equal_range(cluster_index1);
264 for (
NNIterator nn_it = nn_range.first; nn_it != nn_range.second;)
266 clusters_to_be_updated.insert(nn_it->second->getClusterIndex());
270 for (
NNIterator nn_it = nn_range.first; nn_it != nn_range.second;)
272 clusters_to_be_updated.insert(nn_it->second->getClusterIndex());
277 for (std::set<int>::const_iterator cluster_index = clusters_to_be_updated.begin(); cluster_index != clusters_to_be_updated.end(); ++cluster_index)
279 std::map<int, GridBasedCluster>::iterator c_it =
clusters_.find(*cluster_index);
302 std::vector<double> grid_spacing_y_new;
303 grid_spacing_y_new.push_back(grid_spacing_y.front());
304 grid_spacing_y_new.push_back(grid_spacing_y.back());
310 int cluster_index = it->first;
317 for (
unsigned cell = 0; cell < grid_spacing_x.size(); ++cell)
322 std::list<int> cluster_indices = grid_x_only.
getClusters(grid_index);
323 if (cluster_indices.size() > 1)
326 std::list<GridBasedCluster> cluster_list;
327 std::map<GridBasedCluster, int> index_list;
328 for (std::list<int>::const_iterator it = cluster_indices.begin(); it != cluster_indices.end(); ++it)
331 index_list.insert(std::make_pair(
clusters_final_.find(*it)->second, *it));
336 std::list<GridBasedCluster>::const_iterator c1 = cluster_list.begin();
337 std::list<GridBasedCluster>::const_iterator c2 = cluster_list.begin();
339 while (c1 != cluster_list.end())
341 double centre1x = (*c1).getCentre().getX();
342 double centre1y = (*c1).getCentre().getY();
343 double centre2x = (*c2).getCentre().getX();
344 double centre2y = (*c2).getCentre().getY();
346 double box1x_min = (*c1).getBoundingBox().minX();
347 double box1x_max = (*c1).getBoundingBox().maxX();
348 double box1y_min = (*c1).getBoundingBox().minY();
349 double box1y_max = (*c1).getBoundingBox().maxY();
350 double box2x_min = (*c2).getBoundingBox().minX();
351 double box2x_max = (*c2).getBoundingBox().maxX();
352 double box2y_min = (*c2).getBoundingBox().minY();
353 double box2y_max = (*c2).getBoundingBox().maxY();
360 bool overlap = (box1x_min <= box2x_max && box1x_min >= box2x_min) || (box1x_max >= box2x_min && box1x_max <= box2x_max);
374 std::vector<int> points1 = (*c1).getPoints();
375 std::vector<int> points2 = (*c2).getPoints();
376 std::vector<int> new_points;
377 new_points.reserve(points1.size() + points2.size());
378 new_points.insert(new_points.end(), points1.begin(), points1.end());
379 new_points.insert(new_points.end(), points2.begin(), points2.end());
381 double new_x = (centre1x * points1.size() + centre2x * points2.size()) / (points1.size() + points2.size());
382 double new_y = (centre1y * points1.size() + centre2y * points2.size()) / (points1.size() + points2.size());
384 double min_x = std::min(box1x_min, box2x_min);
385 double min_y = std::min(box1y_min, box2y_min);
386 double max_x = std::max(box1x_max, box2x_max);
387 double max_y = std::max(box1y_max, box2y_max);
389 Point new_centre(new_x, new_y);
390 Point position_min(min_x, min_y);
391 Point position_max(max_x, max_y);
392 Rectangle new_bounding_box(position_min, position_max);
399 clusters_final_.insert(std::make_pair(index_list.find(*c1)->second, new_cluster));
406 grid_x_only.
removeCluster(cell_for_cluster1, index_list.find(*c1)->second);
407 grid_x_only.
removeCluster(cell_for_cluster2, index_list.find(*c2)->second);
408 grid_x_only.
addCluster(cell_for_new_cluster, index_list.find(*c1)->second);
425 std::map<int, GridBasedCluster>::iterator it =
clusters_final_.begin();
428 Rectangle box = it->second.getBoundingBox();
429 if (box.
maxY() - box.
minY() < threshold_y)
483 boost::unordered::unordered_multimap<int, std::multiset<MinimumDistance>::const_iterator>
reverse_nns_;
499 void init_(
const std::vector<double>& data_x,
const std::vector<double>& data_y,
500 const std::vector<int>& properties_A,
const std::vector<int>& properties_B)
503 for (
unsigned i = 0; i < data_x.size(); ++i)
511 pb.push_back(properties_B[i]);
522 std::map<int, GridBasedCluster>::iterator iterator =
clusters_.begin();
525 int cluster_index = iterator->first;
561 if (A1 == -1 || A2 == -1)
567 if (A1 != A2)
return true;
573 if (
std::find(B1.begin(), B1.end(), -1) != B1.end() ||
std::find(B2.begin(), B2.end(), -1) != B2.end())
580 std::vector<int> B_intersection;
581 sort(B1.begin(), B1.end());
582 sort(B2.begin(), B2.end());
583 set_intersection(B1.begin(), B1.end(), B2.begin(), B2.end(), back_inserter(B_intersection));
585 return !B_intersection.empty();
606 int nearest_neighbour = -1;
609 for (
int i = -1; i <= 1; ++i)
611 for (
int j = -1; j <= 1; ++j)
614 cell_index2.first += i;
615 cell_index2.second += j;
619 for (std::list<int>::const_iterator cluster_index2 = cluster_indices.begin(); cluster_index2 != cluster_indices.end(); ++cluster_index2)
621 if (*cluster_index2 != cluster_index)
625 double distance =
metric_(centre, centre2);
627 if (distance < min_dist || nearest_neighbour == -1)
633 nearest_neighbour = *cluster_index2;
642 if (nearest_neighbour == -1)
650 std::multiset<MinimumDistance>::const_iterator it =
distances_.insert(
MinimumDistance(cluster_index, nearest_neighbour, min_dist));
652 reverse_nns_.insert(std::make_pair(nearest_neighbour, it));
671 std::pair<NNIterator, NNIterator> nn_range =
reverse_nns_.equal_range(it->getNearestNeighbourIndex());
672 for (
NNIterator nn_it = nn_range.first; nn_it != nn_range.second; ++nn_it)
674 if (nn_it->second == it)