// Point
function Point(_x, _y) {
	this.x = _x;
	this.y = _y;
}

// Returns true if point is inside polygon
function isPointInPolygon(polygon, pt){
	for(var c = false, i = -1, l = polygon.length, j = l - 1; ++i < l; j = i)
		((polygon[i].y <= pt.y && pt.y < polygon[j].y) || (polygon[j].y <= pt.y && pt.y < polygon[i].y))
		&& (pt.x < (polygon[j].x - polygon[i].x) * (pt.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)
		&& (c = !c);
	return c;
}

// Smoothen polygon
// http://www.antigrain.com/research/bezier_interpolation/
function smoothenPolygon(polygon) {
	for (var i = 1; i < polygon.length - 2; i += 3) {
		addControlPoints(polygon, i);
	}
	//TODO: approximation with a cubic Bezier curve
}

// Add smoothen control points
function addControlPoints(polygon, index) {
	if(index < 1 || index + 2 > polygon.length) {
		return;
	}
	// Smooth value between 0 and 1
	var smooth_value = 0.5;

	var p0 = polygon[index - 1];
	var p1 = polygon[index];
	var p2 = polygon[index + 1];
	var p3 = polygon[index + 2];

	var xc1 = (p0.x + p1.x) / 2.0;
    var yc1 = (p0.y + p1.y) / 2.0;
    var xc2 = (p1.x + p2.x) / 2.0;
    var yc2 = (p1.y + p2.y) / 2.0;
    var xc3 = (p2.x + p3.x) / 2.0;
    var yc3 = (p2.y + p3.y) / 2.0;

    var len1 = Math.sqrt((p1.x - p0.x) * (p1.x - p0.x) + (p1.y - p0.y) * (p1.y - p0.y));
    var len2 = Math.sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
    var len3 = Math.sqrt((p3.x - p2.x) * (p3.x - p2.x) + (p3.y - p2.y) * (p3.y - p2.y));

    var k1 = len1 / (len1 + len2);
    var k2 = len2 / (len2 + len3);

    var xm1 = xc1 + (xc2 - xc1) * k1;
    var ym1 = yc1 + (yc2 - yc1) * k1;

    var xm2 = xc2 + (xc3 - xc2) * k2;
    var ym2 = yc2 + (yc3 - yc2) * k2;

    ctrl1_x = xm1 + (xc2 - xm1) * smooth_value + p1.x - xm1;
    ctrl1_y = ym1 + (yc2 - ym1) * smooth_value + p1.y - ym1;

    ctrl2_x = xm2 + (xc2 - xm2) * smooth_value + p2.x - xm2;
    ctrl2_y = ym2 + (yc2 - ym2) * smooth_value + p2.y - ym2;
    
	polygon.splice(index + 1, 0, new Point(ctrl2_x, ctrl2_y));
	polygon.splice(index + 1, 0, new Point(ctrl1_x, ctrl1_y));
}