Parallel Plane Sweep  0.1
Shared memory multithreaded version of the plane sweep algorithm
vectorAlEq.h
Go to the documentation of this file.
1 /*
2  * The MIT License (MIT)
3  * Copyright (c) <2016> <Mark McKenney>
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
6  *
7  * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
10  * */
11 
12 
13 
14 
15 
16 #include "halfsegment.h"
17 #include <cstdlib>
18 #include <iomanip>
19 // event queue contains a vector and is sorted in hseg order
20 
21 #ifndef VECTORALEQ_H
22 #define VECTORALEQ_H
23 
43 {
44  private:
46  vector<halfsegment> eq;
47 
48  public:
55  void insert( const halfsegment & h1 ){
56  if( eq.empty() || eq[eq.size()-1] < h1 ) {
57  eq.push_back( h1 );
58  return;
59  }
60  else {
61  for( vector<halfsegment>::iterator it = eq.begin(); ;it++ ){
62  if( h1 < *it ){
63  eq.insert( it, h1 );
64  break;
65  }
66  }
67 
68  }
69  }
77  bool peek( halfsegment & h1 ){
78  if( eq.empty() ) {
79  return false;
80  }
81  h1 = eq[0];
82  return true;
83  }
89  bool pop( ){
90  if( eq.empty() ) {
91  return false;
92  }
93  eq.erase( eq.begin() );
94  return true;
95  }
99  int size(){
100  return eq.size();
101  }
102 
106  void print(){
107  cerr << "eq:-----"<<endl;
108  for( int i = 0; i < eq.size(); i++ )
109  cerr << eq[i] << endl;
110  cerr << "^^^^^^"<< endl;
111  }
112 
113 
114 };
115 
131 {
132  private:
134  vector<halfsegment> al;
135  public:
137  double xVal;
138 
139  // always assume h1 is the new halfsegment (being entered into the list)
140  // returns true if h1 < h2, false otherwise
152  bool alHsegLT( const halfsegment &h1, const halfsegment &h2 )
153  {
154  // if equal, indicate
155  if( h1 == h2 )
156  return false;
157  // if colinear, then 'first' is greater (due to hseg ordering)
158  // the only time we will have overlapping colinear is when inserting left hsegs
159  // so this shouldn't ever come up when removing based on right segs
160  if( h1.colinear( h2 ) )
161  return false;
162 
163  double h1Y = h1.getYvalAtX( xVal );
164  double h2Y = h2.getYvalAtX( xVal );
165  // at this point, we simply construct hsegs using the sweep line intersect and xval as the dominating point
166  // cerr << "xval, h1, h2 :" << xVal << ", " << h1 << ", " << h2 << endl;
167  halfsegment newH1;
168  halfsegment newH2;
169  newH1.dx = newH2.dx = xVal;
170  newH1.dy = h1Y;
171  newH2.dy = h2Y;
172  if( newH1.dx == h1.sx && newH1.dy == h1.sy ) {
173  newH1.sx = h1.dx;
174  newH1.sy = h1.dy;
175  }
176  else {
177  newH1.sx = h1.sx;
178  newH1.sy = h1.sy;
179  }
180  if( newH2.dx == h2.sx && newH2.dy == h2.sy ) {
181  newH2.sx = h2.sx;
182  newH2.sy = h2.dy;
183  }
184  else {
185  newH2.sx = h2.sx;
186  newH2.sy = h2.sy;
187  }
188  //cerr << "newh1, newh2: " << newH1 << ", " << newH2 << (newH1 < newH2)<<endl;
189  // if Y vals are different
190  if( h1Y < h2Y ) return true;
191  else if( h1Y > h2Y ) return false;
192  // otherwise, the dom point is the same
193  // now we just use the halfsgment < operator
194  // for the active list, we want the seg that is above the other one.
195  // special case: when they are both right hsegs, they always share a dom point. reverse <
196  if( !newH1.isLeft() && !newH2.isLeft( ) ) {
197  if( newH1 < newH2 ) return false;
198  return true;
199  }
200  else if( newH1.isLeft() && newH2.isLeft( ) ) {
201  if( newH1 < newH2 ) return true;
202  return false;
203  }
204  else {
205 
206  // we have a left one and a right one. the right hseg is less
207  if( !newH1.isLeft() ) return true;
208  return false;
209  // we should never get 1 left and 1 right hseg
210 
211  cerr<< "AL comp. got a left and right" << endl;
212  cerr<< "xval: " << std::setprecision(100)<< xVal << endl;
213  cerr << std::setprecision(100) << h1 << endl << h2 << endl << newH1 << endl << newH2 << endl;
214  exit( -1 );
215  }
216  return false;
217  }
218 
224  inline bool alHsegEQ( const halfsegment &h1, const halfsegment &h2 )
225  {
226  return (h1 == h2);
227  }
244  void insert( const halfsegment & h1, bool & duplicate, halfsegment & theDup, int & segIndex )
245  {
246  duplicate = false;
247  if( al.empty() || !alHsegLT( h1, al[al.size()-1]) ) {
248  al.push_back( h1 );
249  theDup = h1;
250  segIndex = al.size()-1;
251  return;
252  }
253  else {
254  int i = 0;
255  for( vector<halfsegment>::iterator it = al.begin(); ; it++ ){
256  if( *it == h1 ){
257  duplicate = true;
258  theDup = *it;
259  segIndex = i;
260  return;
261  }
262  else if( alHsegLT( h1, *it ) ){
263  al.insert( it, h1 );
264  theDup = h1;
265  segIndex = i;
266  return;
267  }
268  i++;
269  }
270  }
271  }
272 
280  bool exists( const halfsegment& h1, halfsegment & theCopy, int & index ){
281  index = find (h1 );
282  if( index != -1 ){
283  theCopy = al[index];
284  return true;
285  }
286  return false;
287  }
288 
294  int find( const halfsegment& h1 ){
295  for( int i= 0; i < al.size(); i++ ){
296  if( h1 == al[i] )
297  return i;
298  }
299  return -1;
300  }
301 
309  void replace( const halfsegment &h1, const halfsegment & newH1 ){
310  int index = find( h1 );
311  if( index <0 || index >= al.size() ){
312  cerr << "replace: did not find halfsegment: " << h1 << endl;
313  exit( -1 );
314  }
315  al[index] = newH1;
316  }
328  void replace( const halfsegment &h1, const halfsegment & newH1, const int index ){
329  if( index <0 || index >= al.size() ){
330  cerr << "replace: did not find halfsegment: " << h1 << endl;
331  exit( -1 );
332  }
333  if( al[index] == h1 ){
334  al[index] = newH1;
335  return;
336  }
337  else {
338  cerr << "trying to replace a seg by index that does not match" <<endl;
339  exit( -1 );
340  }
341  }
342 
350  bool getAbove( const halfsegment& h1, halfsegment &theAbove, const int index ){
351  // cerr << "foundabove index = " << index << endl;
352  if( index < 0 || index > al.size() ){
353  cerr << "invalid size getAbove AL"<<endl;
354  exit(-1);
355  }
356  if( index >= al.size()-1 ){
357  return false;
358  }
359  theAbove = al[index+1];
360  return true;
361  }
362 
371  bool getAbove( const halfsegment& h1, halfsegment &theAbove ){
372  int index = this->find( h1 );
373  // cerr << "foundabove index = " << index << endl;
374  if( index < 0 || index > al.size() ){
375  cerr << "invalid size getAbove AL"<<endl;
376  exit(-1);
377  }
378  if( index >= al.size()-1 ){
379  return false;
380  }
381  theAbove = al[index+1];
382  return true;
383  }
391  bool getBelow(const halfsegment& h1, halfsegment &theBelow, const int index ){
392  if( index < 0 || index >= al.size() ){
393  cerr << "invalid size getBelow AL"<<endl;
394  exit(-1);
395  }
396  if( index <= 0 ){
397  return false;
398  }
399  theBelow = al[index-1];
400  return true;
401  }
410  bool getBelow(const halfsegment& h1, halfsegment &theBelow ){
411  int index = this->find( h1 );
412  if( index < 0 || index >= al.size() ){
413  cerr << "invalid size getBelow AL"<<endl;
414  exit(-1);
415  }
416  if( index <= 0 ){
417  return false;
418  }
419  theBelow = al[index-1];
420  return true;
421  }
422 
423  void erase( const halfsegment & h1, const int index )
424  {
425  // cerr << "erase1"<<endl;
426  if( index < 0 || index >= al.size() )
427  return;
428 
429  vector<halfsegment>::iterator it = al.begin() + index;
430  if( *it == h1 ){
431  al.erase( it );
432  // cerr << "erase2"<<endl;
433  return;
434  }
435  else {
436  cerr << "trying to erase a seg by index that does not match" <<endl;
437  exit( -1 );
438  }
439  }
440 
445  void erase( const halfsegment & h1 )
446  {
447  // cerr << "erase1"<<endl;
448  for(vector<halfsegment>::iterator it = al.begin();it != al.end() ; it++ ){
449  if( *it == h1 ){
450  al.erase( it );
451  // cerr << "erase2"<<endl;
452  return;
453  }
454  }
455  }
456 
460  void print(){
461  cerr << "al:-----"<<endl;
462  for( int i = 0; i < al.size(); i++ )
463  cerr << al[i] << endl;
464  cerr << "^^^^^^" << endl;
465  }
466 };
467 #endif
468 
bool colinear(const halfsegment &rhs) const
A vector-based implementation of a plane sweep event queue.
Definition: vectorAlEq.h:42
holds a single halfsegment, along with labeling information and information indicating if the opposin...
Definition: parPlaneSweep.h:76
bool alHsegLT(const halfsegment &h1, const halfsegment &h2)
Definition: vectorAlEq.h:152
double getYvalAtX(const double x) const
bool pop()
Definition: vectorAlEq.h:89
bool getBelow(const halfsegment &h1, halfsegment &theBelow, const int index)
Definition: vectorAlEq.h:391
bool alHsegEQ(const halfsegment &h1, const halfsegment &h2)
Definition: vectorAlEq.h:224
bool exists(const halfsegment &h1, halfsegment &theCopy, int &index)
Definition: vectorAlEq.h:280
void print()
Definition: vectorAlEq.h:460
bool isLeft() const
double dx
dominating and submissive points
Definition: parPlaneSweep.h:79
int size()
Definition: vectorAlEq.h:99
bool getAbove(const halfsegment &h1, halfsegment &theAbove)
Definition: vectorAlEq.h:371
A vector-based implementation of a plane sweep active list.
Definition: vectorAlEq.h:130
void replace(const halfsegment &h1, const halfsegment &newH1, const int index)
Definition: vectorAlEq.h:328
void print()
Definition: vectorAlEq.h:106
void replace(const halfsegment &h1, const halfsegment &newH1)
Definition: vectorAlEq.h:309
void insert(const halfsegment &h1, bool &duplicate, halfsegment &theDup, int &segIndex)
Definition: vectorAlEq.h:244
bool getBelow(const halfsegment &h1, halfsegment &theBelow)
Definition: vectorAlEq.h:410
bool getAbove(const halfsegment &h1, halfsegment &theAbove, const int index)
Definition: vectorAlEq.h:350
void insert(const halfsegment &h1)
Definition: vectorAlEq.h:55
double xVal
The current position of the sweep line.
Definition: vectorAlEq.h:137
void erase(const halfsegment &h1)
Definition: vectorAlEq.h:445
int find(const halfsegment &h1)
Definition: vectorAlEq.h:294
void erase(const halfsegment &h1, const int index)
Definition: vectorAlEq.h:423
bool peek(halfsegment &h1)
Definition: vectorAlEq.h:77