From 5a4d268daf2f54893250357a0c961375eafb4ff5 Mon Sep 17 00:00:00 2001 From: Roman Sorokin Date: Wed, 20 Aug 2014 16:46:57 +0300 Subject: Improved OverlayTree --- drape/overlay_tree.cpp | 95 ++++++++++++-------------------------------------- drape/overlay_tree.hpp | 63 +++++++++++---------------------- geometry/tree4d.hpp | 23 ++++++++---- 3 files changed, 60 insertions(+), 121 deletions(-) diff --git a/drape/overlay_tree.cpp b/drape/overlay_tree.cpp index b00d3cbd29..d9e3367912 100644 --- a/drape/overlay_tree.cpp +++ b/drape/overlay_tree.cpp @@ -7,109 +7,60 @@ namespace dp void OverlayTree::StartOverlayPlacing(ScreenBase const & screen, bool canOverlap) { - m_modelView = screen; + m_traits.m_modelView = screen; m_canOverlap = canOverlap; - ASSERT(m_tree.empty(), ()); + ASSERT(IsEmpty(), ()); } void OverlayTree::Add(RefPointer handle) { + ScreenBase const & modelView = GetModelView(); + handle->SetIsVisible(m_canOverlap); - handle->Update(m_modelView); + handle->Update(modelView); if (!handle->IsValid()) return; - - m2::RectD pixelRect = handle->GetPixelRect(m_modelView); - find_result_t elements; + m2::RectD const pixelRect = handle->GetPixelRect(modelView); + + typedef buffer_vector, 8> OverlayContainerT; + OverlayContainerT elements; /* * Find elements that already on OverlayTree and it's pixel rect * intersect with handle pixel rect ("Intersected elements") */ - FindIntersectedFunctor f(pixelRect, elements); - m_tree.for_each(f); + ForEachInRect(pixelRect, [&] (RefPointer r) + { + if (handle->IsIntersect(modelView, *r.GetRaw())) + elements.push_back(r); + }); - double inputPriority = handle->GetPriority(); + double const inputPriority = handle->GetPriority(); /* * In this loop we decide which element must be visible * If input element "handle" more priority than all "Intersected elements" * than we remove all "Intersected elements" and insert input element "handle" * But if some of already inserted elements more priority than we don't insert "handle" */ - for (find_result_t::const_iterator it = elements.begin(); it != elements.end(); ++it) - { - if (inputPriority < (*it)->m_nodeValue->GetPriority()) + for (OverlayContainerT::const_iterator it = elements.begin(); it != elements.end(); ++it) + if (inputPriority < (*it)->GetPriority()) return; - } - for (find_result_t::const_iterator it = elements.begin(); it != elements.end(); ++it) - m_tree.erase(*(*it)); + for (OverlayContainerT::const_iterator it = elements.begin(); it != elements.end(); ++it) + Erase(*it); - m_tree.insert(Node(handle, pixelRect)); + BaseT::Add(handle, pixelRect); } void OverlayTree::EndOverlayPlacing() { - for (tree_t::const_iterator it = m_tree.begin(); it != m_tree.end(); ++it) + ForEach([] (RefPointer handle) { - RefPointer handle = (*it).m_nodeValue; handle->SetIsVisible(true); - } - m_tree.clear(); -} - -//////////////////////////////////////////////// -OverlayTree::Node::Node(RefPointer handle, - m2::RectD const & pixelRect) - : m_nodeValue(handle) -{ - m_pts[0] = pixelRect.minX(); - m_pts[1] = pixelRect.minY(); - m_pts[2] = pixelRect.maxX(); - m_pts[3] = pixelRect.maxY(); -} - -OverlayTree::BaseFindFunctor::BaseFindFunctor(m2::RectD const & r) - : m_rect(r) -{ -} - -bool OverlayTree::BaseFindFunctor::ScanLeft(size_t plane, Node const & v) const -{ - switch (plane & 3) // % 4 - { - case 2: return m_rect.minX() < v[2]; - case 3: return m_rect.minY() < v[3]; - default: return true; - } -} - -bool OverlayTree::BaseFindFunctor::ScanRight(size_t plane, Node const & v) const -{ - switch (plane & 3) // % 4 - { - case 0: return m_rect.maxX() > v[0]; - case 1: return m_rect.maxY() > v[1]; - default: return true; - } -} - -OverlayTree::FindIntersectedFunctor::FindIntersectedFunctor(m2::RectD const & r, - find_result_t & intersections) - : base_t(r) - , m_intersections(intersections) -{ -} - -void OverlayTree::FindIntersectedFunctor::operator()(OverlayTree::Node const & node) -{ - m2::RectD const & r = base_t::m_rect; + }); - bool isIntersect = !((node.m_pts[2] <= r.minX()) || (node.m_pts[0] >= r.maxX()) || - (node.m_pts[3] <= r.minY()) || (node.m_pts[1] >= r.maxY())); - if (isIntersect) - m_intersections.push_back(&node); + Clear(); } } // namespace dp diff --git a/drape/overlay_tree.hpp b/drape/overlay_tree.hpp index 29344086af..2b7b994690 100644 --- a/drape/overlay_tree.hpp +++ b/drape/overlay_tree.hpp @@ -2,65 +2,42 @@ #include "overlay_handle.hpp" -#include "../base/buffer_vector.hpp" #include "../geometry/screenbase.hpp" +#include "../geometry/tree4d.hpp" -#include "../std/kdtree.hpp" namespace dp { -class OverlayTree +namespace detail { -public: - void StartOverlayPlacing(ScreenBase const & screen, bool canOverlap = false); - void Add(RefPointer handle); - void EndOverlayPlacing(); - -private: - struct Node - { - typedef double value_type; - - Node(RefPointer handle, m2::RectD const & pixelRect); - - RefPointer m_nodeValue; - double m_pts[4]; - - double operator[] (size_t i) const { return m_pts[i]; } - }; +struct OverlayTraits +{ ScreenBase m_modelView; - typedef KDTree::KDTree<4, Node> tree_t; - tree_t m_tree; - bool m_canOverlap; -private: - typedef buffer_vector find_result_t; - - class BaseFindFunctor + inline m2::RectD const LimitRect(RefPointer handle) { - public: - BaseFindFunctor(m2::RectD const & r); + return handle->GetPixelRect(m_modelView); + } +}; - bool ScanLeft(size_t plane, Node const & v) const; - bool ScanRight(size_t plane, Node const & v) const; +} - protected: - m2::RectD const & m_rect; - }; +class OverlayTree : public m4::Tree, detail::OverlayTraits> +{ + typedef m4::Tree, detail::OverlayTraits> BaseT; - class FindIntersectedFunctor : public BaseFindFunctor - { - typedef BaseFindFunctor base_t; - public: - FindIntersectedFunctor(m2::RectD const & r, find_result_t & intersections); +public: + void StartOverlayPlacing(ScreenBase const & screen, bool canOverlap = false); + void Add(RefPointer handle); + void EndOverlayPlacing(); - void operator()(Node const & node); +private: + ScreenBase const & GetModelView() const { return m_traits.m_modelView; } - private: - find_result_t & m_intersections; - }; +private: + bool m_canOverlap; }; } // namespace dp diff --git a/geometry/tree4d.hpp b/geometry/tree4d.hpp index c4ec54fbdf..99629243f7 100644 --- a/geometry/tree4d.hpp +++ b/geometry/tree4d.hpp @@ -12,15 +12,15 @@ namespace m4 { template - struct Traits + struct TraitsDef { - m2::RectD const LimitRect(T const & t) + m2::RectD const LimitRect(T const & t) const { return t.GetLimitRect(); } }; - template > + template > class Tree { struct value_t @@ -53,7 +53,7 @@ namespace m4 { ostringstream out; - out << m_val.get() << ", (" + out << DebugPrint(m_val) << ", (" << m_pts[0] << ", " << m_pts[1] << ", " << m_pts[2] << ", " @@ -141,13 +141,18 @@ namespace m4 } }; + protected: + Traits m_traits; + m2::RectD GetLimitRect(T const & t) const { return m_traits.LimitRect(t); } + public: + Tree(Traits const & traits = Traits()) : m_traits(traits) {} typedef T elem_t; void Add(T const & obj) { - Add(obj, Traits::LimitRect(obj)); + Add(obj, GetLimitRect(obj)); } void Add(T const & obj, m2::RectD const & rect) @@ -177,10 +182,16 @@ namespace m4 m_tree.erase_exact(val); } + void Erase(T const & obj) + { + value_t val(obj, m_traits.LimitRect(obj)); + m_tree.erase_exact(val); + } + template void ReplaceIf(T const & obj, TCompare comp) { - ReplaceIf(obj, Traits::LimitRect(obj), comp); + ReplaceIf(obj, GetLimitRect(obj), comp); } template -- cgit v1.2.3