write a code in c++ do following

Convex hull : Let us write a function to compute the convex hull of a set of n points in a plane. Instead of carrying around too many arrays, let us employ the power of C++ and use a class. Write the following Point class. Make everything public for simplicity. class Point { public: Point(double x1, double y1) : x(x1), y(y1) { r = sqrt(x*x + y*y); if (r > 0.0) { theta = atan2(y,x); } else { theta = 0; } } double x; double y; double r; double theta; }; We compute the values of r and for later use in comparisons. This is the advantage of writing a class: we can store relevant information all in one object. As explained in the lectures, we shall require a comparison function. For points a and b, we test if a < b. If a = b, we test if ra < rb. Write the following comparison function. bool vcomp(const Point &a, const Point &b) { if (a.theta < b.theta) { return true; } else if (a.theta > b.theta) { return false; } return (a.r < b.r); } 5 Now we write the convex hull function. This is the function signature: void convex_hull_func(int n, const std::vector & x, const std::vector & y, std::vector & convex_hull); The inputs are (i) int n (number of points) (ii) arrays x and y of type double (coordinates of points). The output is (iii) array convex hull of type Point. We need the input n. Do not assume the length of the input arrays x and y is exactly n. They could be longer. We could also make the input an array of Point objects. The following pseudocode describes the steps. You can use it as the basis to write a working function. 1. Let us define a constant tol = 1014 for later use. 2. We begin by clearing convex hull and testing for the trivial case n 3. If n 3 we populate convex hull with the input coordinates and return. We insert the point (x[0], y[0]) at the end to close the polygon. const double tol = 1.0e-14; convex_hull.clear(); if (n <= 0) return; // simple safeguard if (n <= 3) { for (int i = 0; i < n; ++i) { convex_hull.push_back( Point(x[i],y[i]) ); } convex_hull.push_back( Point(x[0],y[0]) ); // close the polygon return; } 3. Next, find the minimum value ymin and save the partner value xmin. Also store the index imin where the minimum is located. Initialize the variables int imin=0, double xmin=x[0] and double ymin=y[0]. (a) Loop from i = 1 to n 1. (b) Test if ymin > y[i]. If yes, then set imin=i, xmin=x[i] and ymin=y[i]. (c) Else test if ymin == y[i]. If yes, then test if xmin > x[i]. If yes, then set imin=i, xmin=x[i] and ymin=y[i]. 6 4. Now construct and sort the vectors vi . Do it as follows: std::vector v; for (int iv = 0; iv < n; ++iv) { double vx = x[iv] - xmin; double vy = y[iv] - ymin; if (iv == imin) { // avoid roundoff error vx = 0; vy = 0; } v.push_back( Point(vx,vy) ); } // sort the vectors std::sort(v.begin(), v.end(), vcomp); 5. Note the following important details: (a) The special case vx = 0 and vy = 0 for iv == imin is to avoid roundoff error. This is the starting point of the convex hull. (b) In the lecture, there were only n 1 vectors vi . (c) Furthermore, the lecture also stated (for the starting point) Without loss of generality, suppose this point is (x1, y1). (d) This is impractical for computation. Instead, the code has n vectors vi , with vi = (0, 0) for i = imin. The comparison function vcomp has been formulated so that the sort algorithm will move that item to the first element in the sorted array. 6. Now construct the points pi . As stated in the lecture, pi and vi can share the same memory. Note that p0 = (xmin, ymin) automatically (from the sort). // add (xmin, ymin) to sorted vectors for (int ip = 0; ip < n; ++ip) { v[ip].x += xmin; v[ip].y += ymin; } std::vector &p = v; // p is reference to v, shares same memory 7. Initialize the stack for the convex hull. convex_hull.push_back(p[0]); convex_hull.push_back(p[1]); 7 8. Next loop through the points pi and update the stack. The tests are described in the lecture. However, they require vector calculus. It is unrealistic to ask you to code them on your own. I will give you the code for the loop of tests. We use the const parameter tol in the tests. int i = convex_hull.size(); while (i < n) { // test for direction of rotation of edges int last = convex_hull.size() - 1; int second_last = last - 1; double ux = convex_hull[last].x - convex_hull[second_last].x; double uy = convex_hull[last].y - convex_hull[second_last].y; double wx = p[i].x - convex_hull[last].x; double wy = p[i].y - convex_hull[last].y; double cross_product = ux*wy - uy*wx; if (cross_product > tol) { // counterclockwise rotation = add to convex hull convex_hull.push_back(p[i]); ++i; } else if (fabs(cross_product) <= tol) { // straight line = replace old point by new point convex_hull.pop_back(); convex_hull.push_back(p[i]); ++i; } else { // clockwise rotation = erase a point in the stack convex_hull.pop_back(); } } 9. After the loop is over, the stack contains the points of the convex hull. Close the convex hull polygon by adding p0 to the end. convex_hull.push_back(p[0]); 10. We are done. Exit the function. Write a main program to call the function. Generate some points and compute the convex hull. Plot the points (in a spreadsheet?). Plot the convex hull (closed polygon). See if it works. The function will work even if some of the points are not distinct. The function will work even if ALL the points coincide. 8 If you know about C++ iterators, there is a more elegant way to write the code for the tests. We use a const reverse iterator to access the last and second last elements in the stack. We use const because we do not change the data inside the Point objects. You should learn how to use C++ iterators. int i = convex_hull.size(); while (i < n) { // test for direction of rotation of edges std::vector::const_reverse_iterator cit = convex_hull.crbegin(); const Point &last_pt = *cit; const Point &second_last_pt = *(++cit); double ux = last_pt.x - second_last_pt.x; double uy = last_pt.y - second_last_pt.y; double wx = p[i].x - last_pt.x; double wy = p[i].y - last_pt.y; double cross_product = ux*wy - uy*wx; if (cross_product > tol) { // counterclockwise rotation = add to convex hull convex_hull.push_back(p[i]); ++i; } else if (fabs(cross_product) <= tol) { // straight line = replace old point by new point convex_hull.pop_back(); convex_hull.push_back(p[i]); ++i; } else { // clockwise rotation = erase a point in the stack convex_hull.pop_back(); } }

Convex hull #2

I was impressed by the suggestion in class by a student, for a computationally cheaper sort function. The suggestion is equivalent to the use of the vector cross product. We do not need the angle , and we do not need to compute any square roots. Let us implement the sort using the vector cross product. To avoid confusion, let us define a new class Point2. You can rename the previous class Point1 if you like. Write the following Point2 class. Make everything public for simplicity. class Point2 { public: Point2(double x1, double y1) : x(x1), y(y1) { r2 = x*x + y*y; } double x; double y; double r2; }; The sort function is as follows. We are given input objects a and b. 1. If axby aybx > 0, return true. 2. If axby aybx < 0, return false. 3. If axby aybx = 0, test if a 2 x + a 2 y < b2 x + b 2 y . Write the following comparison function. bool vcomp2(const Point2 &a, const Point2 &b) { double diff = a.x*b.y - b.x*a.y; if (diff > 0.0) { return true; } else if (diff < 0.0) { return false; } return (a.r2 < b.r2); } Everything else is the same as in Question 1.4. Replace Point by Point2 and vcomp by vcomp2. 10 Here are some input points to test your code. I stated that the algorithm will work even if some of the points coincide. Let us have 104 points, each repeated 100 times, so a total of 106 points (why not?). std::vector x_vec; std::vector y_vec; int n = 10000; for (int i = 0; i < 100*n; ++i) { x = cos(i%n); y = sin(3*(i%n)) * (1.0 - 0.5*x*x); x_vec.push_back(x); y_vec.push_back(y); } On my computer, the original algorithm took 0.81 sec and the new algorithm took 0.67 sec.