Find overlap rectangles and probe colors of different points

FindGraphOverlap.cpp

// FindGrpahColor.cpp 
//

#include <iostream>
#include <memory>
#include <fstream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>

using namespace std;

//Split string at delimiter and form a collection - generic code
vector<string> split(string phrase, string delimiter) {
	vector<string> list;
	string s = phrase;
	size_t pos = 0;
	string token;
	while ((pos = s.find(delimiter)) != string::npos) {
		token = s.substr(0, pos);
		list.push_back(token);
		s.erase(0, pos + delimiter.length());
	}
	list.push_back(s);
	return list;
}

bool IsValidString(string &str)
{
	if (str.size() == 0)
	{
		return false;
	}
	if (str.at(0) == '#')
	{
		return false;
	}
	return true;
}

class chart {
	//Topleft = X1,Y1 
	//BottomRight = X2,Y2
	int _x1 = 0;
	int _y1 = 0;
	int _x2 = 0;
	int _y2 = 0;

	//Color RGB
	int _red = 0;
	int _green = 0;
	int _blue = 0;


public:
	chart() = delete;

	chart(int x1, int y1, int x2, int y2, int r, int g, int b) : _x1(x1), _y1(y1), _x2(x2), _y2(y2), _red(r), _green(g), _blue(b) { }

	~chart() { /*cout << "chart :: destructor called." << endl;*/ }
	int getX1() { return _x1; }
	int getX2() { return _x2; }
	int getY1() { return _y1; }
	int getY2() { return _y2; }

	int getR() { return _red; }
	int getG() { return _green; }
	int getB() { return _blue;	}
	

};

typedef std::shared_ptr<chart> shChartPtr;
typedef std::vector< shChartPtr > vshChartCollection;

shChartPtr getChartshPtr(vector<string>& v1, vector<string>& v2)
{
	string::size_type sz;   // alias of size_t
	return shChartPtr( new  chart(stoi(v1[0], &sz),
				stoi(v1[1], &sz),
				stoi(v1[2], &sz),
				stoi(v1[3], &sz),
				stoi(v2[0], &sz),
				stoi(v2[1], &sz),
				stoi(v2[2], &sz)) );
	
}

class View {
	
	int _id=0; // viewid
	int _rp = 0; // probed redcolor store
	int _gp = 0; // probed greencolor store
	int _bp = 0; // probed bluecolor store

	vshChartCollection _vshchartCol;

	//validate input charts
	bool IsInputChartValid(shChartPtr var)
	{
		 
		int x1 = var->getX1();
		int y1 = var->getY1();
		int x2 = var->getX2();
		int y2 = var->getY2();

		//no negative value
		if (x1 < 0 ||
			x2 < 0 ||
			y1 < 0 ||
			y2 < 0
			) {
			cout << endl << _id << " : Negative dimensions not allwoed.";
			return false;
		}

		//chart should have correctly managed dimensions TopLeft(X1,Y1) 
		if ((x1 >= x2) || (y2 >= y1)) {
			cout << endl << _id << " : Chart Dimensions are incorrect topLeftX < BottomRightX And TopLeftY > BottomRightY.";
			return false;
		}

		//chart should have valid color range
		if (var->getR() < 0 || var->getR() > 255 ||
			var->getG() < 0 || var->getG() > 255 ||
			var->getB() < 0 || var->getB() > 255
			) {
			cout << endl << _id << " : Invalid Color codes must be in 0-255 range.";
			return false;
		}
		return true;
	}

	//Validate all charts; remove all invalid charts from collection and return size
	int ValidateAll_InputCharts()
	{
		for (vshChartCollection::iterator it = _vshchartCol.begin(); it != _vshchartCol.end(); )
		{
			if (false == IsInputChartValid(*it))
				it = _vshchartCol.erase(it);
			else
				++it;
		}
		//_vshchartCol.remove_if(IsInputChartValid);
		//vshChartCollection::iterator new_end = std::remove_if(_vshchartCol.begin(), _vshchartCol.end(), 
		//IsInputChartValid);
		//_vshchartCol.erase(new_end, _vshchartCol.end());

		return _vshchartCol.size();
	}

public:

	int getTCId() { return _id; }
	int getRP() { return _rp; }
	int getGP() { return _gp; }
	int getBP() { return _bp; }
		
	bool IsPresentInChart(chart* ch, int x, int y);
	//Probe the color of the cordinate
	void FindAverageColor(int probeX, int probeY);
	
	View(int id, vshChartCollection vc) : _id(id), _vshchartCol(vc){ }
	vshChartCollection& getChartshCol() { return _vshchartCol; }
	
	~View() { /*cout << "View :: Destructor called." << endl;*/ }
	int DoChartsOverlap();
	bool DoTwoChartsOverlap(shChartPtr var1, shChartPtr var2);
	bool FindTwoChartOverlap_IF(shChartPtr aptr, shChartPtr bptr);
	bool IsPresentInSharedChart(shChartPtr ch, int x, int y); 
	void SetAvgColorSharedPtr(int probeX, int probeY);
	int FindAllTwoCombinationOverlaps();

};


typedef std::shared_ptr<View> ViewPtr;
typedef std::vector<ViewPtr> ViewCollection;

ViewCollection viewshCollection;

typedef std::map<vshChartCollection, int > MapStore;
typedef MapStore::iterator itMapStore;


int View::FindAllTwoCombinationOverlaps()
{
	int overlapCnt = 0, nonOverlapCnt = 0, repeated = 0;

	int testCounter = 0;
	vshChartCollection vtemp, vtemp2;
	vshChartCollection::iterator vit;

	MapStore mpStore;
	itMapStore it;

	for (auto& var1 : _vshchartCol) {

		vtemp.clear();

		for (auto& var2 : _vshchartCol) {
			vtemp.clear();
			if (var1 == var2)
				continue;

			for (it = mpStore.begin(); it != mpStore.end(); ++it)
			{

				vtemp2 = it->first;
				int val = it->second;
				if ((vtemp2[0] == var1 && vtemp2[1] == var2) ||
					(vtemp2[0] == var2 && vtemp2[1] == var1)
					)
				{
					//cout << "already tested A-B or B-A ignoring."<<endl;
					repeated++;
				}
			}

			if (FindTwoChartOverlap_IF(var1, var2) == true)
			{
				//cout << endl << endl << "ViewID - " << _id << ":OVERLAP DETECTED  " << endl;
				//cout << "TopLeft____(x1,y1) = " << var1->getX1() << ", " << var1->getY1() << endl;
				//cout << "BottomRight(x2,y2) = " << var1->getX2() << ", " << var1->getY2() << endl;
				//cout << "TopLeft____(p1,q1) = " << var2->getX1() << ", " << var2->getX2() << endl;
				//cout << "BottomRight(p2,q2) = " << var2->getX2() << ", " << var2->getY2() << endl;
				++overlapCnt;
			}
			else
			{
				++nonOverlapCnt;
			}
			vtemp.push_back(var1);
			vtemp.push_back(var2);
			mpStore.insert(std::pair< vshChartCollection, int >(vtemp, testCounter++));

		}
	}
	//cout << "\nOverlap = " << overlapCnt << endl;
	//cout << "Non Overlap = " << nonOverlapCnt<< endl;
	return overlapCnt;

}

//Figure out if chart overlaps, 
int View::DoChartsOverlap(  )
{
	if ( ValidateAll_InputCharts() < 2 )
		return 0;
	
	return FindAllTwoCombinationOverlaps();
}

//Figure out if chart overlaps
bool View::DoTwoChartsOverlap(shChartPtr var1, shChartPtr var2)
{
	if (false == (IsInputChartValid(var1) && IsInputChartValid(var2)))
		return false;

	if (true == FindTwoChartOverlap_IF(var1, var2))
		return true;
	else
		return false;

}

bool View::IsPresentInSharedChart(shChartPtr ch, int x, int y)
{
	int x1 = ch->getX1();
	int y1 = ch->getY1();
	int x2 = ch->getX2();
	int y2 = ch->getY2();

	if ((x > x1 && x2 > x) && (y1 > y && y > y2))
		return true;

	return false;
}

void View::SetAvgColorSharedPtr(int probeX, int probeY)
{
	int i = 0;
	int r = 0, g = 0, b = 0;
	for (auto& var : getChartshCol()) {
		if (true == IsPresentInSharedChart(var, probeX, probeY))
		{
#if __DBG
			cout << "Probe belong to chart - " << i << endl;
#endif
			r += var->getR();
			g += var->getG();
			b += var->getB();
			++i;
		}

	}
	if (i == 0)
		return;

	_rp = r / i;
	_gp = g / i;
	_bp = b / i;

}

/*
Biggest function to find if the charts overlaps. Check 4 overlap criteria
1. Corners overlap
2. Edge Overlap
3. Nested graph
4. Partial containment

*/
bool View::FindTwoChartOverlap_IF(shChartPtr var1, shChartPtr var2) {
	
	//auto var = getChartshCol();

	//auto var1 = var[0];
	//auto var2 = var[1];


	int x1 = var1->getX1();
	int y1 = var1->getY1();
	int x2 = var1->getX2();
	int y2 = var1->getY2();

	int p1 = var2->getX1();
	int q1 = var2->getY1();
	int p2 = var2->getX2();
	int q2 = var2->getY2();

	int tcid = _id;
	if ((x1<p1) && (p1<x2) && (x2<p2)) //x1<p1<x2<p2 // RIGHT EDGE CHARTS MOVE
	{
		if ((y1>q1) && (q1>y2) && (y2>q2))
		{//bottom right corner
		 //cout << endl << _id << " - Bottom-Right Corner";
			return true;
		}
		if ((y1 >= q1) && (q2 >= y2))
		{
			//cout << endl << _id << " - RIGHT In-Edge";
			return true;
		}
		if ((q1 >= y1) && (y2 >= q2))
		{
			//cout << endl << _id << " - Right OUT-EDGE ";
			return true;
		}
		if ((q1>y1) && (y1>q2) && (q2>y2))
		{
			//cout << endl << _id << " - TOP Right Corner";
			return true;
		}
	}

	if ((p1<x1) && (x1<p2) && (p2<x2)) // left p1<x1<p2<x2
	{
		if ((y1>q1) && (q1>y2) && (y2>q2)) // y1>q1>y1>q2
		{
			//cout << endl << _id << " - LEFT - BottomCorner";
			return true;
		}
		if ((y1 >= q1) && (q2 >= y2)) // y1>q1>q2>y2
		{
			//cout << endl << _id << " - LEFT - InEdge ";
			return true;
		}
		if ((q1 >= y1) && (y2 >= q2)) // q1>y1>y2>q2
		{
			//cout << endl << _id << " - LEFT - OutEdge ";
			return true;
		}
		if ((q1>y1) && (y1>q2) && (q2>y2)) // q1>y1>y2>q2
		{
			//cout << endl << _id << " - LEFT - TOP Corner";
			return true;
		}
	}
	if ((q1>y1) && (y1>q2) && (q2>y2)) // q1>y1>q2>y2 //top right corner
	{
		if ((p1<x1) && (x1<p2) && (p2<x2)) // p1>x1>p2>x2
		{
			//cout << endl << _id << " - TOP ->Left Corner";
			return true;
		}
		if ((x1 <= p1) && (p2 <= x2)) // x1<p1<p2<x2
		{
			//cout << endl << _id << " - TOP InnerEdge";
			return true;
		}
		if ((p1 <= x1) && (x2 <= p2)) // p1<x1<x2<p2
		{
			//cout << endl << _id << " - TOP Out-Edge";
			return true;
		}
		if ((x1<p1) && (p1<x2) && (x2<p2)) // x1<p1<x2<p2
		{
			//cout << endl << _id << " - TOP ->Right Corner";
			return true;
		}
	}
	if ((y1>q1) && (q1>y2) && (y2>q2))//y1>q1>y2>q2 bottom
	{
		if (q2 > x1)
		{
			//cout << endl << _id << " - No OverLap";
			return true;
		}
		if ((p1<x1) && (x1<p2) && (p2<x2)) {
			//cout << endl << _id << " - Bottom Left Corner.";
			return true;
		}
		if ((x1 <= p1) && (p2 <= x2)) {
			//cout << endl << _id << " - Bottom INEDGE";
			return true;
		}
		if ((p1 <= x1) && (x2 <= p2)) {
			//cout << endl << _id << " - Bottom OUT-EDGE";
			return true;
		}
		if ((x1<p1) && (p1<x2) && (x2<p2)) {
			//cout << endl << _id << " - Bottom Right Corner";
			return true;
		}
	}
	if ((q1 >= y1) && (y2 >= q2) && (x1 <= p1) && (p2 <= x2)) {
		//cout << endl << _id << " - Vertical Intrunk overlap.";
		return true;
	}
	if ((y1 >= q1) && (q2 >= y2) && (p1 <= x1) && (x2 <= p2)) {
		//cout << endl << _id << " - Horizontal Intrunk overlap.";
		return true;
	}
	if (((p1 <= x1) && (p2 >= x2) && (q1 >= y1) && (y2 >= q2)) ||
		((x1 <= p1) && (p2 <= x2) && (y1 >= q1) && (q2 >= y2))
		) // nesting ??
	{
		//cout << endl << _id << " - Nested boxes .";
		return true;
	}

	// Following code to find out the failing / non overlapping maps
#if __DBG
	cout << endl << endl << "ViewID - " << _id << ": NO OVERLAP DETECTED  " << endl;
	cout << "TopLeft____(x1,y1) = " << x1 << ", " << y1 << endl;
	cout << "BottomRight(x2,y2) = " << x2 << ", " << y2 << endl;
	cout << "TopLeft____(p1,q1) = " << p1 << ", " << q1 << endl;
	cout << "BottomRight(p2,q2) = " << p2 << ", " << q2 << endl;
#endif

	return false;

}

bool readInputs(string path) 
{
	
	std::ifstream file(path);
	if (!file)
		return false;

	if (file.is_open()) 
	{

		std::string line;
		int testCaseId = 0;
		while (getline(file, line)) 
		{
	
			//cout << line << endl;
			
			if (false == IsValidString(line))
				continue;


			string::size_type sz;   // alias of size_t
			int nCharts = std::stoi(line, &sz);

			std::string tmp;
			vector<string> listCordinates;
			vector<string> listColors;
			
			//vChartCollection vc;
			vshChartCollection vshc;
			for (int count = 0; count < nCharts; ++count) 
			{
				listCordinates.clear();
				listColors.clear();

				getline(file, tmp);
				//cout << tmp << endl; 
				if (false == IsValidString(line))
					continue;
				
				listCordinates = split(tmp, ",");

				getline(file, tmp);
				//cout << tmp << endl;
				if (false == IsValidString(line))
					continue;
				listColors = split(tmp, ",");
					
				shChartPtr pshTemp = getChartshPtr(listCordinates, listColors);
				vshc.push_back(pshTemp);

			}
	
			ViewPtr val = ViewPtr(new View(testCaseId++, vshc));


			viewshCollection.push_back(val);

		}

	}

	file.close();

	return true;
}

/*
Inputs are read from an input file. Original Input formatted file is supplied under name "Input_org.txt"
	Number of chart in this view
	Topleft cordinate of chart 1, Bottom-RightCordinate of chart-1( X1,Y1,X2,Y2 )
	RGB of chart 1
	Topleft cordinate of chart 2,, Bottom-RightCordinate of chart-2( P1,Q1,P2,Q2 )
	RGB of chart 2
	# = comment ignored

	1. Get total "combination of 2" overlapping charts 
		For single View, enter only one View entry

	2. Probe points/cordinates are hardcoded value 

Limitation - 
   no proper format shared for how many color probes per View, hence it has to be tested manually 
   everytime, how to do - example is present state
   1. enter only single View details in input file.
   2. Modify source for Probe Cordinates
   Output -
    ViewID-0 - R= 0, G= 0, B= 0
	ViewID-0 - R= 10, G= 20, B= 30
	ViewID-0 - R= 40, G= 50, B= 60
	ViewID-0 - R= 25, G= 35, B= 45

*/
int main( int argc, char**argv )
{
	
	string path = argv[1] ? argv[1]: "";
	
	if (false == readInputs(path))
	{
		cout << "Input test cases file read failed. path issue." << endl;
		return 0;
	}

	int counter = 0;
	
	for( auto& var : viewshCollection)
	{
		cout << "\n\nViewID-" << var->getTCId() << ": Total Charts in View - " << var->getChartshCol().size() ;
		counter = var->DoChartsOverlap();
		cout << "\nChart Overlapped - " << counter ;

		/*
		 Hardcoded static color probing points, Call SetAvgColorSharedPtr for each point to be probed.
		*/
		//Probe A - outside of both charts
		var->SetAvgColorSharedPtr(10, 10);
		cout << "\nProbePointColor => R= " <<var->getRP() << ", G= "<< var->getGP()<< ", B= "<< var->getBP() ;
		
		////Probe B - Inside Chart A => should return Chart A colors
		//var->SetAvgColorSharedPtr(15, 35);
		//cout << "ViewID-" << var->getTCId() << " - R= " << var->getRP() << ", G= " << var->getGP() << ", B= " << var->getBP() << endl;

		////Probe C - Inside Chart B => should return Chart B colors
		//var->SetAvgColorSharedPtr(25, 15);
		//cout << "ViewID-" << var->getTCId() << " - R= " << var->getRP() << ", G= " << var->getGP() << ", B= " << var->getBP() << endl;

		////Probe D - Inside Overlap => should return average
		//var->SetAvgColorSharedPtr(25, 25);
		//cout << "ViewID-" << var->getTCId() << " - R= " << var->getRP() << ", G= " << var->getGP() << ", B= " << var->getBP() << endl;

	}



	return 0;
}

#Input.txt
#invalid negative X-axis
2
-10,20,20,10
255,0,0
10,40,20,30
0,0,255
#invalid negative Y-axis
2
10,20,20,10
255,0,0
10,-40,20,30
0,0,255
#Invalid RGB > 255
2
10,20,20,10
256,300,100
10,40,20,30
-10,0,255
#Invalid rectangle - A
2
0,0,0,0
0,30,100
10,40,20,30
10,0,255
#Invalid rectangle - B
2
10,20,20,10
0,30,100
0,0,0,0
10,0,255
#Invalid rectangle - x1<x2
2
10,20,5,20
255,44,100
10,20,30,0
10,0,255
#Invalid rectangle - x1==x2 - straight line
2
10,40,10,10
255,0,0
0,50,20,0
0,0,255
#Invalid rectangle - y1==y2 - straight line
2
10,40,100,40
255,0,0
0,50,20,0
0,0,255
#Valid case X axis mutual no overlap
2
10,20,20,10
255,0,0
30,20,40,10
0,255,0
#Valid case Y axis mutual no overlap
2
10,20,20,10
255,0,0
10,40,20,30
0,0,255
#Valid case Right Bottom Corner
2
10,40,30,20
255,0,0
20,30,40,10
0,0,255
#Valid case Right InEdge
2
10,40,30,20
255,0,0
20,30,40,25
0,0,255
#Valid case Right OutEdge
2
10,40,30,20
255,0,0
20,50,40,10
0,0,255
#Valid case Right Top Corner
2
10,40,30,20
255,0,0
20,50,40,30
0,0,255
#Valid case Left Lower Corner
2
10,40,30,10
255,0,0
0,20,20,0
0,0,255
#Valid case Left InEdge
2
10,40,30,10
255,0,0
0,20,20,10
0,0,255
#Valid case Left Out Edge
2
10,40,30,10
255,0,0
0,50,20,0
0,0,255
#Valid case Left Top Corner
2
10,40,30,10
255,0,0
0,50,20,20
0,0,255
#Valid case Left Out==IN Edge
2
10,40,30,10
255,0,0
0,40,20,10
0,0,255

#Valid case Bottom Left Corner
2
20,40,40,20
255,0,0
10,30,30,10
0,0,255
#Valid case Bottom IN-Edge
2
10,40,40,20
255,0,0
10,30,30,0
0,0,255
#Valid case Bottom Out-Edge
2
10,40,40,20
255,0,0
0,30,50,0
0,0,255
#Valid case Bottom Right Corner
2
10,40,40,20
255,0,0
20,30,50,0
0,0,255

#Valid case TOP Left Corner
2
20,40,40,20
255,0,0
10,50,30,30
0,0,255
#Valid case TOP INEdge Corner
2
0,40,40,0
255,0,0
10,50,30,30
0,0,255
#Valid case TOP Out-Edge Corner
2
10,40,40,10
255,0,0
0,50,50,30
0,0,255
#Valid case TOP Left Corner
2
10,30,30,10
255,0,0
20,40,40,20
0,0,255

#Valid case 1-in-1
2
10,30,30,10
255,0,0
0,40,40,0
0,0,255

#Valid case 1-in-1
2
0,40,40,0
255,0,0
10,30,30,10
0,0,255

#Valid case 1-in-1
2
10,30,40,20
255,0,0
20,40,30,10
0,0,255

#Valid case 1-in-1
2
20,40,30,10
255,0,0
10,30,40,20
0,0,255
#############################*********Monkey cases
2
10,20,20,10
255,0,0
0,10,10,0
0,0,255
2
10,20,20,10
255,0,0
10,10,20,0
0,0,255
2
10,20,20,10
255,0,0
20,10,30,0
0,0,255
2
10,20,20,10
255,0,0
20,20,30,10
0,0,255
2
10,20,20,10
255,0,0
20,30,30,20
0,0,255
2
10,20,20,10
255,0,0
0,30,10,20
0,0,255
2
10,20,20,10
255,0,0
0,20,10,10
0,0,255
2
10,20,20,10
255,0,0
0,10,10,0
0,0,255

#Valid case Right Bottom Corner 14*13/2 = 91
14
0,60,20,40
110,120,130
20,60,40,40
140,150,160
40,60,60,40
170,180,190
0,40,20,20
200,210,220
20,40,40,20
230,240,255
40,40,60,20
255,255,255
0,20,20,0
250,240,240
20,20,40,0
150,140,130
40,20,60,0
120,125,140
10,50,30,30
112,114,116
30,50,50,30
118,120,122
10,30,30,10
124,126,126
30,30,50,20
128,130,134
0,60,60,0
0,255,0

Question Statement - Give two rectangles (TopLeft) and (BottomRight) cordinates and their color respectively, Find
1 . if they overlap
2. Color of a coordinate , if lies in overlapping zone get the average of two colors.