1 /* 2 * RenderItemMatcher.hpp 3 * 4 * Created on: Feb 16, 2009 5 * Author: struktured 6 */ 7 8 #ifndef RenderItemMatcher_HPP 9 #define RenderItemMatcher_HPP 10 11 #include "RenderItemDistanceMetric.hpp" 12 #include <vector> 13 #include <map> 14 #include <iostream> 15 #include "HungarianMethod.hpp" 16 17 typedef std::vector<std::pair<RenderItem*, RenderItem*> > RenderItemMatchList; 18 19 class MatchResults; 20 21 class RenderItemMatcher : public std::binary_function<RenderItemList, RenderItemList, MatchResults> { 22 23 public: 24 25 struct MatchResults { 26 RenderItemMatchList matches; 27 std::vector<RenderItem*> unmatchedLeft; 28 std::vector<RenderItem*> unmatchedRight; 29 30 double error; 31 }; 32 33 static const std::size_t MAXIMUM_SET_SIZE = 1000; 34 35 /// Computes an optimal matching between two renderable item sets. 36 /// @param lhs the "left-hand side" list of render items. 37 /// @param rhs the "right-hand side" list of render items. 38 /// Sets a list of match pairs, possibly self referencing, and an error estimate of the matching. operator ()(const RenderItemList & lhs,const RenderItemList & rhs) const39 inline virtual void operator()(const RenderItemList & lhs, const RenderItemList & rhs) const { 40 41 // Ensure the first argument is greater than next to aid the helper function's logic. 42 if (lhs.size() >= rhs.size()) { 43 _results.error = computeMatching(lhs, rhs); 44 setMatches(lhs, rhs); 45 } else { 46 _results.error = computeMatching(rhs, lhs); 47 setMatches(rhs, lhs); 48 } 49 50 51 } 52 RenderItemMatcher()53 RenderItemMatcher() {} ~RenderItemMatcher()54 virtual ~RenderItemMatcher() {} 55 matchResults()56 inline MatchResults & matchResults() { return _results; } 57 weight(int i,int j) const58 inline double weight(int i, int j) const { return _weights[i][j]; } 59 distanceFunction()60 MasterRenderItemDistance & distanceFunction() { return _distanceFunction; } 61 62 private: 63 mutable HungarianMethod<MAXIMUM_SET_SIZE> _hungarianMethod; 64 mutable double _weights[MAXIMUM_SET_SIZE][MAXIMUM_SET_SIZE]; 65 66 mutable MatchResults _results; 67 68 /// @idea interface this entirely allow overriding of its type. 69 mutable MasterRenderItemDistance _distanceFunction; 70 71 double computeMatching(const RenderItemList & lhs, const RenderItemList & rhs) const; 72 73 void setMatches(const RenderItemList & lhs_src, const RenderItemList & rhs_src) const; 74 75 }; 76 77 #endif 78