function SameSigns(a,b){
	return ((a^b)>0);
}

/* Line intersection algorithm. Author: Mukesh Prasad */
function IsLinesCross(x1, y1, x2, y2, x3, y3, x4, y4){
    var a1, a2, b1, b2, c1, c2;
    var r1, r2, r3, r4;

    a1 = y2-y1;
    b1 = x1-x2;
    c1 = x2*y1 - x1*y2;

    r3 = a1*x3 + b1*y3 + c1;
    r4 = a1*x4 + b1*y4 + c1;

    if(r3 && r4 && SameSigns(r3, r4))
		return false;

    a2 = y4-y3;
    b2 = x3-x4;
    c2 = x4*y3 - x3*y4;

    r1 = a2*x1 + b2*y1 + c2;
    r2 = a2*x2 + b2*y2 + c2;

    if(r1 && r2 && SameSigns(r1, r2))
		return false;

	var denom = a1*b2 - a2*b1;
    if(denom == 0)
        return false;
		
    var offset = denom<0 ? -denom/2 : denom/2;

	var num = b1*c2 - b2*c1;
	var x = Math.floor((num < 0 ? num-offset : num+offset) / denom);

    num = a2*c1 - a1*c2;
    var y = Math.floor((num < 0 ? num-offset : num+offset ) / denom);
	
    return new Point(x, y);
}

function IsBBoxCross(sh1, sh2){
	return (Math.min(sh1.x+sh1.w, sh2.x+sh2.w) > Math.max(sh1.x, sh2.x) && Math.max(sh1.y, sh2.y) < Math.min(sh1.y+sh1.h, sh2.y+sh2.h) )
}

function InsidePolygon(aPolygon, p){
	var counter = 0;
	var i, xinters, p1, p2, l;
	p1 = aPolygon[0];
	l=aPolygon.length;
	
	for (i=1;i<=l;i++){
		p2 = aPolygon[i % l];
		if(
			(p.y > Math.min(p1.y,p2.y)) && 
			(p.y <= Math.max(p1.y,p2.y)) && 
			(p.x <= Math.max(p1.x,p2.x)) && 
			(p1.y != p2.y)
		){
			xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
			if (p1.x == p2.x || p.x <= xinters)
				counter++;
		}
		p1 = p2;
	}

    return (counter%2 == 0) ? 0 : 1;
}

function IsOverlap(oEblock, oEraser){
	if(IsBBoxCross(oEblock.oShape, oEraser.oBBox)){
		var l=oEraser.oShape.length-1;
		var _sh=oEblock.oShape;
		var _esh=oEraser.oShape;
		var p1=_esh[l], p2=_esh[0];
		if(
			IsLinesCross(_sh.x,        _sh.y,        _sh.x+_sh.w,  _sh.y,          p1.x, p1.y, p2.x, p2.y) ||
			IsLinesCross(_sh.x+_sh.w,  _sh.y,        _sh.x+_sh.w,  _sh.y+_sh.h,    p1.x, p1.y, p2.x, p2.y) ||
			IsLinesCross(_sh.x,        _sh.y+_sh.h,  _sh.x+_sh.w,  _sh.y+_sh.h,    p1.x, p1.y, p2.x, p2.y) ||
			IsLinesCross(_sh.x,        _sh.y,        _sh.x,        _sh.y+_sh.h,    p1.x, p1.y, p2.x, p2.y)
		)
			return true;
		do{
			p1=_esh[l], p2=_esh[l-1];
			if(
				IsLinesCross(_sh.x,        _sh.y,        _sh.x+_sh.w,  _sh.y,          p1.x, p1.y, p2.x, p2.y) ||
				IsLinesCross(_sh.x+_sh.w,  _sh.y,        _sh.x+_sh.w,  _sh.y+_sh.h,    p1.x, p1.y, p2.x, p2.y) ||
				IsLinesCross(_sh.x,        _sh.y+_sh.h,  _sh.x+_sh.w,  _sh.y+_sh.h,    p1.x, p1.y, p2.x, p2.y) ||
				IsLinesCross(_sh.x,        _sh.y,        _sh.x,        _sh.y+_sh.h,    p1.x, p1.y, p2.x, p2.y)
			)
				return true;
		}while(--l)
	}
	return false;
}


function SortPoints(a, b){
	return a.x - b.x;
}