//-------------------------------------------------------------------------
// A 2d point, for positions
//-------------------------------------------------------------------------
struct fPoint {
	float x;
	float y;
};

// -----------------------------------------------------------------------------------------
// Get the area of a triangle
// -----------------------------------------------------------------------------------------
int AreaOfTriangle(fPoint p1, fPoint p2, fPoint p3) 
{
	return abs((p2.x * p1.y - p1.x * p2.y) + (p3.x * p2.y - p2.x * p3.y) + (p1.x * p3.y - p2.x * p1.y)) / 2
}

// -----------------------------------------------------------------------------------------
// Get a random point inside a triangle
// -----------------------------------------------------------------------------------------
fPoint RandInTriangle(fPoint p1, fPoint p2, fPoint p3) 
{
	fPoint thispoint;
	double a = 1.0;
	double b = 1.0;
	while (a+b>1) { a=rand(); b=rand(); }
	double c = 1 - a - b;
	thispoint.x = (p1.x*a)+(p2.x*b)+(p3.x*c);
	thispoint.y = (p1.y*a)+(p2.y*b)+(p3.y*c);
	return thispoint;
}

// -----------------------------------------------------------------------------------------
// Get a random point inside a polygon
// -----------------------------------------------------------------------------------------
fPoint RandInPoly(fPoint p[], int pcount) 
{
	int tval = 0;
	int tnum = 0;
	int totalarea = 0;
	int areas[pcount-1];

	for(int i=0; i<pcount-2; i++) {
		totalarea += AreaOfTriangle(p[0], p[i+1], p[i+2]);
		areas[i+1] = totalarea;
	}
	tval = rand() * totalarea / RAND_MAX;
	for (tnum=1; tnum<pcount-1; tnum++) { if(tval<=areas[tnum]&&tval>areas[tnum-1]) break; }

	return RandInTriangle(p[0], p[tnum], p[tnum+1]);
}