i need to plot the graph of (x,y) data points and convex_hull(x,y) in c++ my cod

ID: 3752220 • Letter: I

Question

i need to plot the graph of (x,y) data points and convex_hull(x,y) in c++

my code is below

#include <iostream>
#include<cmath>
#include <vector>
#include<algorithm>

using namespace std;
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;
};
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);
}

void convex_hull_func(int n, const std::vector<double> & x,const std::vector<double> & y, std::vector<Point> & convex_hull){
const double tol=1.0*exp(-14);
convex_hull.clear();

int imin=0;
double xmin=x[0];
double ymin=y[0];
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;
}
for(int i=1;i<=n-1;i++){
if(ymin>y[i]){
imin=i;
xmin=x[i];
ymin=y[i];
}else if(ymin==y[i]){
if(xmin>x[i]){
imin=i;
xmin=x[i];
ymin=y[i];
}
}
}
std::vector<Point> 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);
// add (xmin, ymin) to sorted vectors
for (int ip = 0; ip < n; ++ip) {
v[ip].x += xmin;
v[ip].y += ymin;
}
std::vector<Point> &p = v; // p is reference to v, shares same memory
convex_hull.push_back(p[0]);
convex_hull.push_back(p[1]);
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();
}
}
convex_hull.push_back(p[0]);
}

int main()
{

int n,i;

double atx,aty;

vector<double> x;

vector<double> y;

vector<Point> convex_hull; // declaring the parameters for the function call.

cout<<"Enter the number of points: "; // initialization of n

cin>>n;

for(i=0;i<n;i++) // initialization of x and y

{

cout<<"Enter the x and the y points("<<i+1<<"):";

cin>>atx;
cin>>aty;

x.push_back(atx);

y.push_back(aty);
convex_hull.push_back(Point(x[i],y[i]));
}

convex_hull_func(n,x,y,convex_hull); // function call

return 0;
}

Explanation / Answer

// A simple representation of graph using STL

#include<bits/stdc++.h>

using namespace std;

// A utility function to add an edge in an

// undirected graph.

void addEdge(vector<int> adj[], int u, int v)

{

adj[u].push_back(v);

adj[v].push_back(u);

}

// A utility function to print the adjacency list

// representation of graph

void printGraph(vector<int> adj[], int V)

{

for (int v = 0; v < V; ++v)

{

cout << " Adjacency list of vertex "

<< v << " head ";

for (auto x : adj[v])

cout << "-> " << x;

printf(" ");

}

// Driver code

int main()

{

int V = 5;

vector<int> adj[V];

addEdge(adj, 0, 1);

addEdge(adj, 0, 4);

addEdge(adj, 1, 2);

addEdge(adj, 1, 3);

addEdge(adj, 1, 4);

addEdge(adj, 2, 3);

addEdge(adj, 3, 4);

printGraph(adj, V);

return 0;

}