parPlaneSweep.cpp File Reference

#include "parPlaneSweep.h"
#include <iomanip>

Go to the source code of this file.

Functions
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.

Parameters

param

is 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

Parameters

first	is the first halfsegment for comparison.
second	is the second halfsegment for comparison.
param	is 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

Parameters

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 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

Parameters

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 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.