Parallel Plane Sweep  0.1
Shared memory multithreaded version of the plane sweep algorithm
parPlaneSweep.cpp File Reference
#include "parPlaneSweep.h"
#include <iomanip>

Go to the source code of this file.


int avlHsegCompare (const void *first, const void *second, void *param)
int avlHsegActiveListCompare (const void *first, const void *second, void *param)
int binarySearchExists (vector< halfsegment > &region, double x, int hi=-1, int lo=0)
int binarySearchSmallestGreater (vector< halfsegment > &region, double x, int hi=-1, int lo=-1)
bool binarySearchHalfsegment (vector< halfsegment > &region, 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 > &region, 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, avl_table *discoveredSegs, avl_table *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)

Function Documentation

int avlHsegActiveListCompare ( const void *  first,
const void *  second,
void *  param 

Comparison function for the AVL tree to compare halfsegments in the ACTIVE LIST.

Orders halfsegemnts vertically along a line the the X value of the current sweep line.

paramis used to the get the current X value of the sweep line.

Definition at line 42 of file parPlaneSweep.cpp.

int avlHsegCompare ( const void *  first,
const void *  second,
void *  param 

Comparison function to allow the AVL tree to compare halfsegments

firstis the first halfsegment for comparison.
secondis the second halfsegment for comparison.
paramis not used in this function

Definition at line 22 of file parPlaneSweep.cpp.

int binarySearchExists ( vector< halfsegment > &  region,
double  x,
int  hi = -1,
int  lo = 0 

A binary search function

Definition at line 117 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 152 of file parPlaneSweep.cpp.

int binarySearchSmallestGreater ( vector< halfsegment > &  region,
double  x,
int  hi = -1,
int  lo = -1 

A binary search function

Definition at line 133 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 589 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 918 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

regionthe region to split into strips
isoBoundsthe 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 756 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 702 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

r1halfsegments defining one input region
r2halfsegments definining the second input region
isoBounds[in/out] the x values indicating vertical lines that form strip boundaries.

Definition at line 835 of file parPlaneSweep.cpp.

bool hsegIDSort ( const halfsegment h1,
const halfsegment h2 

Definition at line 751 of file parPlaneSweep.cpp.

void insertBrokenSegsToActiveListAndDiscoveredQueue ( const vector< halfsegment > &  brokenSegs,
vector< halfsegment > &  result,
avl_table discoveredSegs,
avl_table 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 558 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 347 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 247 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 322 of file parPlaneSweep.cpp.