1/*
2 Copyright (c) 2005-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17#ifndef __CONVEX_HULL_H__
18#define __CONVEX_HULL_H__
19
20#include <cassert>
21#include <cstdlib>
22#include <iostream>
23#include <iomanip>
24#include <sstream>
25#include <vector>
26#include <string>
27#include <cstring>
28#include <algorithm>
29#include <functional>
30#include <climits>
31#include "tbb/tick_count.h"
32#include "tbb/task_scheduler_init.h"
33#include "../../common/utility/utility.h"
34#include "../../common/utility/fast_random.h"
35
36using namespace std;
37
38namespace cfg {
39 // convex hull problem user set parameters
40 long numberOfPoints = 5000000; // problem size
41 utility::thread_number_range threads(tbb::task_scheduler_init::default_num_threads);
42
43 // convex hull grain sizes for 3 subproblems. Be sure 16*GS < 512Kb
44 const size_t generateGrainSize = 25000;
45 const size_t findExtremumGrainSize = 25000;
46 const size_t divideGrainSize = 25000;
47};
48
49namespace util {
50 bool silent = false;
51 bool verbose = false;
52 vector<string> OUTPUT;
53
54 // utility functionality
55 void ParseInputArgs(int argc, char* argv[]) {
56 utility::parse_cli_arguments(
57 argc,argv,
58 utility::cli_argument_pack()
59 //"-h" option for displaying help is present implicitly
60 .positional_arg(cfg::threads,"n-of-threads",utility::thread_number_range_desc)
61 .positional_arg(cfg::numberOfPoints,"n-of-points","number of points")
62 .arg(silent,"silent","no output except elapsed time")
63 .arg(verbose,"verbose","turns verbose ON")
64 );
65 //disabling verbose if silent is specified
66 if (silent) verbose = false;;
67 }
68
69 template <typename T>
70 struct point {
71 T x;
72 T y;
73 //According to subparagraph 4 of paragraph 12.6.2 "Initializing bases and members" [class.base.init]
74 //of ANSI-ISO-IEC C++ 2003 standard, POD members will _not_ be initialized if they are not mentioned
75 //in the base-member initializer list.
76
77 //For more details why this needed please see comment in FillRNDPointsVector_buf
78 point() {}
79 point(T _x, T _y) : x(_x), y(_y) {}
80 };
81
82 std::ostream& operator<< (std::ostream& o, point<double> const& p) {
83 return o << "(" << p.x << "," << p.y << ")";
84 }
85
86 struct rng {
87 static const size_t max_rand = USHRT_MAX;
88 utility::FastRandom my_fast_random;
89 rng (size_t seed):my_fast_random(seed) {}
90 unsigned short operator()(){return my_fast_random.get();}
91 unsigned short operator()(size_t& seed){return my_fast_random.get(seed);}
92 };
93
94
95 template < typename T ,typename rng_functor_type>
96 point<T> GenerateRNDPoint(size_t& count, rng_functor_type random, size_t rand_max) {
97 /* generates random points on 2D plane so that the cluster
98 is somewhat circle shaped */
99 const size_t maxsize=500;
100 T x = random()*2.0/(double)rand_max - 1;
101 T y = random()*2.0/(double)rand_max - 1;
102 T r = (x*x + y*y);
103 if(r>1) {
104 count++;
105 if(count>10) {
106 if (random()/(double)rand_max > 0.5)
107 x /= r;
108 if (random()/(double)rand_max > 0.5)
109 y /= r;
110 count = 0;
111 }
112 else {
113 x /= r;
114 y /= r;
115 }
116 }
117
118 x = (x+1)*0.5*maxsize;
119 y = (y+1)*0.5*maxsize;
120
121 return point<T>(x,y);
122 }
123
124 template <typename Index>
125 struct edge {
126 Index start;
127 Index end;
128 edge(Index _p1, Index _p2) : start(_p1), end(_p2) {};
129 };
130
131 template <typename T>
132 ostream& operator <<(ostream& _ostr, point<T> _p) {
133 return _ostr << '(' << _p.x << ',' << _p.y << ')';
134 }
135
136 template <typename T>
137 istream& operator >>(istream& _istr, point<T> _p) {
138 return _istr >> _p.x >> _p.y;
139 }
140
141 template <typename T>
142 bool operator ==(point<T> p1, point<T> p2) {
143 return (p1.x == p2.x && p1.y == p2.y);
144 }
145
146 template <typename T>
147 bool operator !=(point<T> p1, point<T> p2) {
148 return !(p1 == p2);
149 }
150
151 template <typename T>
152 double cross_product(const point<T>& start, const point<T>& end1, const point<T>& end2) {
153 return ((end1.x-start.x)*(end2.y-start.y)-(end2.x-start.x)*(end1.y-start.y));
154 }
155
156 // Timing functions are based on TBB to always obtain wall-clock time
157 typedef tbb::tick_count my_time_t;
158
159 my_time_t gettime() {
160 return tbb::tick_count::now();
161 }
162
163 double time_diff(my_time_t start, my_time_t end) {
164 return (end-start).seconds();
165 }
166
167 void WriteResults(int nthreads, double initTime, double calcTime) {
168 if(verbose) {
169 cout << " Step by step hull construction:" << endl;
170 for(size_t i = 0; i < OUTPUT.size(); ++i)
171 cout << OUTPUT[i] << endl;
172 }
173 if (!silent){
174 cout
175 << " Number of nodes:" << cfg::numberOfPoints
176 << " Number of threads:" << nthreads
177 << " Initialization time:" << setw(10) << setprecision(3) << initTime
178 << " Calculation time:" << setw(10) << setprecision(3) << calcTime
179 << endl;
180 }
181 }
182};
183
184#endif // __CONVEX_HULL_H__
185