Elysian Shadows

The Next Generation of 2D Roleplaying Games
http://elysianshadows.com/phpBB3/

real world challenge

http://elysianshadows.com/phpBB3/viewtopic.php?t=3334

Page 1 of 1

real world challenge

Posted: Sun Mar 29, 2009 7:34 pm
by avansc
i was gonna make a nice slide with info on, but some people were inpatient. so this is just the watered down version.

my friends dad worked at this place that did geology scanning type thing where they had these planes fly in circuits with scanning equipment that looked for oil, gold and so on. well turns out that these coords had to have an over all anti clockwise trend, and one day the data was clockwise and cost them millions of dollars. so your task is to write a program. or just complete the skeleton program, that makes sure that date points is anticlockwise over all, and that no two lines bewteen 4 coords cross. ie, it never flys over the same place twice.

Image

that image isn't numbered, but that could be an image. so you can see if you trace one way its clock wise, and trace the other is anti..

here is the skeleton code.

have fun kids.

NOTE: you can add any data structures or functions to the class to help you.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>

using namespace std;

struct sVec2;
class cGeo_Calc;

struct sVec2
{
	double x;
	double y;
};

class cGeo_Calc
{
public:
	cGeo_Calc(vector<sVec2> tList);
	~cGeo_Calc();
	
	bool crossing(); // you finish this.
	bool clock_Wise(); // you finish this.
	
private:
	vector<sVec2> point_List;
};

cGeo_Calc::cGeo_Calc(vector<sVec2> tList)
{
	this->point_List = tList;
	printf("cGeo_Calc Created with %d data points.\n", this->point_List.size());
}

cGeo_Calc::~cGeo_Calc()
{
}

bool cGeo_Calc::crossing()
{
	// TODO : Complete this yourself.
	
	return false;
}

bool cGeo_Calc::clock_Wise()
{
	printf("STATUS : ");
	
	if(!this->crossing())
	{
		printf("ERROR IN DATA, lines cross.\n");
		return false;
	}
	// TODO : Complete this yourself.
	
	return false;
}

////// test bed //////

void test_Bed()
{

	vector<sVec2> temp;
	sVec2 v;
	v.x = 0;
	v.y = 0;
	
	for(int a = 0;a <= 10000;a++)
	{
		v.x = 1000*cos(360*((double)a/10000)/180*3.141592653589793);
		v.y = 1000*sin(360*((double)a/10000)/180*3.141592653589793);
		temp.push_back(v);
	}
	
	
	cGeo_Calc *test = new cGeo_Calc(temp);
	if(test->clock_Wise())
	{
		printf("Successful, data is anti clock wise.\n\n");
	}else
	{
		printf("Failure, data is clock wise.\n\n");
	}

	///////////////// test 2 ///////////////////

	temp.clear();
	v.x = 0;
	v.y = 0;
	
	for(int a = 0;a <= 10000;a++)
	{
		v.x = 1000*cos(360*((double)a/10000)/180*3.141592653589793);
		v.y = 1000*sin(360*((double)a/10000)/180*3.141592653589793);
		temp.push_back(v);
	}
	
	
	test = new cGeo_Calc(temp);
	if(test->clock_Wise())
	{
		printf("Successful, data is anti clock wise.\n\n");
	}else
	{
		printf("Failure, data is clock wise.\n\n");
	}
	
	delete test;
}

////// done bed //////

int main (int argc, char * const argv[])
{
	printf("Start of program.\n\n");
	test_Bed();
	return 0;
}

Re: real world challenge

Posted: Mon Mar 30, 2009 3:34 pm
by RyanPridgeon
You cruel, cruel person.

I might have a go at this :D

Re: real world challenge

Posted: Mon Mar 30, 2009 6:21 pm
by Rada
I'm not sure what the challenge is.
well turns out that these coords had to have an over all anti clockwise trend
is the polygon that you've drawn an area that was mapped with the scanning equipment? do they see a shape on the screen and are interpreting the shape, or are they given a series of points?

Re: real world challenge

Posted: Mon Mar 30, 2009 9:54 pm
by avansc
Image

left is clock right is counter

Re: real world challenge

Posted: Tue Mar 31, 2009 3:31 pm
by avansc
it seems either no one likes these challenges, or this one is to hard.

either way, if no one shows interest soon i'll just post the answer.

Re: real world challenge - solution

Posted: Tue Mar 31, 2009 6:28 pm
by avansc
seems people arent really interested.
here you go.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>

using namespace std;

struct sVec2;
class cGeo_Calc;
struct sLine;
double len_vec(sVec2 *v);
double dot_prod(sVec2 *v1, sVec2 *v2);
int side_of_line(sVec2 *A, sVec2 *B, sVec2 *P);

struct sVec2
{
	double x;
	double y;
};

struct sLine
{
	sVec2 A;
	sVec2 B;
}; 

double len_vec(sVec2 *v)
{
	return sqrt(pow(v->x,2) + pow(v->y,2));
}

double dot_prod(sVec2 *v1, sVec2 *v2)
{
	return (v1->x * v2->x) + (v1->y * v2->y);
}

int side_of_line(sVec2 *A, sVec2 *B, sVec2 *P)
{
   return float(P->y - A->y) * float(B->x - A->x) - float(P->x - A->x) * float(B->y - A->y);
}

class cGeo_Calc
{
public:
	cGeo_Calc(vector<sVec2> tList);
	~cGeo_Calc();
	
	bool line_Inter(sLine AB, sLine CD);
	double angle(sVec2 *A, sVec2 *B, sVec2 *C);

	bool crossing(); // you finish this.
	bool clock_Wise(); // you finish this.
	
private:
	vector<sVec2> point_List;
};

double cGeo_Calc::angle(sVec2 *A, sVec2 *B, sVec2 *C)
{
	sVec2 *AB = (sVec2*)malloc(sizeof(sVec2));
	AB->x = B->x - A->x;
	AB->y = B->y - A->y;
	sVec2 *BC = (sVec2*)malloc(sizeof(sVec2));
	BC->x = C->x - B->x;
	BC->y = C->y - B->y;
	double dot = dot_prod(AB, BC);
	double AB_len = len_vec(AB);
	double BC_len = len_vec(BC);

	double ang = acos((dot)/(AB_len*BC_len))*180/3.141592653589793;
	free(AB);
	free(BC);

	if(side_of_line(A, B, C) > 0)
	{
		return ang;
	}
	return -1*ang;
}

bool cGeo_Calc::line_Inter(sLine AB, sLine CD)
{
	if(((CD.B.y - CD.A.y)*(AB.B.x - AB.A.x) - (CD.B.x - CD.A.x)*(AB.B.y - AB.A.y)) == 0)
		return false;

	if(((CD.B.y - CD.A.y)*(AB.B.x - AB.A.x) - (CD.B.x - CD.A.x)*(AB.B.y - AB.A.y)) != 0)
	{
		if(((((CD.B.x - CD.A.x)*(AB.A.y - CD.A.y) - (CD.B.y - CD.A.y)*(AB.A.x - CD.A.x))/
				((CD.B.y - CD.A.y)*(AB.B.x - AB.A.x) - (CD.B.x - CD.A.x)*(AB.B.y - AB.A.y))) > 0) && 
				((((CD.B.x - CD.A.x)*(AB.A.y - CD.A.y) - (CD.B.y - CD.A.y)*(AB.A.x - CD.A.x))/
				((CD.B.y - CD.A.y)*(AB.B.x - AB.A.x) - (CD.B.x - CD.A.x)*(AB.B.y - AB.A.y))) < 1))
		{
			if((((AB.B.x - AB.A.x)*(AB.A.y - CD.A.y) - (AB.B.y - AB.A.y)*(AB.A.x - CD.A.x))/
				((CD.B.y - CD.A.y)*(AB.B.x - AB.A.x) - (CD.B.x - CD.A.x)*(AB.B.y - AB.A.y)) > 0) && 
				(((AB.B.x - AB.A.x)*(AB.A.y - CD.A.y) - (AB.B.y - AB.A.y)*(AB.A.x - CD.A.x))/
				((CD.B.y - CD.A.y)*(AB.B.x - AB.A.x) - (CD.B.x - CD.A.x)*(AB.B.y - AB.A.y)) < 1))
			{
				return true;
			}
		}
	}

	return false;
}


cGeo_Calc::cGeo_Calc(vector<sVec2> tList)
{
	this->point_List = tList;
	printf("cGeo_Calc Created with %d data points.\n", this->point_List.size());
}

cGeo_Calc::~cGeo_Calc()
{
}

bool cGeo_Calc::crossing()
{
	// TODO : Complete this yourself.
	
	sLine AB;
	sLine CD;
	
	for(int a = 0;a < this->point_List.size()-3;a++)
	{
		AB.A.x = this->point_List[a].x;
		AB.A.y = this->point_List[a].y;
		
		AB.B.x = this->point_List[a+1].x;
		AB.B.y = this->point_List[a+1].y;
		
		for(int b = a+3;b < this->point_List.size()-1;b++)
		{
			CD.A.x = this->point_List[b].x;
			CD.A.y = this->point_List[b].y;
			
			CD.B.x = this->point_List[b+1].x;
			CD.B.y = this->point_List[b+1].y;
			
			if(this->line_Inter(AB, CD))
				return false;
		}
	}
	
	return true;
}

bool cGeo_Calc::clock_Wise()
{
	printf("STATUS : ");
	
	if(!this->crossing())
	{
		printf("ERROR IN DATA, lines cross.\n");
		return false;
	}
	
	// TODO : Complete this yourself.
	double ang = 0;

	for(int a = 0;a < this->point_List.size()-2;a++)
	{
		ang += this->angle(&this->point_List[a], &this->point_List[a+1], &this->point_List[a+2]);
	}

	ang += this->angle(&this->point_List[this->point_List.size()-2], &this->point_List[0], &this->point_List[1]);

	if(ang < 0)
		return true;

	return false;
}

////// test bed //////

void test_Bed()
{

	vector<sVec2> temp;
	sVec2 v;

	v.x = 0;
	v.y = 0;

	
	for(int a = 0;a <= 1000;a++)
	{
		v.x = 1000*cos(360*((double)a/1000)/180*3.141592653589793);
		v.y = 1000*sin(360*((double)a/1000)/180*3.141592653589793);
		temp.push_back(v);
	}
	
	
	cGeo_Calc *test = new cGeo_Calc(temp);
	if(test->clock_Wise())
	{
		printf("Successful, data is anti clock wise.\n\n");
	}else
	{
		printf("Failure, data is clock wise.\n\n");
	}


	delete test;
}

////// done bed //////

int main (int argc, char * const argv[])
{
	printf("Start.\n");
	test_Bed();
	printf("End.\n");
	return 0;
}

Re: real world challenge

Posted: Tue Mar 31, 2009 10:23 pm
by MarauderIIC
Didn't check forum for two days and look what happens. :P
All times are UTC-06:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited