JarvisMarch.h

Go to the documentation of this file.

//
// Created by calvrix on 13/02/17.
//
#ifndef COMPUTGEOALGOS_JARVISMARCH_H
#define COMPUTGEOALGOS_JARVISMARCH_H

#include <iostream>
#include <bits/stdc++.h>
#include "origin.h"
using namespace std;

vector<int> indices_j;
void swap(double &p, double &q) {
    double tray = p;
    p = q;
    q = tray;
}


void swapElements(pair<double, double> &p, pair<double, double> &q) {
    swap(p.first, q.first);
    swap(p.second, q.second);
}



double execJarvisMarch(vector<pair<double, double> > Points) {
    int len, i, current, min = 0, hullLength = 0;
    len = int(Points.size());
    double x_min = Points[0].first; // a **double** value which gets the point with lowest y-coordinate
    pair<double, double> leftMost;
    //clock_t j_taken;
    //j_taken = clock();
    for (int i = 1; i < len; i++)
    {
        if (orderedSort(Points[i], Points[min]))
            x_min = Points[i].first, min = i;
    }

    P0 = leftMost = Points[min]; //P0 denotes the latest point permanently added to the hull
    indices_j.pb(min);
    swapElements(Points[hullLength++], Points[min]); //Swap the left-most point with the point in the set with index 0
    /*
     * Form the Hull by processing the remaining points
     */
    vector<pair<double , double> > convex_hull; // a **vector data structure** for storing the convex hull points
    do {
        convex_hull.pb(P0);
        for (i = hullLength, current = i; i < len; i++) {
            //Find the next point by comparing angles made with the last edge on the hull
            if (orderByPolar(Points[i], Points[current])) {
                current = i;
            }
        }
        //Since the above check starts from an index = hullLength, check if the start of the hull is the next point
        if (orderByPolar(Points[0], Points[current])) {
            current = 0;
        }
        P0 = Points[current];
        swapElements(Points[hullLength++], Points[current]); //Swap the latest added point with the point in the set having index equal to the hull length
    } while (P0 != leftMost);
    ofstream out_file;
    out_file.open("output.ch");
    out_file << "CH\n";
    out_file << len << " " << convex_hull.size() << "\n";
    for (int i = 0; i < len; i++) {
        out_file << Points[i].first << " " << Points[i].second << " 0\n";
    }
    for (i = 0; i < convex_hull.size(); i++) {
        out_file << ((i + 1)%len) << " ";
    }
    printVectorData(hullLength-1,convex_hull,"");
    //j_taken = clock()-j_taken;
    return 0;
}
#endif