diff options
author | Yury Melnichek <melnichek@gmail.com> | 2011-09-10 16:18:40 +0400 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 01:23:33 +0300 |
commit | 4be41d23fef29b2565b5daa62f81fa77a487352e (patch) | |
tree | 03cdda84e33af1084d557c33d326d217d4995744 /geometry/covering.hpp | |
parent | 8dbf49350de70a2caf7c8ae32e3b1d66a9f5d0f1 (diff) |
Rename geometry/covering.hpp -> geometry/covering_utils.hpp.
Diffstat (limited to 'geometry/covering.hpp')
-rw-r--r-- | geometry/covering.hpp | 97 |
1 files changed, 0 insertions, 97 deletions
diff --git a/geometry/covering.hpp b/geometry/covering.hpp deleted file mode 100644 index 52c6551da9..0000000000 --- a/geometry/covering.hpp +++ /dev/null @@ -1,97 +0,0 @@ -#pragma once -#include "../geometry/point2d.hpp" -#include "../base/assert.hpp" -#include "../base/base.hpp" -#include "../base/buffer_vector.hpp" -#include "../base/logging.hpp" -#include "../base/math.hpp" -#include "../std/algorithm.hpp" - -namespace covering -{ - -enum CellObjectIntersection -{ - CELL_OBJECT_NO_INTERSECTION = 0, - CELL_OBJECT_INTERSECT = 1, - CELL_INSIDE_OBJECT = 2, - OBJECT_INSIDE_CELL = 3 -}; - -template <class CellIdT> -inline CellObjectIntersection IntersectCellWithLine(CellIdT const cell, - m2::PointD const & a, - m2::PointD const & b) -{ - pair<uint32_t, uint32_t> const xy = cell.XY(); - uint32_t const r = cell.Radius(); - m2::PointD const cellCorners[4] = - { - m2::PointD(xy.first - r, xy.second - r), - m2::PointD(xy.first - r, xy.second + r), - m2::PointD(xy.first + r, xy.second + r), - m2::PointD(xy.first + r, xy.second - r) - }; - for (int i = 0; i < 4; ++i) - if (m2::SegmentsIntersect(a, b, cellCorners[i], cellCorners[i == 0 ? 3 : i - 1])) - return CELL_OBJECT_INTERSECT; - if (xy.first - r <= a.x && a.x <= xy.first + r && xy.second - r <= a.y && a.y <= xy.second + r) - return OBJECT_INSIDE_CELL; - return CELL_OBJECT_NO_INTERSECTION; -} - -template <class CellIdT> -CellObjectIntersection IntersectCellWithTriangle( - CellIdT const cell, m2::PointD const & a, m2::PointD const & b, m2::PointD const & c) -{ - CellObjectIntersection const i1 = IntersectCellWithLine(cell, a, b); - if (i1 == CELL_OBJECT_INTERSECT) - return CELL_OBJECT_INTERSECT; - CellObjectIntersection const i2 = IntersectCellWithLine(cell, b, c); - if (i2 == CELL_OBJECT_INTERSECT) - return CELL_OBJECT_INTERSECT; - CellObjectIntersection const i3 = IntersectCellWithLine(cell, c, a); - if (i3 == CELL_OBJECT_INTERSECT) - return CELL_OBJECT_INTERSECT; - ASSERT_EQUAL(i1, i2, (cell, a, b, c)); - ASSERT_EQUAL(i2, i3, (cell, a, b, c)); - ASSERT_EQUAL(i3, i1, (cell, a, b, c)); - return i1; -} - -template <class CellIdT, class CellIdContainerT, typename IntersectF> -void CoverObject(IntersectF const & intersect, uint64_t cellPenaltyArea, CellIdContainerT & out, - CellIdT cell) -{ - uint64_t const cellArea = my::sq(uint64_t(1 << (CellIdT::DEPTH_LEVELS - 1 - cell.Level()))); - CellObjectIntersection const intersection = intersect(cell); - - if (intersection == CELL_OBJECT_NO_INTERSECTION) - return; - if (intersection == CELL_INSIDE_OBJECT || - cell.Level() == CellIdT::DEPTH_LEVELS - 1 || - cellPenaltyArea >= cellArea) - { - out.push_back(cell); - return; - } - - buffer_vector<CellIdT, 32> subdiv; - for (uint8_t i = 0; i < 4; ++i) - CoverObject(intersect, cellPenaltyArea, subdiv, cell.Child(i)); - - uint64_t subdivArea = 0; - for (size_t i = 0; i < subdiv.size(); ++i) - subdivArea += my::sq(uint64_t(1 << (CellIdT::DEPTH_LEVELS - 1 - subdiv[i].Level()))); - - ASSERT(!subdiv.empty(), (cellPenaltyArea, out, cell)); - - if (subdiv.empty() || cellPenaltyArea * (int(subdiv.size()) - 1) >= cellArea - subdivArea) - out.push_back(cell); - else - for (size_t i = 0; i < subdiv.size(); ++i) - out.push_back(subdiv[i]); -} - - -} // namespace covering |