Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file SUMORTree.h
15 : /// @author Daniel Krajzewicz
16 : /// @date 27.10.2008
17 : ///
18 : // A RT-tree for efficient storing of SUMO's GL-objects
19 : /****************************************************************************/
20 : #pragma once
21 : #include <config.h>
22 :
23 : #include <utils/foxtools/fxheader.h>
24 : #include <utils/common/MsgHandler.h>
25 : #include <utils/geom/Boundary.h>
26 : #include <utils/gui/globjects/GUIGlObject.h>
27 : #include <utils/gui/settings/GUIVisualizationSettings.h>
28 : #include <utils/gui/div/GUIIOGlobals.h>
29 :
30 : #include "RTree.h"
31 :
32 :
33 : #define GUI_RTREE_QUAL RTree<GUIGlObject*, GUIGlObject, float, 2, GUIVisualizationSettings>
34 :
35 : // specialized implementation for speedup and avoiding warnings
36 :
37 : template<>
38 : inline float GUI_RTREE_QUAL::RectSphericalVolume(Rect* a_rect) {
39 : ASSERT(a_rect);
40 10103440 : const float extent0 = a_rect->m_max[0] - a_rect->m_min[0];
41 10103440 : const float extent1 = a_rect->m_max[1] - a_rect->m_min[1];
42 6973373 : return .78539816f * (extent0 * extent0 + extent1 * extent1);
43 : }
44 :
45 : template<>
46 : inline GUI_RTREE_QUAL::Rect GUI_RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB) {
47 : ASSERT(a_rectA && a_rectB);
48 : Rect newRect;
49 9861706 : newRect.m_min[0] = rtree_min(a_rectA->m_min[0], a_rectB->m_min[0]);
50 9861706 : newRect.m_max[0] = rtree_max(a_rectA->m_max[0], a_rectB->m_max[0]);
51 9861706 : newRect.m_min[1] = rtree_min(a_rectA->m_min[1], a_rectB->m_min[1]);
52 9861706 : newRect.m_max[1] = rtree_max(a_rectA->m_max[1], a_rectB->m_max[1]);
53 : return newRect;
54 : }
55 :
56 :
57 : // ===========================================================================
58 : // class definitions
59 : // ===========================================================================
60 : /** @class SUMORTree
61 : * @brief A RT-tree for efficient storing of SUMO's GL-objects
62 : *
63 : * This class specialises the used RT-tree implementation from "rttree.h" and
64 : * extends it by a mutex for avoiding parallel change and traversal of the tree.
65 : */
66 : class SUMORTree : private GUI_RTREE_QUAL, public Boundary {
67 : public:
68 : /// @brief Constructor
69 30100 : SUMORTree() :
70 : GUI_RTREE_QUAL(&GUIGlObject::drawGL),
71 30100 : myLock(true) {
72 30100 : }
73 :
74 : /// @brief Destructor
75 45072 : virtual ~SUMORTree() {
76 : // check if lock is locked before insert objects
77 30048 : if (myLock.locked()) {
78 : // cannot throw exception in destructor
79 0 : WRITE_ERROR("Mutex of SUMORTree is locked during call of the destructor");
80 : }
81 : // show information in gui testing debug gl mode
82 30048 : WRITE_GLDEBUG("Number of objects in SUMORTree during call of the destructor: " + toString(myTreeDebug.size()));
83 45072 : }
84 :
85 : /** @brief Insert entry
86 : * @param a_min Min of bounding rect
87 : * @param a_max Max of bounding rect
88 : * @param a_dataId Positive Id of data. Maybe zero, but negative numbers not allowed.
89 : * @see RTree::Insert
90 : */
91 409525 : virtual void Insert(const float a_min[2], const float a_max[2], GUIGlObject* const & a_dataId) {
92 409525 : FXMutexLock locker(myLock);
93 409525 : GUI_RTREE_QUAL::Insert(a_min, a_max, a_dataId);
94 409525 : }
95 :
96 : /** @brief Remove entry
97 : * @param a_min Min of bounding rect
98 : * @param a_max Max of bounding rect
99 : * @param a_dataId Positive Id of data. Maybe zero, but negative numbers not allowed.
100 : * @see RTree::Remove
101 : */
102 2396 : virtual void Remove(const float a_min[2], const float a_max[2], GUIGlObject* const & a_dataId) {
103 2396 : FXMutexLock locker(myLock);
104 2396 : GUI_RTREE_QUAL::Remove(a_min, a_max, a_dataId);
105 2396 : }
106 :
107 : /** @brief Find all within search rectangle
108 : * @param a_min Min of search bounding rect
109 : * @param a_max Max of search bounding rect
110 : * @param a_searchResult Search result array. Caller should set grow size. Function will reset, not append to array.
111 : * @param a_resultCallback Callback function to return result. Callback should return 'true' to continue searching
112 : * @param a_context User context to pass as parameter to a_resultCallback
113 : * @return Returns the number of entries found
114 : * @see RTree::Search
115 : */
116 1076992 : virtual int Search(const float a_min[2], const float a_max[2], const GUIVisualizationSettings& c) const {
117 1076992 : FXMutexLock locker(myLock);
118 2153980 : return GUI_RTREE_QUAL::Search(a_min, a_max, c);
119 : }
120 :
121 : /** @brief Adds an additional object (detector/shape/trigger) for visualisation
122 : * @param[in] o The object to add
123 : */
124 29012 : void addAdditionalGLObject(GUIGlObject *o, const double exaggeration = 1) {
125 : // check if lock is locked before insert objects
126 29012 : if (myLock.locked()) {
127 0 : throw ProcessError("Mutex of SUMORTree is locked before object insertion");
128 : }
129 : // lock mutex
130 : FXMutexLock locker(myLock);
131 : // obtain boundary of object
132 29012 : Boundary b = o->getCenteringBoundary();
133 : // grow using exaggeration
134 29012 : if (exaggeration > 1) {
135 0 : b.scale(exaggeration);
136 : }
137 : // show information in gui testing debug gl mode
138 29012 : if (MsgHandler::writeDebugGLMessages()) {
139 0 : if (!b.isInitialised()) {
140 0 : throw ProcessError(StringUtils::format("Boundary of GUIGlObject % is not initialised (insertion)", o->getMicrosimID()));
141 0 : } else if ((b.getWidth() == 0) || (b.getHeight() == 0)) {
142 0 : throw ProcessError(StringUtils::format("Boundary of GUIGlObject % has an invalid size (insertion)", o->getMicrosimID()));
143 : } else if (myTreeDebug.count(o) > 0) {
144 0 : throw ProcessError("GUIGlObject was already inserted");
145 : } else {
146 0 : myTreeDebug[o] = b;
147 : // write GL Debug
148 0 : WRITE_GLDEBUG("\tInserted " + o->getFullName() + " into SUMORTree with boundary " + toString(b));
149 : }
150 : }
151 : // insert it in Tree
152 29012 : const float cmin[2] = {(float) b.xmin(), (float) b.ymin()};
153 29012 : const float cmax[2] = {(float) b.xmax(), (float) b.ymax()};
154 29012 : Insert(cmin, cmax, o);
155 : // update tree size
156 29012 : myTreeSize++;
157 58024 : }
158 :
159 : /** @brief Removes an additional object (detector/shape/trigger) from being visualised
160 : * @param[in] o The object to remove
161 : */
162 2396 : void removeAdditionalGLObject(GUIGlObject *o, const double exaggeration = 1) {
163 : // check if lock is locked remove insert objects
164 2396 : if (myLock.locked()) {
165 0 : throw ProcessError("Mutex of SUMORTree is locked before object remove");
166 : }
167 : // lock mutex
168 : FXMutexLock locker(myLock);
169 : // obtain boundary of object
170 2396 : Boundary b = o->getCenteringBoundary();
171 : // grow using exaggeration
172 2396 : if (exaggeration > 1) {
173 0 : b.scale(exaggeration);
174 : }
175 : // show information in gui testing debug gl mode
176 2396 : if (MsgHandler::writeDebugGLMessages()) {
177 0 : if (!b.isInitialised()) {
178 0 : throw ProcessError(StringUtils::format("Boundary of GUIGlObject % is not initialised (deletion)", o->getMicrosimID()));
179 0 : } else if ((b.getWidth() == 0) || (b.getHeight() == 0)) {
180 0 : throw ProcessError(StringUtils::format("Boundary of GUIGlObject % has an invalid size (deletion)", o->getMicrosimID()));
181 : } else if (myTreeDebug.count(o) == 0) {
182 0 : throw ProcessError("GUIGlObject wasn't inserted");
183 0 : } else if (toString(b) != toString(myTreeDebug.at(o))) {
184 : // show information in console before throwing exception
185 0 : std::cout << "Tree: " << toString(myTreeDebug.at(o)) << " original: " << toString(b) << std::endl;
186 0 : throw ProcessError("add boundary of GUIGlObject " + o->getMicrosimID() + " is different of removed boundary (" + toString(b) + " != " + toString(myTreeDebug.at(o)) + ")");
187 : } else {
188 : myTreeDebug.erase(o);
189 0 : WRITE_GLDEBUG("\tRemoved object " + o->getFullName() + " from SUMORTree with boundary " + toString(b));
190 : }
191 : }
192 : // remove it from Tree
193 2396 : const float cmin[2] = {(float) b.xmin(), (float) b.ymin()};
194 2396 : const float cmax[2] = {(float) b.xmax(), (float) b.ymax()};
195 2396 : Remove(cmin, cmax, o);
196 : // update tree size
197 2396 : myTreeSize--;
198 4792 : }
199 :
200 : /// @brief update boundaries
201 : void updateBoundaries(GUIGlObjectType type) {
202 : // declare vector with glObjects to update
203 : std::vector<GUIGlObject*> glObjects;
204 : glObjects.reserve(myTreeSize);
205 : // declare iterator
206 : GUI_RTREE_QUAL::Iterator it;
207 : GetFirst(it);
208 : // iterate over entire tree and keep glObject in glObjects
209 : while (!IsNull(it)) {
210 : const auto glType = (*it)->getType();
211 : if ((glType == type) ||
212 : ((glType > GLO_ADDITIONALELEMENT) && (glType < GLO_SHAPE)) || // Additionals
213 : ((glType >= GLO_TAZ) && (glType < GLO_LOCKICON))) { // TAZ Elements
214 : glObjects.push_back(*it);
215 : }
216 : GetNext(it);
217 : }
218 : // remove and insert all elements again with the new boundary
219 : for (const auto &glObject : glObjects) {
220 : removeAdditionalGLObject(glObject);
221 : removeObjectFromTreeDebug(glObject);
222 : addAdditionalGLObject(glObject);
223 : }
224 : }
225 :
226 : protected:
227 : /// @brief A mutex avoiding parallel change and traversal of the tree
228 : mutable FXMutex myLock;
229 :
230 : /// @brief number of inserted elements
231 : int myTreeSize = 0;
232 :
233 : private:
234 : /**@brief Map only used for check that SUMORTree works as expected, only is used if option "gui-testing-debug-gl" is enabled.
235 : * @note Warning: DO NOT USE in release mode and use it in debug mode carefully, due it produces a slowdown.
236 : */
237 : std::map<GUIGlObject*, Boundary> myTreeDebug;
238 :
239 : /// @brief remove object from TreeDebug
240 : bool removeObjectFromTreeDebug(const GUIGlObject* obj) {
241 : for (auto it = myTreeDebug.begin(); it != myTreeDebug.end(); it++) {
242 : if (it->first == obj) {
243 : myTreeDebug.erase(it);
244 : return true;
245 : }
246 : }
247 : return false;
248 : }
249 : };
|
