Parallel Plane Sweep
0.1
Shared memory multithreaded version of the plane sweep algorithm
|
#include <iomanip>
#include <omp.h>
#include "parPlaneSweep.h"
#include "vectorAlEq.h"
#include <limits>
#include <algorithm>
Go to the source code of this file.
Functions | |
int | binarySearchExists (vector< halfsegment > ®ion, double x, int hi=-1, int lo=0) |
int | binarySearchSmallestGreater (vector< halfsegment > ®ion, double x, int hi=-1, int lo=-1) |
bool | binarySearchHalfsegment (vector< halfsegment > ®ion, const halfsegment &h, int &mid, int hi=-1, int lo=0) |
void | findIsoBoundaries (vector< halfsegment > &r1, vector< halfsegment > &r2, vector< double > &isoBounds) |
void | createStrips (vector< halfsegment > ®ion, vector< double > &isoBounds, vector< halfsegment > &rStrips, vector< int > &stripStopIndex) |
void | partialOverlay (const vector< halfsegment > &r1Strips, const vector< halfsegment > &r2Strips, vector< halfsegment > &result, vector< int > &r1StripStopIndex, vector< int > &r2StripStopIndex, const int stripID) |
bool | findIntersectionPoint (const halfsegment &h1, const halfsegment &h2, double &X, double &Y, bool &colinear) |
bool | breakHsegs (const halfsegment &alSeg, halfsegment &origCurr, vector< halfsegment > &brokenSegs, bool &colinear, const bool includeCurrSegInBrokenSegs) |
void | createFinalOverlay (vector< halfsegment > &finalResult, vector< vector< halfsegment > > &resultStrips, const vector< double > &isoBounds) |
void | insertBrokenSegsToActiveListAndDiscoveredQueue (const vector< halfsegment > &brokenSegs, vector< halfsegment > &result, eventQueue &discoveredSegs, activeListVec &activeList, const double eventX, const double eventY) |
void | parallelOverlay (vector< halfsegment > &r1, vector< halfsegment > &r2, vector< halfsegment > &result, int numStrips, int numWorkerThreads) |
void | overlayPlaneSweep (const halfsegment r1[], int r1Size, const halfsegment r2[], int r2Size, vector< halfsegment > &result) |
bool | hsegIDSort (const halfsegment &h1, const halfsegment &h2) |
int binarySearchExists | ( | vector< halfsegment > & | region, |
double | x, | ||
int | hi = -1 , |
||
int | lo = 0 |
||
) |
A binary search function
Definition at line 23 of file parPlaneSweep.cpp.
bool binarySearchHalfsegment | ( | vector< halfsegment > & | region, |
const halfsegment & | h, | ||
int & | mid, | ||
int | hi = -1 , |
||
int | lo = 0 |
||
) |
A binary search function
Definition at line 58 of file parPlaneSweep.cpp.
int binarySearchSmallestGreater | ( | vector< halfsegment > & | region, |
double | x, | ||
int | hi = -1 , |
||
int | lo = -1 |
||
) |
A binary search function
Definition at line 39 of file parPlaneSweep.cpp.
bool breakHsegs | ( | const halfsegment & | alSeg, |
halfsegment & | origCurr, | ||
vector< halfsegment > & | brokenSegs, | ||
bool & | colinear, | ||
const bool | includeCurrSegInBrokenSegs | ||
) |
break halfsegments if they intersect. returns a vector of the resulting halfsegments, since various numbers of halfsegments are returned based on the confguration of the input halfsegments.
Definition at line 514 of file parPlaneSweep.cpp.
void createFinalOverlay | ( | vector< halfsegment > & | finalResult, |
vector< vector< halfsegment > > & | resultStrips, | ||
const vector< double > & | isoBounds | ||
) |
Remove breaks in halfsegments that are only introduced to create strips.
This is not strictly necessary, but removes breaks in halfsegemnts that were introduced solely for the purpose of createing strips
Definition at line 848 of file parPlaneSweep.cpp.
void createStrips | ( | vector< halfsegment > & | region, |
vector< double > & | isoBounds, | ||
vector< halfsegment > & | rStrips, | ||
vector< int > & | stripStopIndex | ||
) |
Break an input region up into strips. Strip boundaries are isoBounds
region | the region to split into strips |
isoBounds | the strip boundaries |
rStrips | [out] the region broken into strips. Each halfsegment will have a strip ID indicating the strip to which it belongs. stripIDs start at 0 and increment. |
stripStopIndex | [out] halfsegments in rStrips are sorted by strip ID then halfsegment ordering. This vector marks the positions in the rStrips array where the last halfsegment in each strip is located. |
Definition at line 686 of file parPlaneSweep.cpp.
bool findIntersectionPoint | ( | const halfsegment & | h1, |
const halfsegment & | h2, | ||
double & | X, | ||
double & | Y, | ||
bool & | colinear | ||
) |
Find the intersection point between two halfsegments. Also indicate if they are colinear.
Definition at line 632 of file parPlaneSweep.cpp.
void findIsoBoundaries | ( | vector< halfsegment > & | r1, |
vector< halfsegment > & | r2, | ||
vector< double > & | isoBounds | ||
) |
Find the isolation boundaries. Isolation boundaries are vertical lines that do not intersect any halfsegment end points in r1 or r2 that form the strip boundaries
r1 | halfsegments defining one input region |
r2 | halfsegments definining the second input region |
isoBounds | [in/out] the x values indicating vertical lines that form strip boundaries. |
Definition at line 765 of file parPlaneSweep.cpp.
bool hsegIDSort | ( | const halfsegment & | h1, |
const halfsegment & | h2 | ||
) |
Definition at line 681 of file parPlaneSweep.cpp.
void insertBrokenSegsToActiveListAndDiscoveredQueue | ( | const vector< halfsegment > & | brokenSegs, |
vector< halfsegment > & | result, | ||
eventQueue & | discoveredSegs, | ||
activeListVec & | activeList, | ||
const double | eventX, | ||
const double | eventY | ||
) |
Once two intersecting halfsegments have been broken up based on their intersection such that the result halfsegments only intersect at end points, we need to put those halfsegments in the event queue, and possible the active list. This function does that.
eventX and eventY indicate the current event point (where the sweep line is).
Definition at line 480 of file parPlaneSweep.cpp.
void overlayPlaneSweep | ( | const halfsegment | r1[], |
int | r1Size, | ||
const halfsegment | r2[], | ||
int | r2Size, | ||
vector< halfsegment > & | result | ||
) |
See the prototype in parPlaneSweep.h
Definition at line 258 of file parPlaneSweep.cpp.
void parallelOverlay | ( | vector< halfsegment > & | r1, |
vector< halfsegment > & | r2, | ||
vector< halfsegment > & | result, | ||
int | numStrips, | ||
int | numWorkerThreads | ||
) |
See the prototype in parPlaneSweep.h
Definition at line 157 of file parPlaneSweep.cpp.
void partialOverlay | ( | const vector< halfsegment > & | r1Strips, |
const vector< halfsegment > & | r2Strips, | ||
vector< halfsegment > & | result, | ||
vector< int > & | r1StripStopIndex, | ||
vector< int > & | r2StripStopIndex, | ||
const int | stripID | ||
) |
This function calls the individual overlay functions. It simply sets up calls to overlayPlaneSweep().
It is expected that the overlayPlaneSweep() function splits up the input into strips, and then passes those strips to this function.
The start and stop indexes indcate where each strip starts in the r1Strips and r2Strips vectors.
See the prototype in parPlaneSweep.h
Definition at line 233 of file parPlaneSweep.cpp.