Commit | Line | Data |
---|---|---|

b311480e | 1 | // Created on: 2007-05-26 |

2 | // Created by: Andrey BETENEV | |

973c2be1 | 3 | // Copyright (c) 2007-2014 OPEN CASCADE SAS |

b311480e | 4 | // |

973c2be1 | 5 | // This file is part of Open CASCADE Technology software library. |

b311480e | 6 | // |

d5f74e42 | 7 | // This library is free software; you can redistribute it and/or modify it under |

8 | // the terms of the GNU Lesser General Public License version 2.1 as published | |

973c2be1 | 9 | // by the Free Software Foundation, with special exception defined in the file |

10 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT | |

11 | // distribution for complete text of the license and disclaimer of any warranty. | |

b311480e | 12 | // |

973c2be1 | 13 | // Alternatively, this file may be used under the terms of Open CASCADE |

14 | // commercial license or contractual agreement. | |

7fd59977 | 15 | |

16 | #ifndef NCollection_CellFilter_HeaderFile | |

17 | #define NCollection_CellFilter_HeaderFile | |

18 | ||

19 | #include <Standard_Real.hxx> | |

20 | #include <NCollection_List.hxx> | |

21 | #include <NCollection_Map.hxx> | |

22 | #include <NCollection_DataMap.hxx> | |

ddf2fe8e | 23 | #include <NCollection_IncAllocator.hxx> |

1c35b92f | 24 | #include <NCollection_TypeDef.hxx> |

7fd59977 | 25 | |

26 | //! Auxiliary enumeration serving as responce from method Inspect | |

27 | enum NCollection_CellFilter_Action | |

28 | { | |

29 | CellFilter_Keep = 0, //!< Target is needed and should be kept | |

30 | CellFilter_Purge = 1 //!< Target is not needed and can be removed from the current cell | |

31 | }; | |

32 | ||

33 | /** | |

34 | * A data structure for sorting geometric objects (called targets) in | |

35 | * n-dimensional space into cells, with associated algorithm for fast checking | |

36 | * of coincidence (overlapping, intersection, etc.) with other objects | |

37 | * (called here bullets). | |

38 | * | |

39 | * Description | |

40 | * | |

41 | * The algorithm is based on hash map, thus it has linear time of initialization | |

42 | * (O(N) where N is number of cells covered by added targets) and constant-time | |

43 | * search for one bullet (more precisely, O(M) where M is number of cells covered | |

44 | * by the bullet). | |

45 | * | |

46 | * The idea behind the algorithm is to separate each co-ordinate of the space | |

47 | * into equal-size cells. Note that this works well when cell size is | |

48 | * approximately equal to the characteristic size of the involved objects | |

49 | * (targets and bullets; including tolerance eventually used for coincidence | |

50 | * check). | |

51 | * | |

52 | * Usage | |

53 | * | |

54 | * The target objects to be searched are added to the tool by methods Add(); | |

55 | * each target is classified as belonging to some cell(s). The data on cells | |

56 | * (list of targets found in each one) are stored in the hash map with key being | |

57 | * cumulative index of the cell by all co-ordinates. | |

58 | * Thus the time needed to find targets in some cell is O(1) * O(number of | |

59 | * targets in the cell). | |

60 | * | |

61 | * As soon as all the targets are added, the algorithm is ready to check for | |

62 | * coincidence. | |

63 | * To find the targets coincident with any given bullet, it checks all the | |

64 | * candidate targets in the cell(s) covered by the bullet object | |

65 | * (methods Inspect()). | |

66 | * | |

67 | * The methods Add() and Inspect() have two flavours each: one accepts | |

68 | * single point identifying one cell, another accept two points specifying | |

69 | * the range of cells. It should be noted that normally at least one of these | |

70 | * methods is called as for range of cells: either due to objects having non- | |

71 | * zero size, or in order to account for the tolerance when objects are points. | |

72 | * | |

73 | * The set of targets can be modified during the process: new targets can be | |

74 | * added by Add(), existing targets can be removed by Remove(). | |

75 | * | |

76 | * Implementation | |

77 | * | |

78 | * The algorithm is implemented as template class, thus it is capable to | |

79 | * work with objects of any type. The only argument of the template should be | |

80 | * the specific class providing all necessary features required by the | |

81 | * algorithm: | |

82 | * | |

83 | * - typedef "Target" defining type of target objects. | |

84 | * This type must have copy constructor | |

85 | * | |

86 | * - typedef "Point" defining type of geometrical points used | |

87 | * | |

88 | * - enum Dimension whose value must be dimension of the point | |

89 | * | |

90 | * - method Coord() returning value of the i-th coordinate of the point: | |

91 | * | |

92 | * static Standard_Real Coord (int i, const Point& thePnt); | |

93 | * | |

94 | * Note that index i is from 0 to Dimension-1. | |

95 | * | |

96 | * - method IsEqual() used by Remove() to identify objects to be removed: | |

97 | * | |

98 | * Standard_Boolean IsEqual (const Target& theT1, const Target& theT2); | |

99 | * | |

100 | * - method Inspect() performing necessary actions on the candidate target | |

101 | * object (usially comparison with the currently checked bullet object): | |

102 | * | |

103 | * NCollection_CellFilter_Action Inspect (const Target& theObject); | |

104 | * | |

105 | * The returned value can be used to command CellFilter | |

106 | * to remove the inspected item from the current cell; this allows | |

107 | * to exclude the items that has been processed and are not needed any | |

108 | * more in further search (for better performance). | |

109 | * | |

110 | * Note that method Inspect() can be const and/or virtual. | |

111 | */ | |

112 | ||

113 | template <class Inspector> | |

114 | class NCollection_CellFilter | |

115 | { | |

116 | public: | |

1c35b92f | 117 | typedef TYPENAME Inspector::Target Target; |

118 | typedef TYPENAME Inspector::Point Point; | |

7fd59977 | 119 | |

120 | public: | |

121 | ||

122 | //! Constructor; initialized by cell size. | |

123 | //! | |

124 | //! Note: the cell size must be ensured to be greater than | |

125 | //! maximal co-ordinate of the involved points divided by INT_MAX, | |

126 | //! in order to avoid integer overflow of cell index. | |

127 | //! | |

128 | //! By default cell size is 0, which is invalid; thus if default | |

129 | //! constructor is used, the tool must be initialized later with | |

130 | //! appropriate cell size by call to Reset() | |

131 | NCollection_CellFilter (Standard_Real theCellSize=0, | |

132 | const Handle(NCollection_IncAllocator)& theAlloc=0) | |

133 | { | |

134 | Reset (theCellSize, theAlloc); | |

135 | } | |

136 | ||

137 | //! Constructor; initialized by cell sizes along each dimension. | |

138 | //! Note: the cell size in each dimension must be ensured to be greater than | |

139 | //! maximal co-ordinate of the involved points by this dimension divided by INT_MAX, | |

140 | //! in order to avoid integer overflow of cell index. | |

141 | NCollection_CellFilter (Standard_Real theCellSize[], | |

142 | const Handle(NCollection_IncAllocator)& theAlloc=0) | |

143 | { | |

144 | Reset (theCellSize, theAlloc); | |

145 | } | |

146 | ||

147 | //! Clear the data structures, set new cell size and allocator | |

148 | void Reset (Standard_Real theCellSize, | |

149 | const Handle(NCollection_IncAllocator)& theAlloc=0) | |

150 | { | |

151 | for (int i=0; i < Inspector::Dimension; i++) | |

152 | myCellSize[i] = theCellSize; | |

153 | resetAllocator ( theAlloc ); | |

154 | } | |

155 | ||

156 | //! Clear the data structures and set new cell sizes and allocator | |

157 | void Reset (Standard_Real theCellSize[], | |

158 | const Handle(NCollection_IncAllocator)& theAlloc=0) | |

159 | { | |

160 | for (int i=0; i < Inspector::Dimension; i++) | |

161 | myCellSize[i] = theCellSize[i]; | |

162 | resetAllocator ( theAlloc ); | |

163 | } | |

164 | ||

165 | //! Adds a target object for further search at a point (into only one cell) | |

166 | void Add (const Target& theTarget, const Point &thePnt) | |

167 | { | |

168 | Cell aCell (thePnt, myCellSize); | |

169 | add (aCell, theTarget); | |

170 | } | |

171 | ||

172 | //! Adds a target object for further search in the range of cells | |

173 | //! defined by two points (the first point must have all co-ordinates equal or | |

174 | //! less than the same co-ordinate of the second point) | |

175 | void Add (const Target& theTarget, | |

176 | const Point &thePntMin, const Point &thePntMax) | |

177 | { | |

178 | // get cells range by minimal and maximal co-ordinates | |

179 | Cell aCellMin (thePntMin, myCellSize); | |

180 | Cell aCellMax (thePntMax, myCellSize); | |

181 | Cell aCell = aCellMin; | |

182 | // add object recursively into all cells in range | |

183 | iterateAdd (Inspector::Dimension-1, aCell, aCellMin, aCellMax, theTarget); | |

184 | } | |

185 | ||

186 | //! Find a target object at a point and remove it from the structures. | |

187 | //! For usage of this method "operator ==" should be defined for Target. | |

188 | void Remove (const Target& theTarget, const Point &thePnt) | |

189 | { | |

190 | Cell aCell (thePnt, myCellSize); | |

191 | remove (aCell, theTarget); | |

192 | } | |

193 | ||

194 | //! Find a target object in the range of cells defined by two points and | |

195 | //! remove it from the structures | |

196 | //! (the first point must have all co-ordinates equal or | |

197 | //! less than the same co-ordinate of the second point). | |

198 | //! For usage of this method "operator ==" should be defined for Target. | |

199 | void Remove (const Target& theTarget, | |

200 | const Point &thePntMin, const Point &thePntMax) | |

201 | { | |

202 | // get cells range by minimal and maximal co-ordinates | |

203 | Cell aCellMin (thePntMin, myCellSize); | |

204 | Cell aCellMax (thePntMax, myCellSize); | |

205 | Cell aCell = aCellMin; | |

206 | // remove object recursively from all cells in range | |

207 | iterateRemove (Inspector::Dimension-1, aCell, aCellMin, aCellMax, theTarget); | |

208 | } | |

209 | ||

210 | //! Inspect all targets in the cell corresponding to the given point | |

211 | void Inspect (const Point& thePnt, Inspector &theInspector) | |

212 | { | |

213 | Cell aCell (thePnt, myCellSize); | |

214 | inspect (aCell, theInspector); | |

215 | } | |

216 | ||

217 | //! Inspect all targets in the cells range limited by two given points | |

218 | //! (the first point must have all co-ordinates equal or | |

219 | //! less than the same co-ordinate of the second point) | |

220 | void Inspect (const Point& thePntMin, const Point& thePntMax, | |

221 | Inspector &theInspector) | |

222 | { | |

223 | // get cells range by minimal and maximal co-ordinates | |

224 | Cell aCellMin (thePntMin, myCellSize); | |

225 | Cell aCellMax (thePntMax, myCellSize); | |

226 | Cell aCell = aCellMin; | |

227 | // inspect object recursively into all cells in range | |

228 | iterateInspect (Inspector::Dimension-1, aCell, | |

229 | aCellMin, aCellMax, theInspector); | |

230 | } | |

231 | ||

232 | #if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530) | |

233 | public: // work-around against obsolete SUN WorkShop 5.3 compiler | |

234 | #else | |

235 | protected: | |

236 | #endif | |

237 | ||

238 | /** | |

239 | * Auxiliary class for storing points belonging to the cell as the list | |

240 | */ | |

241 | struct ListNode { | |

242 | Target Object; | |

243 | ListNode *Next; | |

244 | }; | |

245 | ||

246 | /** | |

247 | * Auxilary structure representing a cell in the space. | |

248 | * Cells are stored in the map, each cell contains list of objects | |

249 | * that belong to that cell. | |

250 | */ | |

251 | struct Cell | |

252 | { | |

253 | public: | |

254 | //! Empty constructor -- required only for NCollection_Map, | |

255 | //! therefore does not initialize index (avoid cycle) | |

256 | Cell () : Objects(0) {} | |

257 | ||

258 | //! Constructor; computes cell indices | |

259 | Cell (const Point& thePnt, const Standard_Real theCellSize[]) | |

260 | : Objects(0) | |

261 | { | |

262 | for (int i=0; i < Inspector::Dimension; i++) | |

263 | { | |

264 | Standard_Real val = (Standard_Real)(Inspector::Coord(i, thePnt) / theCellSize[i]); | |

265 | //If the value of index is greater than | |

266 | //INT_MAX it is decreased correspondingly for the value of INT_MAX. If the value | |

267 | //of index is less than INT_MIN it is increased correspondingly for the absolute | |

268 | //value of INT_MIN. | |

269 | index[i] = long((val > INT_MAX - 1) ? fmod(val, (Standard_Real) INT_MAX) | |

270 | : (val < INT_MIN + 1) ? fmod(val, (Standard_Real) INT_MIN) | |

271 | : val); | |

272 | } | |

273 | } | |

274 | ||

275 | //! Copy constructor: ensure that list is not deleted twice | |

276 | Cell (const Cell& theOther) { (*this) = theOther; } | |

277 | ||

278 | //! Assignment operator: ensure that list is not deleted twice | |

279 | void operator = (const Cell& theOther) | |

280 | { | |

281 | for (int i=0; i < Inspector::Dimension; i++) | |

282 | index[i] = theOther.index[i]; | |

283 | Objects = theOther.Objects; | |

284 | ((Cell&)theOther).Objects = 0; | |

285 | } | |

286 | ||

287 | //! Destructor; calls destructors for targets contained in the list | |

288 | ~Cell () | |

289 | { | |

290 | for ( ListNode* aNode = Objects; aNode; aNode = aNode->Next ) | |

291 | aNode->Object.~Target(); | |

292 | // note that list nodes need not to be freed, since IncAllocator is used | |

293 | Objects = 0; | |

294 | } | |

295 | ||

296 | //! Compare cell with other one | |

297 | Standard_Boolean IsEqual (const Cell& theOther) const | |

298 | { | |

299 | for (int i=0; i < Inspector::Dimension; i++) | |

300 | if ( index[i] != theOther.index[i] ) return Standard_False; | |

301 | return Standard_True; | |

302 | } | |

303 | ||

304 | //! Compute hash code | |

305 | Standard_Integer HashCode (const Standard_Integer theUpper) const | |

306 | { | |

307 | // number of bits per each dimension in the hash code | |

308 | const Standard_Size aShiftBits = (BITS(long)-1) / Inspector::Dimension; | |

309 | long aCode=0; | |

310 | for (int i=0; i < Inspector::Dimension; i++) | |

311 | aCode = ( aCode << aShiftBits ) ^ index[i]; | |

312 | return (unsigned)aCode % theUpper; | |

313 | } | |

314 | ||

315 | public: | |

316 | long index[Inspector::Dimension]; | |

317 | ListNode *Objects; | |

318 | }; | |

319 | ||

320 | // definition of global functions is needed for map | |

321 | friend Standard_Integer HashCode (const Cell &aCell, const Standard_Integer theUpper) | |

322 | { return aCell.HashCode(theUpper); } | |

323 | friend Standard_Boolean IsEqual (const Cell &aCell1, const Cell &aCell2) | |

324 | { return aCell1.IsEqual(aCell2); } | |

325 | ||

326 | protected: | |

327 | ||

328 | //! Reset allocator to the new one | |

329 | void resetAllocator (const Handle(NCollection_IncAllocator)& theAlloc) | |

330 | { | |

331 | if ( theAlloc.IsNull() ) | |

332 | myAllocator = new NCollection_IncAllocator; | |

333 | else | |

334 | myAllocator = theAlloc; | |

335 | myCells.Clear ( myAllocator ); | |

336 | } | |

337 | ||

338 | //! Add a new target object into the specified cell | |

339 | void add (const Cell& theCell, const Target& theTarget) | |

340 | { | |

341 | // add a new cell or get reference to existing one | |

342 | Cell& aMapCell = (Cell&)myCells.Added (theCell); | |

343 | ||

344 | // create a new list node and add it to the beginning of the list | |

345 | ListNode* aNode = (ListNode*)myAllocator->Allocate(sizeof(ListNode)); | |

346 | new (&aNode->Object) Target (theTarget); | |

347 | aNode->Next = aMapCell.Objects; | |

348 | aMapCell.Objects = aNode; | |

349 | } | |

350 | ||

351 | //! Internal addition function, performing iteration for adjacent cells | |

352 | //! by one dimension; called recursively to cover all dimensions | |

353 | void iterateAdd (int idim, Cell &theCell, | |

354 | const Cell& theCellMin, const Cell& theCellMax, | |

355 | const Target& theTarget) | |

356 | { | |

357 | int start = theCellMin.index[idim]; | |

358 | int end = theCellMax.index[idim]; | |

359 | for (int i=start; i <= end; i++) { | |

360 | theCell.index[idim] = i; | |

361 | if ( idim ) // recurse | |

362 | iterateAdd (idim-1, theCell, theCellMin, theCellMax, theTarget); | |

363 | else // add to this cell | |

364 | add (theCell, theTarget); | |

365 | } | |

366 | } | |

367 | ||

368 | //! Remove the target object from the specified cell | |

369 | void remove (const Cell& theCell, const Target& theTarget) | |

370 | { | |

371 | // check if any objects are recorded in that cell | |

372 | if ( ! myCells.Contains (theCell) ) | |

373 | return; | |

374 | ||

375 | // iterate by objects in the cell and check each | |

376 | Cell& aMapCell = (Cell&)myCells.Added (theCell); | |

377 | ListNode* aNode = aMapCell.Objects; | |

378 | ListNode* aPrev = NULL; | |

379 | while (aNode) | |

380 | { | |

381 | ListNode* aNext = aNode->Next; | |

382 | if (Inspector::IsEqual (aNode->Object, theTarget)) | |

383 | { | |

384 | aNode->Object.~Target(); | |

385 | (aPrev ? aPrev->Next : aMapCell.Objects) = aNext; | |

386 | // note that aNode itself need not to be freed, since IncAllocator is used | |

387 | } | |

388 | else | |

389 | aPrev = aNode; | |

390 | aNode = aNext; | |

391 | } | |

392 | } | |

393 | ||

394 | //! Internal removal function, performing iteration for adjacent cells | |

395 | //! by one dimension; called recursively to cover all dimensions | |

396 | void iterateRemove (int idim, Cell &theCell, | |

397 | const Cell& theCellMin, const Cell& theCellMax, | |

398 | const Target& theTarget) | |

399 | { | |

400 | int start = theCellMin.index[idim]; | |

401 | int end = theCellMax.index[idim]; | |

402 | for (int i=start; i <= end; i++) { | |

403 | theCell.index[idim] = i; | |

404 | if ( idim ) // recurse | |

405 | iterateRemove (idim-1, theCell, theCellMin, theCellMax, theTarget); | |

406 | else // remove from this cell | |

407 | remove (theCell, theTarget); | |

408 | } | |

409 | } | |

410 | ||

411 | //! Inspect the target objects in the specified cell. | |

412 | void inspect (const Cell& theCell, Inspector& theInspector) | |

413 | { | |

414 | // check if any objects are recorded in that cell | |

415 | if ( ! myCells.Contains (theCell) ) | |

416 | return; | |

417 | ||

418 | // iterate by objects in the cell and check each | |

419 | Cell& aMapCell = (Cell&)myCells.Added (theCell); | |

420 | ListNode* aNode = aMapCell.Objects; | |

421 | ListNode* aPrev = NULL; | |

422 | while(aNode) { | |

423 | ListNode* aNext = aNode->Next; | |

424 | NCollection_CellFilter_Action anAction = | |

425 | theInspector.Inspect (aNode->Object); | |

426 | // delete items requested to be purged | |

427 | if ( anAction == CellFilter_Purge ) { | |

428 | aNode->Object.~Target(); | |

429 | (aPrev ? aPrev->Next : aMapCell.Objects) = aNext; | |

430 | // note that aNode itself need not to be freed, since IncAllocator is used | |

431 | } | |

432 | else | |

433 | aPrev = aNode; | |

434 | aNode = aNext; | |

435 | } | |

436 | } | |

437 | ||

438 | //! Inspect the target objects in the specified range of the cells | |

439 | void iterateInspect (int idim, Cell &theCell, | |

440 | const Cell& theCellMin, const Cell& theCellMax, | |

441 | Inspector& theInspector) | |

442 | { | |

443 | int start = theCellMin.index[idim]; | |

444 | int end = theCellMax.index[idim]; | |

445 | for (int i=start; i <= end; i++) { | |

446 | theCell.index[idim] = i; | |

447 | if ( idim ) // recurse | |

448 | iterateInspect (idim-1, theCell, theCellMin, theCellMax, theInspector); | |

449 | else // inspect this cell | |

450 | inspect (theCell, theInspector); | |

451 | } | |

452 | } | |

453 | ||

454 | protected: | |

455 | Handle(NCollection_BaseAllocator) myAllocator; | |

456 | NCollection_Map<Cell> myCells; | |

457 | Standard_Real myCellSize [Inspector::Dimension]; | |

458 | }; | |

459 | ||

460 | /** | |

461 | * Base class defining part of the Inspector interface | |

462 | * for CellFilter algorithm, working with gp_XYZ points in 3d space | |

463 | */ | |

464 | ||

465 | class gp_XYZ; | |

466 | struct NCollection_CellFilter_InspectorXYZ | |

467 | { | |

468 | //! Points dimension | |

469 | enum { Dimension = 3 }; | |

470 | ||

471 | //! Points type | |

472 | typedef gp_XYZ Point; | |

473 | ||

474 | //! Access to co-ordinate | |

475 | static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); } | |

476 | ||

477 | //! Auxiliary method to shift point by each coordinate on given value; | |

478 | //! useful for preparing a points range for Inspect with tolerance | |

479 | Point Shift (const Point& thePnt, Standard_Real theTol) const | |

480 | { return Point (thePnt.X() + theTol, thePnt.Y() + theTol, thePnt.Z() + theTol); } | |

481 | }; | |

482 | ||

483 | /** | |

484 | * Base class defining part of the Inspector interface | |

485 | * for CellFilter algorithm, working with gp_XY points in 2d space | |

486 | */ | |

487 | ||

488 | class gp_XY; | |

489 | struct NCollection_CellFilter_InspectorXY | |

490 | { | |

491 | //! Points dimension | |

492 | enum { Dimension = 2 }; | |

493 | ||

494 | //! Points type | |

495 | typedef gp_XY Point; | |

496 | ||

497 | //! Access to co-ordinate | |

498 | static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); } | |

499 | ||

500 | //! Auxiliary method to shift point by each coordinate on given value; | |

501 | //! useful for preparing a points range for Inspect with tolerance | |

502 | Point Shift (const Point& thePnt, Standard_Real theTol) const | |

503 | { return Point (thePnt.X() + theTol, thePnt.Y() + theTol); } | |

504 | }; | |

505 | ||

506 | #endif | |

507 |