CDirectionalOptimalPathSolver.h
Go to the documentation of this file.
1 #ifndef iipr_CDirectionalOptimalPathSolver_included
2 #define iipr_CDirectionalOptimalPathSolver_included
3 
4 
5 // STL includes
6 #include <map>
7 
8 // ACF includes
9 #include <istd/CIndex2d.h>
10 #include <iimg/CScanlineMask.h>
11 #include <iimg/CGeneralBitmap.h>
12 
13 
14 #ifdef __clang__
15  #define __forceinline __attribute__((always_inline))
16 #elif defined(__GNUC__) && !defined(__forceinline)
17  #define __forceinline inline
18 #endif
19 
20 
21 namespace iipr
22 {
23 
24 
26 {
27 public:
29 
30  bool Initialize(
31  const i2d::CVector2d& beginPoint,
32  const iimg::IBitmap& costOffsetBitmap,
33  const iimg::IBitmap& costXBitmap,
34  const iimg::IBitmap& costYBitmap,
35  const iimg::CScanlineMask& costBitmapMask,
36  double dirFactor);
37 
38  bool IsInitialized() const;
39 
44  bool CalculateCostData(
45  const QVector<i2d::CVector2d>& destPoints,
46  double maxCost,
47  int minDestPoints);
52  double GetOptimalPath(
53  const i2d::CVector2d& destPoint,
54  i2d::CPolypoint* optimalPathPtr = NULL) const;
55 
56 protected:
57  typedef std::multimap<double, istd::CIndex2d> ProcessingQueue;
58 
59  struct CostElement
60  {
61  qint8 revDirCode;
62  qint8 invMask;
63  float costSum;
64  float costX;
65  float costY;
66  float costOffset;
67  };
68 
70  {
71  Neighbourhood(float distance, float dirX, float dirY, int revDirCode)
72  {
73  this->distance = distance;
74  this->dirX = dirX;
75  this->dirY = dirY;
76  this->revDirCode = quint8(revDirCode);
77  this->invMask = quint8(~(1 << revDirCode));
78  }
79  float distance;
80  float dirX;
81  float dirY;
82  quint8 revDirCode;
83  quint8 invMask;
84  };
85 
86  void TryChangeNeighbour(
87  const CostElement& element,
88  const Neighbourhood& neigbourhood,
89  const istd::CIndex2d& neighbourIndex,
90  CostElement& neighbourElement);
91  bool PopNextElement(istd::CIndex2d& elementIndex, float& elementCostSum);
92 
93 private:
94  bool m_isInitialized;
95  float m_processedCostSum;
96  istd::CIndex2d m_startIndex;
97  ProcessingQueue m_processingQueue;
98  istd::CIndex2d m_workMapPos;
99  iimg::CGeneralBitmap m_workMap;
100 };
101 
102 
103 // inline public methods
104 
106 {
107  return m_isInitialized;
108 }
109 
110 
111 // inline protected methods
112 
114  const CostElement& element,
115  const Neighbourhood& neigbourhood,
116  const istd::CIndex2d& neighbourIndex,
117  CostElement& neighbourElement)
118 {
119  Q_ASSERT(element.costSum >= 0);
120 
121  if (neighbourElement.costSum > 0){
122  Q_ASSERT(neighbourElement.costSum >= 0);
123 
124  double edgeCost =
125  element.costOffset + neighbourElement.costOffset +
126  (element.costX + neighbourElement.costX) * neigbourhood.dirX +
127  (element.costY + neighbourElement.costY) * neigbourhood.dirY;
128  float costSum = (edgeCost > 0)? element.costSum + edgeCost * neigbourhood.distance: element.costSum;
129 
130  if (costSum < neighbourElement.costSum){
131  m_processingQueue.insert(ProcessingQueue::value_type(costSum, neighbourIndex));
132 
133  neighbourElement.revDirCode = neigbourhood.revDirCode;
134  neighbourElement.invMask &= neigbourhood.invMask;
135  neighbourElement.costSum = costSum;
136  }
137  }
138 }
139 
140 
141 __forceinline bool CDirectionalOptimalPathSolver::PopNextElement(istd::CIndex2d& elementIndex, float& elementCostSum)
142 {
143  ProcessingQueue::iterator nearestNodeIter = m_processingQueue.begin();
144  if (nearestNodeIter != m_processingQueue.end()){
145  elementIndex = nearestNodeIter->second;
146  elementCostSum = nearestNodeIter->first;
147 
148  m_processingQueue.erase(nearestNodeIter);
149 
150  return true;
151  }
152 
153  return false;
154 }
155 
156 
157 } // namespace iipr
158 
159 
160 #endif // !iipr_CDirectionalOptimalPathSolver_included
161 
162 
bool Initialize(const i2d::CVector2d &beginPoint, const iimg::IBitmap &costOffsetBitmap, const iimg::IBitmap &costXBitmap, const iimg::IBitmap &costYBitmap, const iimg::CScanlineMask &costBitmapMask, double dirFactor)
bool CalculateCostData(const QVector< i2d::CVector2d > &destPoints, double maxCost, int minDestPoints)
Calculates bitmap containing cost from begin point to each pixel (it stops when cost to all destinati...
bool PopNextElement(istd::CIndex2d &elementIndex, float &elementCostSum)
std::multimap< double, istd::CIndex2d > ProcessingQueue
double GetOptimalPath(const i2d::CVector2d &destPoint, i2d::CPolypoint *optimalPathPtr=NULL) const
Get cost of optimal path.
void TryChangeNeighbour(const CostElement &element, const Neighbourhood &neigbourhood, const istd::CIndex2d &neighbourIndex, CostElement &neighbourElement)
#define NULL
Neighbourhood(float distance, float dirX, float dirY, int revDirCode)

© 2007-2017 Witold Gantzke and Kirill Lepskiy