GridN.h
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2010, Rice University
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Rice University nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 /* Author: Ioan Sucan */
36 
37 #ifndef OMPL_DATASTRUCTURES_GRID_N_
38 #define OMPL_DATASTRUCTURES_GRID_N_
39 
40 #include "ompl/datastructures/Grid.h"
41 
42 namespace ompl
43 {
44 
46  template <typename _T>
47  class GridN : public Grid<_T>
48  {
49  public:
50 
52  typedef typename Grid<_T>::Cell BaseCell;
53 
56 
58  typedef typename Grid<_T>::Coord Coord;
59 
61  struct Cell : public BaseCell
62  {
64  unsigned int neighbors;
65 
67  bool border;
68 
69  Cell() : BaseCell(), neighbors(0), border(true)
70  {
71  }
72 
73  virtual ~Cell()
74  {
75  }
76  };
77 
79  typedef std::vector<Cell*> CellArray;
80 
81 
83  explicit
84  GridN(unsigned int dimension) : Grid<_T>(dimension)
85  {
86  hasBounds_ = false;
88  setDimension(dimension);
89  }
90 
91  virtual ~GridN()
92  {
93  }
94 
97  void setDimension(unsigned int dimension)
98  {
99  assert(Grid<_T>::empty() == true);
100  Grid<_T>::dimension_ = dimension;
101  Grid<_T>::maxNeighbors_ = 2 * dimension;
104  }
105 
106 
115  void setBounds(const Coord &low, const Coord &up)
116  {
117  lowBound_ = low;
118  upBound_ = up;
119  hasBounds_ = true;
120  }
121 
124  void setInteriorCellNeighborLimit(unsigned int count)
125  {
127  assert(interiorCellNeighborsLimit_ > 0);
129  }
130 
132  Cell* getCell(const Coord &coord) const
133  {
134  return static_cast<Cell*>(Grid<_T>::getCell(coord));
135  }
136 
138  void neighbors(const Cell* cell, CellArray& list) const
139  {
140  Coord test = cell->coord;
141  neighbors(test, list);
142  }
143 
145  void neighbors(const Coord& coord, CellArray& list) const
146  {
147  Coord test = coord;
148  neighbors(test, list);
149  }
150 
152  void neighbors(Coord& coord, CellArray& list) const
153  {
154  BaseCellArray baselist;
155  Grid<_T>::neighbors(coord, baselist);
156  list.reserve(list.size() + baselist.size());
157  for (unsigned int i = 0 ; i < baselist.size() ; ++i)
158  list.push_back(static_cast<Cell*>(baselist[i]));
159  }
160 
166  virtual BaseCell* createCell(const Coord& coord, BaseCellArray *nbh = NULL)
167  {
168  Cell *cell = new Cell();
169  cell->coord = coord;
170 
171  BaseCellArray *list = nbh ? nbh : new BaseCellArray();
172  Grid<_T>::neighbors(cell->coord, *list);
173 
174  for (typename BaseCellArray::iterator cl = list->begin() ; cl != list->end() ; ++cl)
175  {
176  Cell* c = static_cast<Cell*>(*cl);
177  c->neighbors++;
178  if (c->border && c->neighbors >= interiorCellNeighborsLimit_)
179  c->border = false;
180  }
181 
182  cell->neighbors = numberOfBoundaryDimensions(cell->coord) + list->size();
183  if (cell->border && cell->neighbors >= interiorCellNeighborsLimit_)
184  cell->border = false;
185 
186  if (!nbh)
187  delete list;
188 
189  return cell;
190  }
191 
194  virtual bool remove(BaseCell *cell)
195  {
196  if (cell)
197  {
198  BaseCellArray *list = new BaseCellArray();
199  Grid<_T>::neighbors(cell->coord, *list);
200  for (typename BaseCellArray::iterator cl = list->begin() ; cl != list->end() ; ++cl)
201  {
202  Cell* c = static_cast<Cell*>(*cl);
203  c->neighbors--;
204  if (!c->border && c->neighbors < interiorCellNeighborsLimit_)
205  c->border = true;
206  }
207  delete list;
208  typename Grid<_T>::CoordHash::iterator pos = Grid<_T>::hash_.find(&cell->coord);
209  if (pos != Grid<_T>::hash_.end())
210  {
211  Grid<_T>::hash_.erase(pos);
212  return true;
213  }
214  }
215  return false;
216  }
217 
219  void getCells(CellArray &cells) const
220  {
222  i != Grid<_T>::hash_.end() ; ++i)
223  cells.push_back(static_cast<Cell*>(i->second));
224  }
225 
226  protected:
227 
229  unsigned int numberOfBoundaryDimensions(const Coord &coord) const
230  {
231  unsigned int result = 0;
232  if (hasBounds_)
233  {
234  for (unsigned int i = 0 ; i < Grid<_T>::dimension_ ; ++i)
235  if (coord[i] == lowBound_[i] || coord[i] == upBound_[i])
236  result++;
237  }
238  return result;
239  }
240 
243 
245  Coord lowBound_;
246 
248  Coord upBound_;
249 
254 
258  };
259 }
260 
261 #endif
void neighbors(Coord &coord, CellArray &list) const
Get the list of neighbors for a given coordinate.
Definition: GridN.h:152
Representation of a simple grid.
Definition: Grid.h:51
unsigned int neighbors
The number of neighbors.
Definition: GridN.h:64
void setBounds(const Coord &low, const Coord &up)
Definition: GridN.h:115
Grid< _T >::CellArray BaseCellArray
Datatype for array of cells in base class.
Definition: GridN.h:55
void setInteriorCellNeighborLimit(unsigned int count)
Definition: GridN.h:124
Grid< _T >::Cell BaseCell
Datatype for cell in base class.
Definition: GridN.h:52
std::vector< int > Coord
Definition of a coordinate within this grid.
Definition: Grid.h:56
void getCells(CellArray &cells) const
Get the set of instantiated cells in the grid.
Definition: GridN.h:219
bool overrideCellNeighborsLimit_
Definition: GridN.h:257
virtual BaseCell * createCell(const Coord &coord, BaseCellArray *nbh=NULL)
Definition: GridN.h:166
Coord coord
The coordinate of the cell.
Definition: Grid.h:65
unsigned int numberOfBoundaryDimensions(const Coord &coord) const
Compute how many sides of a coordinate touch the boundaries of the grid.
Definition: GridN.h:229
void setDimension(unsigned int dimension)
Definition: GridN.h:97
Grid< _T >::Coord Coord
Datatype for cell coordinates.
Definition: GridN.h:58
std::vector< Cell * > CellArray
The datatype for arrays of cells.
Definition: Grid.h:77
Main namespace. Contains everything in this library.
Definition: Cost.h:42
Cell * getCell(const Coord &coord) const
Get the cell at a specified coordinate.
Definition: Grid.h:122
GridN(unsigned int dimension)
The constructor takes the dimension of the grid as argument.
Definition: GridN.h:84
bool border
A flag indicating whether this cell is on the border or not.
Definition: GridN.h:67
Representation of a grid where cells keep track of how many neighbors they have.
Definition: GridN.h:47
iterator end() const
Return the end() iterator for the grid.
Definition: Grid.h:383
std::vector< Cell * > CellArray
The datatype for arrays of cells.
Definition: GridN.h:79
void neighbors(const Coord &coord, CellArray &list) const
Get the list of neighbors for a given coordinate.
Definition: GridN.h:145
Coord lowBound_
If bounds are set, this defines the lower corner cell.
Definition: GridN.h:245
Definition of a cell in this grid.
Definition: Grid.h:59
bool hasBounds_
Flag indicating whether bounds are in effect for this grid.
Definition: GridN.h:242
unsigned int interiorCellNeighborsLimit_
Definition: GridN.h:253
iterator begin() const
Return the begin() iterator for the grid.
Definition: Grid.h:377
void neighbors(const Cell *cell, CellArray &list) const
Get the list of neighbors for a given cell.
Definition: GridN.h:138
void neighbors(const Cell *cell, CellArray &list) const
Get the list of neighbors for a given cell.
Definition: Grid.h:130
Cell * getCell(const Coord &coord) const
Get the cell at a specified coordinate.
Definition: GridN.h:132
Definition of a cell in this grid.
Definition: GridN.h:61
Coord upBound_
If bounds are set, this defines the upper corner cell.
Definition: GridN.h:248