GteRectangleManager.h
Go to the documentation of this file.
1 // David Eberly, Geometric Tools, Redmond WA 98052
2 // Copyright (c) 1998-2017
3 // Distributed under the Boost Software License, Version 1.0.
4 // http://www.boost.org/LICENSE_1_0.txt
5 // http://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
6 // File Version: 3.0.0 (2016/06/19)
7 
8 #pragma once
9 
11 #include <Mathematics/GteEdgeKey.h>
12 #include <algorithm>
13 #include <set>
14 #include <vector>
15 
16 namespace gte
17 {
18 
19 template <typename Real>
21 {
22 public:
23  // Construction.
24  RectangleManager(std::vector<AlignedBox2<Real>>& rectangles);
25 
26  // No default construction, copy construction, or assignment are allowed.
27  RectangleManager() = delete;
28  RectangleManager(RectangleManager const&) = delete;
30 
31  // This function is called by the constructor and does the sort-and-sweep
32  // to initialize the update system. However, if you add or remove items
33  // from the array of rectangles after the constructor call, you will need
34  // to call this function once before you start the multiple calls of the
35  // update function.
36  void Initialize();
37 
38  // After the system is initialized, you can move the rectangles using this
39  // function. It is not enough to modify the input array of rectangles
40  // since the endpoint values stored internally by this class must also
41  // change. You can also retrieve the current rectangles information.
42  void SetRectangle(int i, AlignedBox2<Real> const& rectangle);
43  void GetRectangle(int i, AlignedBox2<Real>& rectangle) const;
44 
45  // When you are finished moving rectangles, call this function to
46  // determine the overlapping rectangles. An incremental update is applied
47  // to determine the new set of overlapping rectangles.
48  void Update();
49 
50  // If (i,j) is in the overlap set, then rectangle i and rectangle j are
51  // overlapping. The indices are those for the the input array. The
52  // set elements (i,j) are stored so that i < j.
53  std::set<EdgeKey<false>> const& GetOverlap() const;
54 
55 private:
56  class Endpoint
57  {
58  public:
59  Real value; // endpoint value
60  int type; // '0' if interval min, '1' if interval max.
61  int index; // index of interval containing this endpoint
62 
63  // Support for sorting of endpoints.
64  bool operator<(Endpoint const& endpoint) const;
65  };
66 
67  void InsertionSort (std::vector<Endpoint>& endpoint, std::vector<int>& lookup);
68 
69  std::vector<AlignedBox2<Real>>& mRectangles;
70  std::vector<Endpoint> mXEndpoints, mYEndpoints;
71  std::set<EdgeKey<false>> mOverlap;
72 
73  // The intervals are indexed 0 <= i < n. The endpoint array has 2*n
74  // entries. The original 2*n interval values are ordered as b[0], e[0],
75  // b[1], e[1], ..., b[n-1], e[n-1]. When the endpoint array is sorted,
76  // the mapping between interval values and endpoints is lost. In order
77  // to modify interval values that are stored in the endpoint array, we
78  // need to maintain the mapping. This is done by the following lookup
79  // table of 2*n entries. The value mLookup[2*i] is the index of b[i]
80  // in the endpoint array. The value mLookup[2*i+1] is the index of
81  // e[i] in the endpoint array.
82  std::vector<int> mXLookup, mYLookup;
83 };
84 
85 template <typename Real>
87  :
88  mRectangles(rectangles)
89 {
90  Initialize();
91 }
92 
93 template <typename Real>
95 {
96  // Get the rectangle endpoints.
97  int intrSize = static_cast<int>(mRectangles.size()), endpSize = 2 * intrSize;
98  mXEndpoints.resize(endpSize);
99  mYEndpoints.resize(endpSize);
100  for (int i = 0, j = 0; i < intrSize; ++i)
101  {
102  mXEndpoints[j].type = 0;
103  mXEndpoints[j].value = mRectangles[i].min[0];
104  mXEndpoints[j].index = i;
105  mYEndpoints[j].type = 0;
106  mYEndpoints[j].value = mRectangles[i].min[1];
107  mYEndpoints[j].index = i;
108  ++j;
109 
110  mXEndpoints[j].type = 1;
111  mXEndpoints[j].value = mRectangles[i].max[0];
112  mXEndpoints[j].index = i;
113  mYEndpoints[j].type = 1;
114  mYEndpoints[j].value = mRectangles[i].max[1];
115  mYEndpoints[j].index = i;
116  ++j;
117  }
118 
119  // Sort the rectangle endpoints.
120  std::sort(mXEndpoints.begin(), mXEndpoints.end());
121  std::sort(mYEndpoints.begin(), mYEndpoints.end());
122 
123  // Create the interval-to-endpoint lookup tables.
124  mXLookup.resize(endpSize);
125  mYLookup.resize(endpSize);
126  for (int j = 0; j < endpSize; ++j)
127  {
128  mXLookup[2 * mXEndpoints[j].index + mXEndpoints[j].type] = j;
129  mYLookup[2 * mYEndpoints[j].index + mYEndpoints[j].type] = j;
130  }
131 
132  // Active set of rectangles (stored by index in array).
133  std::set<int> active;
134 
135  // Set of overlapping rectangles (stored by pairs of indices in array).
136  mOverlap.clear();
137 
138  // Sweep through the endpoints to determine overlapping x-intervals.
139  for (int i = 0; i < endpSize; ++i)
140  {
141  Endpoint& endpoint = mXEndpoints[i];
142  int index = endpoint.index;
143  if (endpoint.type == 0) // an interval 'begin' value
144  {
145  // In the 1D problem, the current interval overlaps with all the
146  // active intervals. In 2D we also need to check for y-overlap.
147  for (auto activeIndex : active)
148  {
149  // Rectangles activeIndex and index overlap in the
150  // x-dimension. Test for overlap in the y-dimension.
151  AlignedBox2<Real> const& r0 = mRectangles[activeIndex];
152  AlignedBox2<Real> const& r1 = mRectangles[index];
153  if (r0.max[1] >= r1.min[1] && r0.min[1] <= r1.max[1])
154  {
155  if (activeIndex < index)
156  {
157  mOverlap.insert(EdgeKey<false>(activeIndex, index));
158  }
159  else
160  {
161  mOverlap.insert(EdgeKey<false>(index, activeIndex));
162  }
163  }
164  }
165  active.insert(index);
166  }
167  else // an interval 'end' value
168  {
169  active.erase(index);
170  }
171  }
172 }
173 
174 template <typename Real>
176 {
177  mRectangles[i] = rectangle;
178  mXEndpoints[mXLookup[2 * i]].value = rectangle.min[0];
179  mXEndpoints[mXLookup[2 * i + 1]].value = rectangle.max[0];
180  mYEndpoints[mYLookup[2 * i]].value = rectangle.min[1];
181  mYEndpoints[mYLookup[2 * i + 1]].value = rectangle.max[1];
182 }
183 
184 template <typename Real>
186 {
187  rectangle = mRectangles[i];
188 }
189 
190 template <typename Real>
191 void RectangleManager<Real>::InsertionSort(std::vector<Endpoint>& endpoint, std::vector<int>& lookup)
192 {
193  // Apply an insertion sort. Under the assumption that the rectangles
194  // have not changed much since the last call, the endpoints are nearly
195  // sorted. The insertion sort should be very fast in this case.
196 
198  int endpSize = static_cast<int>(endpoint.size());
199  for (int j = 1; j < endpSize; ++j)
200  {
201  Endpoint key = endpoint[j];
202  int i = j - 1;
203  while (i >= 0 && key < endpoint[i])
204  {
205  Endpoint e0 = endpoint[i];
206  Endpoint e1 = endpoint[i + 1];
207 
208  // Update the overlap status.
209  if (e0.type == 0)
210  {
211  if (e1.type == 1)
212  {
213  // The 'b' of interval E0.index was smaller than the 'e'
214  // of interval E1.index, and the intervals *might have
215  // been* overlapping. Now 'b' and 'e' are swapped, and
216  // the intervals cannot overlap. Remove the pair from
217  // the overlap set. The removal operation needs to find
218  // the pair and erase it if it exists. Finding the pair
219  // is the expensive part of the operation, so there is no
220  // real time savings in testing for existence first, then
221  // deleting if it does.
222  mOverlap.erase(EdgeKey<false>(e0.index, e1.index));
223  }
224  }
225  else
226  {
227  if (e1.type == 0)
228  {
229  // The 'b' of interval E1.index was larger than the 'e'
230  // of interval E0.index, and the intervals were not
231  // overlapping. Now 'b' and 'e' are swapped, and the
232  // intervals *might be* overlapping. Determine if they
233  // are overlapping and then insert.
234  if (query(mRectangles[e0.index], mRectangles[e1.index]).intersect)
235  {
236  mOverlap.insert(EdgeKey<false>(e0.index, e1.index));
237  }
238  }
239  }
240 
241  // Reorder the items to maintain the sorted list.
242  endpoint[i] = e1;
243  endpoint[i + 1] = e0;
244  lookup[2 * e1.index + e1.type] = i;
245  lookup[2 * e0.index + e0.type] = i + 1;
246  --i;
247  }
248  endpoint[i + 1] = key;
249  lookup[2 * key.index + key.type] = i + 1;
250  }
251 }
252 
253 template <typename Real>
255 {
258 }
259 
260 template <typename Real>
261 std::set<EdgeKey<false>> const& RectangleManager<Real>::GetOverlap() const
262 {
263  return mOverlap;
264 }
265 
266 template <typename Real>
268 {
269  if (value < endpoint.value)
270  {
271  return true;
272  }
273  if (value > endpoint.value)
274  {
275  return false;
276  }
277  return type < endpoint.type;
278 }
279 
280 }
std::vector< Endpoint > mYEndpoints
Vector< N, Real > max
Definition: GteAlignedBox.h:40
Vector< N, Real > min
Definition: GteAlignedBox.h:40
std::vector< Endpoint > mXEndpoints
GLsizei const GLfloat * value
Definition: glcorearb.h:819
std::vector< int > mYLookup
void SetRectangle(int i, AlignedBox2< Real > const &rectangle)
void GetRectangle(int i, AlignedBox2< Real > &rectangle) const
bool operator<(Endpoint const &endpoint) const
std::vector< int > mXLookup
void InsertionSort(std::vector< Endpoint > &endpoint, std::vector< int > &lookup)
std::vector< AlignedBox2< Real > > & mRectangles
std::set< EdgeKey< false > > mOverlap
std::set< EdgeKey< false > > const & GetOverlap() const
GLuint index
Definition: glcorearb.h:781
RectangleManager & operator=(RectangleManager const &)=delete
GLenum query
Definition: glext.h:2716
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:103


geometric_tools_engine
Author(s): Yijiang Huang
autogenerated on Thu Jul 18 2019 04:00:01