Hey guys!
I'm trying to write a program that calculates the area of the convex hull of a set of points in a plane. I can find which points construct the convex hull but calculating the area is a little bit difficult for me. I guess the problem is that I sort the points, and then remove duplicates before calculating the area.
Any help will be appreciated :).
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <fstream>
#include <algorithm>
using namespace std;
class Point
{
private:
double x;
double y;
public:
void get_coords(double a, double b)
{
x = a;
y = b;
}
double get_x()
{
return x;
}
double get_y()
{
return y;
}
};
int get_orientation(Point P1, Point P2, Point P);
bool is_internal(Point P1, Point P2, Point P3, Point P);
int main (int argc, char *argv[])
{
if(argc < 2) {
cout << "Not enough arguments in the command line." << endl;
system("PAUSE");
return 0;
}
const char* filename = argv[1];
ifstream inFile(filename);
vector<Point> P;
vector<int> convex;
int pts, cvx = 1;
if(!inFile) {
cout << endl << "Can't open input file." << filename;
system("PAUSE");
return 1;
}
pts = 0;
while(!inFile.eof()) {
inFile >> a;
inFile >> b;
Temp.get_coords(a, b);
P.push_back(Temp);
pts++;
}
for(int i = 0; i < pts; i++) {
convex.push_back(i);
}
for(int i = 0; i < pts; i++) {
for(int j = 0; j < pts; j++) {
if(j != i) {
for(int k = 0; k < pts; k++) {
if(k != j && k != i) {
for(int l = 0; l < pts; l++) {
if(l != i && l != j && l != k) {
if(is_internal(P[i], P[j], P[k], P[l])) {
convex[l] = -1;
}
}
}
}
}
}
}
}
cout << endl;
sort(convex.begin(), convex.end());
convex.erase(unique(convex.begin(), convex.end()), convex.end());
cout << endl << convex.size() << endl << endl;
area = 0;
cvx = convex.size();
for(int j, i = 0; i < cvx; i++) {
if(convex[i] >= 0) {
cout << convex[i] << endl;
j = (i + 1) % cvx;
area += P[convex[i]].get_x()*P[(convex[j])].get_y();
area -= P[convex[i]].get_y()*P[(convex[j])].get_x();
}
}
cout << "Area of the convex hull is " << area/2 << endl;
system("PAUSE");
return 0;
}
int get_orientation(Point P1, Point P2, Point P)
{
double orientation = ((P2.get_x() - P1.get_x()) * (P.get_y() - P1.get_y()) - (P2.get_y() - P1.get_y()) * (P.get_x() - P1.get_x()));
if (orientation > 0) {
return 1;
}
else if (orientation < 0) {
return -1;
}
else {
return 0;
}
}
bool is_internal(Point P1, Point P2, Point P3, Point P)
{
int line1 = get_orientation(P1, P2, P);
int line2 = get_orientation(P2, P3, P);
int line3 = get_orientation(P3, P1, P);
return ((line1 == line2) && (line2 == line3));
}