ETSP.h

//-------------------------------------------------------------------
//
//  Permission is  hereby  granted, free  of charge, to any person
//  obtaining a copy of this software and associated documentation
//  files  ( the "Software" ),  to  deal in  the  Software without
//  restriction, including  without limitation the rights to  use,
//  copy, modify,  merge, publish, distribute, sublicense,  and/or
//  sell copies of the Software, and to permit persons to whom the
//  Software is  furnished  to do  so,  subject  to  the following
//  conditions:
//
//  The above  copyright notice  and  this permission notice shall
//  be included  in  all copies  or  substantial  portions  of the
//  Software.
//
//  THE SOFTWARE IS  PROVIDED  "AS IS",  WITHOUT  WARRANTY  OF ANY
//  KIND,  EXPRESS OR IMPLIED, INCLUDING  BUT NOT  LIMITED  TO THE
//  WARRANTIES   OF  MERCHANTABILITY,  FITNESS  FOR  A  PARTICULAR
//  PURPOSE AND NONINFRINGEMENT. IN NO EVENT  SHALL THE AUTHORS OR
//  COPYRIGHT HOLDERS  BE  LIABLE FOR  ANY CLAIM, DAMAGES OR OTHER
//  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
//  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
//  USE OR OTHER DEALINGS IN THE SOFTWARE.
//-------------------------------------------------------------------
//-------------------------------------------------------------------

#ifndef _ETSP_H_
#define _ETSP_H_

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include "vec3.h"

class ETSP
{
	public:
	ETSP(std::vector<vec3> &myData, int start, int end, int myplane);
	int plane;
	std::vector<vec3> data;
        std::vector<int> order;

	private:
	std::vector<std::vector<int> > graph;  //adjeceny list of the MST
        std::vector<int> inverse_mapped_order;
	void MST();
	std::vector<int> match();
	void orderFromMST();
	void traverse(int curr, std::vector<bool> &visited);
	void orderFromMatch();
	double areaTri(int i, int j);
	double computeArea();
};

#endif //_ETSP_H_