Parallel Plane Sweep  0.1
Shared memory multithreaded version of the plane sweep algorithm
main.cpp
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 #include <iostream>
13 #include <vector>
14 #include <string>
15 #include <sstream>
16 #include <cstdlib>
17 #include <algorithm>
18 #include "parPlaneSweep.h"
19 #include "d2hex.h"
20 #include <fstream>
21 
22 
45 using namespace std;
46 
53 void tokenizeString(const std::string& str,
54  std::vector<string>& tokens,
55  const string& delimiters );
56 
75 int main( int argc, char * argv[] )
76 {
77  // read the argument regions
78  std::string inputFileName1, inputFileName2;
79  vector< halfsegment >v1, v2, result;
80  int minStrips, maxStrips;
81  if( argc != 5 )
82  {
83  std::cerr << "usage: exe [input file name 1] [input file name 2] [min strips][max strips]" << std::endl;
84  exit( -1 );
85  }
86  {
87  std::stringstream ss1;
88  ss1 << argv[1];
89  ss1 >> inputFileName1;
90  }
91  {
92  std::stringstream ss1;
93  ss1 << argv[2];
94  ss1 >> inputFileName2;
95  }
96  {
97  std::stringstream ss1;
98  ss1 << argv[3];
99  ss1 >> minStrips;
100  }
101  {
102  std::stringstream ss1;
103  ss1 << argv[4];
104  ss1 >> maxStrips;
105  }
106 
107  ifstream inFileStrm1;
108  inFileStrm1.open( argv[1] );
109  if( ! inFileStrm1 )
110  {
111  cerr << "Error: could not open file: " << argv[1] << endl;
112  exit( -1 );
113  }
114  ifstream inFileStrm2;
115  inFileStrm2.open( argv[2] );
116  if( ! inFileStrm2 )
117  {
118  cerr << "Error: could not open file: " << argv[2] << endl;
119  exit( -1 );
120  }
121 
122  cerr << "Reading files: " << argv[1] << ", " <<argv[2] << endl;
123  vector<string> splitLine;
124  string line(" ");
125  double x, y;
126  int la, lb;
127  int i = 0;
128  while(inFileStrm1.good() )
129  {
130  getline(inFileStrm1, line);
131  if( inFileStrm1.good() )
132  {
133  if( line.size() == 0 || line[0] == '#' )
134  continue;
135  splitLine.clear();
136  string delim(" \t" );
137  tokenizeString( line, splitLine, delim );
138  v1.push_back( halfsegment() );
139  v1[i].dx = doubleHexConverter::hex2d(splitLine[0]);
140  v1[i].dy = doubleHexConverter::hex2d(splitLine[1]);
141  v1[i].sx = doubleHexConverter::hex2d(splitLine[2]);
142  v1[i].sy = doubleHexConverter::hex2d(splitLine[3]);
143  stringstream ss1( splitLine[4] );
144  ss1 >> la;
145  stringstream ss2( splitLine[5] );
146  ss2 >> lb;
147  v1[i].la = la;
148  v1[i].ola = la;
149  v1[i].lb = lb;
150  v1[i].olb = lb;
151  v1[i].regionID = 2;
152  i++;
153  v1.push_back( v1[i-1].getBrother() );
154  i++;
155  }
156  }
157  cerr <<"file 1 finished reading"<<endl;
158  i = 0;
159  while(inFileStrm2.good() )
160  {
161  getline(inFileStrm2, line);
162  if( inFileStrm2.good() )
163  {
164  if( line.size() == 0 || line[0] == '#' )
165  continue;
166  splitLine.clear();
167  string delim(" \t" );
168  tokenizeString( line, splitLine, delim );
169  v2.push_back( halfsegment() );
170  v2[i].dx = doubleHexConverter::hex2d(splitLine[0]);
171  v2[i].dy = doubleHexConverter::hex2d(splitLine[1]);
172  v2[i].sx = doubleHexConverter::hex2d(splitLine[2]);
173  v2[i].sy = doubleHexConverter::hex2d(splitLine[3]);
174  stringstream ss1( splitLine[4] );
175  ss1 >> la;
176  stringstream ss2( splitLine[5] );
177  ss2 >> lb;
178  v2[i].la = la;
179  v2[i].ola = la;
180  v2[i].lb = lb;
181  v2[i].olb = lb;
182  v2[i].regionID = 3;
183  i++;
184  v2.push_back( v2[i-1].getBrother() );
185  i++;
186  }
187  }
188  cerr <<"file 2 finished reading"<<endl;
189 
190 
191  std::sort( v1.begin(), v1.end() );
192  std::sort( v2.begin(), v2.end() );
193  if( minStrips < 1 ) {
194  minStrips = 1;
195  }
196  for( int i = minStrips; i <= maxStrips; i= (i==1)? 2: i*2 ){
197  cout << "*** num strips: " << i << endl;
198  if( i == 1 ){
199 
200  overlayPlaneSweep( &(v1[0]), v1.size(), &(v2[0]), v2.size(), result );
201  }
202  else {
203 
204  parallelOverlay( v1, v2, result, i);
205  }
206  cout << "num segs: " << result.size()/2<<endl;
207  }
208 
209 }
210 
211 
212 void tokenizeString(const std::string& str, std::vector<string>& tokens, const string& delimiters )
213 {
214  std::string::size_type lastPos = str.find_first_not_of(delimiters, 0); // Skip delimiters at beginning.
215  std::string::size_type pos = str.find_first_of(delimiters, lastPos); // Find first "non-delimiter".
216 
217  while (std::string::npos != pos || std::string::npos != lastPos)
218  {
219  tokens.push_back(str.substr(lastPos, pos - lastPos)); // Found a token, add it to the vector.
220  lastPos = str.find_first_not_of(delimiters, pos); // Skip delimiters. Note the "not_of"
221  pos = str.find_first_of(delimiters, lastPos); // Find next "non-delimiter"
222  }
223 }
224 
holds a single halfsegment, along with labeling information and information indicating if the opposin...
Definition: parPlaneSweep.h:76
void parallelOverlay(vector< halfsegment > &r1, vector< halfsegment > &r2, vector< halfsegment > &result, int numStrips, int numWorkerThreads)
void tokenizeString(const std::string &str, std::vector< string > &tokens, const string &delimiters)
Definition: main.cpp:212
void overlayPlaneSweep(const halfsegment r1[], int r1Size, const halfsegment r2[], int r2Size, vector< halfsegment > &result)
static double hex2d(const string &hexer)
Definition: d2hex.h:42
int main(int argc, char *argv[])
Definition: main.cpp:75