JarvisMarch.h File Reference

#include <iostream>
#include <bits/stdc++.h>
#include "origin.h"

Include dependency graph for JarvisMarch.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
void	swap (double &p, double &q)
	Generic Swap Function. More...
void	swapElements (pair< double, double > &p, pair< double, double > &q)
	Point Swap Function. More...
double	execJarvisMarch (vector< pair< double, double > > Points)
	Jarvis March Algorithm Implementation More...

Variables
vector< int >	indices_j

Function Documentation

double execJarvisMarch

(

vector< pair< double, double > >

Points

)

Jarvis March Algorithm Implementation

1. First Step is to sort points with respect to their x coordinates.
   
2. Start from the left-most point.
   
3. Choose and add the point that makes the largest obtuse interior angle with the latest edge on the hull.
   
4. Swap the point with the corresponding nth point in the point set to avoid repeating already chosen 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;
}

void swap	(	double &	p,
		double &	q
	)

Generic Swap Function.

                                {
    double tray = p;
    p = q;
    q = tray;
}

void swapElements	(	pair< double, double > &	p,
		pair< double, double > &	q
	)

Point Swap Function.

Swaps the coordinates of the points passed. Used for efficiency by reducing number of checks

                                                                    {
    swap(p.first, q.first);
    swap(p.second, q.second);
}

Variable Documentation

vector<int> indices_j