in c++ i need to write a main class to call \" void convex_hull_func(int n, cons
ID: 3751511 • Letter: I
Question
in c++ i need to write a main class to call
" void convex_hull_func(int n, const std::vector<double> & x, const std::vector<double> & y, std::vector<point> & convex_hull)"
the code is bellow. just need help to call void convex_hull_func in main class in oreder to generate some points and compute convex hull
#include <iostream>
#include<cmath>
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;
duoble 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()
{
return 0;
}
Explanation / Answer
Code:
#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 vector<double> & x, const vector<double> & y, 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
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>>aty;
x.push_back(atx);
y.push_back(aty);
}
convex_hull_func(n,x,y,convex_hull); // function call
return 0;
}
Made some changes and fixed some errors.
You need the vector header to use vector and you need an algorithm header to sort the vector.
You also have to initialize the vectors for it to work.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.