convex_hull_sample.cpp File Reference

#include "convex_hull.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_for.h"
#include "tbb/parallel_reduce.h"
#include "tbb/blocked_range.h"
#include "tbb/tick_count.h"
#include "tbb/concurrent_vector.h"

Include dependency graph for convex_hull_sample.cpp:

Go to the source code of this file.

Classes
class	FillRNDPointsVector_buf
class	FindXExtremum
class	SplitByCP_buf
Typedefs
typedef util::point< double >	point_t
typedef tbb::concurrent_vector < point_t >	pointVec_t
typedef tbb::blocked_range < size_t >	range_t
Functions
void	appendVector (const point_t *src, size_t srcSize, pointVec_t &dest)
void	appendVector (const pointVec_t &src, pointVec_t &dest)
point_t	divide (const pointVec_t &P, pointVec_t &P_reduced, const point_t &p1, const point_t &p2)
void	divide_and_conquer (const pointVec_t &P, pointVec_t &H, point_t p1, point_t p2)
template<FindXExtremum::extremumType type>
point_t	extremum (const pointVec_t &P)
void	initialize (pointVec_t &points)
int	main (int argc, char *argv[])
void	quickhull (const pointVec_t &points, pointVec_t &hull)

---

Typedef Documentation

typedef util::point<double> point_t

Definition at line 46 of file convex_hull_sample.cpp.

typedef tbb::concurrent_vector< point_t > pointVec_t

Definition at line 47 of file convex_hull_sample.cpp.

typedef tbb::blocked_range<size_t> range_t

Definition at line 48 of file convex_hull_sample.cpp.

---

Function Documentation

void appendVector	(	const point_t *	src,
		size_t	srcSize,
		pointVec_t &	dest
	)

Definition at line 50 of file convex_hull_sample.cpp.

References tbb::concurrent_vector< T, A >::grow_by().

                                                                        {
    std::copy(src, src + srcSize, dest.grow_by(srcSize));
}

void appendVector	(	const pointVec_t &	src,
		pointVec_t &	dest
	)

Definition at line 54 of file convex_hull_sample.cpp.

References tbb::concurrent_vector< T, A >::begin(), tbb::concurrent_vector< T, A >::end(), tbb::concurrent_vector< T, A >::grow_by(), and tbb::concurrent_vector< T, A >::size().

                                                           {
    std::copy(src.begin(), src.end(), dest.grow_by(src.size()));
}

point_t divide	(	const pointVec_t &	P,
		pointVec_t &	P_reduced,
		const point_t &	p1,
		const point_t &	p2
	)

Definition at line 203 of file convex_hull_sample.cpp.

References SplitByCP_buf::farthestPoint(), SplitByCP_buf::grainSize, util::OUTPUT, tbb::parallel_reduce(), tbb::concurrent_vector< T, A >::size(), and util::VERBOSE.

                                                         {
    SplitByCP_buf sbcpb(p1, p2, P, P_reduced);
    // Must use simple_partitioner (see the comment in initialize() above)
    tbb::parallel_reduce(range_t(0, P.size(), SplitByCP_buf::grainSize),
                         sbcpb, tbb::simple_partitioner());

    if(util::VERBOSE) {
        std::stringstream ss;
        ss << P.size() << " nodes in bucket"<< ", "
            << "dividing by: [ " << p1 << ", " << p2 << " ], "
            << "farthest node: " << sbcpb.farthestPoint();
        util::OUTPUT.push_back(ss.str());
    }

    return sbcpb.farthestPoint();
}

void divide_and_conquer	(	const pointVec_t &	P,
		pointVec_t &	H,
		point_t	p1,
		point_t	p2
	)

Definition at line 221 of file convex_hull_sample.cpp.

References appendVector(), divide(), divide_and_conquer(), tbb::concurrent_vector< T, A >::push_back(), and tbb::concurrent_vector< T, A >::size().

                                                    {
    if (P.size()<2) {
        H.push_back(p1);
        appendVector(P, H);
    }
    else {
        pointVec_t P_reduced;
        pointVec_t H1, H2;

        point_t p_far = divide(P, P_reduced, p1, p2);

        divide_and_conquer(P_reduced, H1, p1, p_far);
        divide_and_conquer(P_reduced, H2, p_far, p2);

        appendVector(H1, H);
        appendVector(H2, H);
    }
}

template<FindXExtremum::extremumType type>

point_t extremum

(

const pointVec_t &

P

)

Definition at line 144 of file convex_hull_sample.cpp.

References FindXExtremum::extremeXPoint(), FindXExtremum::grainSize, tbb::parallel_reduce(), and tbb::concurrent_vector< T, A >::size().

                                      {
    FindXExtremum fxBody(P, type);
    tbb::parallel_reduce(range_t(0, P.size(), FindXExtremum::grainSize), fxBody);
    return fxBody.extremeXPoint();
}

void initialize

(

pointVec_t &

points

)

Definition at line 81 of file convex_hull_sample.cpp.

References tbb::concurrent_vector< T, A >::clear(), FillRNDPointsVector_buf::grainSize, cfg::MAXPOINTS, and tbb::parallel_for().

                                    {
    points.clear();

    // In the buffered version, a temporary storage for as much as grainSize elements 
    // is allocated inside the body. Since auto_partitioner may increase effective
    // range size which would cause a crash, simple partitioner has to be used.
    tbb::parallel_for(range_t(0, cfg::MAXPOINTS, FillRNDPointsVector_buf::grainSize),
                      FillRNDPointsVector_buf(points), tbb::simple_partitioner());
}

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 255 of file convex_hull_sample.cpp.

References util::gettime(), initialize(), cfg::NUM_THREADS_END, cfg::NUM_THREADS_START, util::ParseInputArgs(), quickhull(), util::time_diff(), and util::WriteResults().

                                 {
    util::ParseInputArgs(argc, argv);

    pointVec_t      points;
    pointVec_t      hull;
    int             nthreads;
    util::my_time_t tm_init, tm_start, tm_end;

    std::cout << " Starting TBB-bufferred version of QUICK HULL algorithm" << std::endl;

    for(nthreads=cfg::NUM_THREADS_START; nthreads<=cfg::NUM_THREADS_END;
        ++nthreads) {
        tbb::task_scheduler_init init(nthreads);
        tm_init = util::gettime();
        initialize(points);
        tm_start = util::gettime();
        quickhull(points, hull);
        tm_end = util::gettime();

        util::WriteResults(nthreads, util::time_diff(tm_init, tm_start),
            util::time_diff(tm_start, tm_end));
    }

    return 0;
}

void quickhull	(	const pointVec_t &	points,
		pointVec_t &	hull
	)

Definition at line 241 of file convex_hull_sample.cpp.

References appendVector(), tbb::concurrent_vector< T, A >::clear(), and divide_and_conquer().

                                                           {
    hull.clear();

    point_t p_maxx = extremum<FindXExtremum::maxX>(points);
    point_t p_minx = extremum<FindXExtremum::minX>(points);

    pointVec_t H;

    divide_and_conquer(points, hull, p_maxx, p_minx);
    divide_and_conquer(points, H, p_minx, p_maxx);

    appendVector(H, hull);
}