/**
 * @file mapmath.js
 * @version 20190415 ms
 * @type JS
 */

/**
 * @class KExtent
 * @params xmin,ymin,xmax,ymax
 */
function KExtent(xmin,ymin,xmax,ymax){
	this.isNull=ymin===undefined;
	this.xmin=this.isNull?0:xmin;
	this.ymin=this.isNull?0:ymin;
	this.xmax=this.isNull?0:xmax===undefined?xmin:xmax;
	this.ymax=this.isNull?0:ymax===undefined?ymin:ymax;
}
KExtent.prototype.toShape=function(precision){
	if(precision===undefined) precision=0;
	var line=new KLine();
	line.points.push(new KPoint(this.xmin,this.ymin));
	line.points.push(new KPoint(this.xmax,this.ymin));
	line.points.push(new KPoint(this.xmax,this.ymax));
	line.points.push(new KPoint(this.xmin,this.ymax));
	line.points.push(new KPoint(this.xmin,this.ymin));
	var shp=new KShape(KShape.stPolygon);
	shp.precision=precision;
	shp.lines.push(line);
	return shp;
};
KExtent.prototype.expand=function(ext){
	var expanded=false;
	if(!ext.isNull){
		if(this.isNull){
			this.xmin=ext.xmin;this.ymin=ext.ymin;this.xmax=ext.xmax;this.ymax=ext.ymax;this.isNull=false;expanded=true;
		}else{
			if(ext.xmin<this.xmin){this.xmin=ext.xmin;expanded=true;}
			if(ext.ymin<this.ymin){this.ymin=ext.ymin;expanded=true;}
			if(ext.xmax>this.xmax){this.xmax=ext.xmax;expanded=true;}
			if(ext.ymax>this.ymax){this.ymax=ext.ymax;expanded=true;}
		}
	}
	return expanded;
};
KExtent.prototype.reset=function(){
	this.isNull=true;
	this.xmin=0;
	this.ymin=0;
	this.xmax=0;
	this.ymax=0;
};
KExtent.prototype.overlaps=function(ext){
	return this.xmin<=ext.xmax && this.xmax>=ext.xmin && this.ymin<=ext.ymax && this.ymax>=ext.ymin;
};

/**
 * @class KPoint
 * @constructor
 * @params x,y
 */
function KPoint(x,y){
	this.x=x;this.y=y;
}
KPoint.prototype.clone=function(){
	return new KPoint(this.x,this.y);
};
KPoint.prototype.set=function(x,y){
	this.x=x;this.y=y;
};
KPoint.prototype.equals=function(other){
	return this.x==other.x && this.y==other.y;
};
KPoint.prototype.extent=function(){
	return new KExtent(this.x,this.y,this.x,this.y);
};
KPoint.prototype.snapToGrid=function(sizeX,sizeY){
	if(sizeY===undefined) sizeY=sizeX;
	return new KPoint(Math.round(this.x/sizeX)*sizeX,Math.round(this.y/sizeY)*sizeY);
};
KPoint.prototype.distanceToPoint=function(pt){
	var dX=pt.x-this.x,dY=pt.y-this.y;
	return Math.sqrt(dX*dX+dY*dY);
};
KPoint.prototype.distanceToLine=function(lineA,lineB){
	var x12=lineB.x-lineA.x,y12=lineB.y-lineA.y,x13=this.x-lineA.x,y13=this.y-lineA.y;
	var d12=Math.sqrt(x12*x12+y12*y12);if(d12==0) return Math.sqrt(x13*x13+y13*y13);
	var pp=(x12*x13+y12*y13)/d12;
	if(pp<0)
		return Math.sqrt(x13*x13+y13*y13);
	else if(pp>d12){
		var x23=this.x-lineB.x,y23=this.y-lineB.y;
		return Math.sqrt(x23*x23+y23*y23);
	}else
		return Math.abs((x12*y13-y12*x13)/d12);
};
KPoint.prototype.isOnLine=function(lineA,lineB){
	// TODO (mapmath.js) reduce precision to float
	return ((this.x-lineB.x)*(lineA.y-lineB.y))==((this.y-lineB.y)*(lineA.x-lineB.x)) && this.x>=Math.min(lineA.x,lineB.x) && this.x<=Math.max(lineA.x,lineB.x) && this.y>=Math.min(lineA.y,lineB.y) && this.y<=Math.max(lineA.y,lineB.y);
};

/**
 * @class KLine
 * @constructor
 */
function KLine(){
	this.points=[];
	this.outerRing=-1;
}
KLine.prototype.clone=function(){
	var n=new KLine();
	for(var a=0;a<this.points.length;a++) n.points.push(this.points[a].clone());
	return n;
};
KLine.prototype.extent=function(){
	var e=new KExtent();
	for(var a=0;a<this.points.length;a++) e.expand(this.points[a].extent());
	return e;
};
KLine.prototype.length=function(){
	var l=0;
	for(var a=0;a<this.points.length-1;a++){
		var dX=this.points[a+1].x-this.points[a].x,dY=this.points[a+1].y-this.points[a].y;
		l+=Math.sqrt(dX*dX+dY*dY);
	}
	return l;
};
KLine.prototype.interpolatePoint=function(fraction){
	return this.interpolatePointMetric(fraction*this.length());
};
KLine.prototype.interpolatePointMetric=function(offset){
	var pos=0;
	for(var a=0;a<this.points.length-1;a++){
		var p1=this.points[a],p2=this.points[a+1];
		var dx=p2.x-p1.x,dy=p2.y-p1.y;
		var d=Math.sqrt(dx*dx+dy*dy);
		if(d!=0){
			var cc=(offset-pos)/d;
			if(pos+d>=offset) return new KPoint(p1.x+dx*cc,p1.y+dy*cc);
			pos+=d;
		}
	}
	return null;
};
KLine.prototype.flip=function(){
	for(var a=0;a<=Math.floor((this.points.length-2)/2);a++){
		var pt=this.points[a];
		this.points[a]=this.points[this.points.length-1-a];
		this.points[this.points.length-1-a]=pt;
	}
};
KLine.prototype.closePath=function(){
	if(this.points[0].x!=this.points[this.points.length-1].x || this.points[0].y!=this.points[this.points.length-1].y) this.points.push(this.points[0].clone());
};
KLine.prototype.getInteriorAngle=function(p,s1,s2){
	var d9=p.x-s2.x,d10=p.y-s2.y,d11=s1.x-p.x,d12=s1.y-p.y;
	var d6=d9*d11+d10*d12;
	var d8=(d9*d9+d10*d10)*(d11*d11+d12*d12);if(d8==0) return 0;
	d6=-d6/Math.sqrt(d8);
	if(d6>=1) return 0;
	if(d6<=-1) return Math.PI;
	var d7=Math.acos(d6);
	if((d9*d12-d10*d11)>0) return d7;else return Math.PI*2-d7;
};
KLine.prototype.isHole=function(){
	var lastPt;
	if(this.points[0].equals(this.points[this.points.length-1])){	// ring is closed
		if(this.points.length<4) return false;
		lastPt=this.points.length-2;
	}else{	// ring is NOT closed
		if(this.points.length<3) return false;
		lastPt=this.points.length-1;
	}
	var ang=this.getInteriorAngle(this.points[lastPt],this.points[lastPt-1],this.points[0]);
	var interiorAng=ang;
	var exteriorAng=Math.PI*2-ang;
	var ang=this.getInteriorAngle(this.points[0],this.points[lastPt],this.points[1]);
	interiorAng+=ang;
	exteriorAng+=Math.PI*2-ang;
	for(var j=0;j<lastPt-1;j++){
		ang=this.getInteriorAngle(this.points[j+1],this.points[j],this.points[j+2]);
		interiorAng+=ang;
		exteriorAng+=Math.PI*2-ang;
	}
	return interiorAng>exteriorAng;
};
KLine.prototype.snapToGrid=function(sizeX,sizeY){
	var n=[];
	var last=null;
	for(var a=0;a<this.points.length;a++){
		var pt=this.points[a].snapToGrid(sizeX,sizeY);
		if(last===null || !pt.equals(last)){
			n.push(pt);
			last=pt;
		}
	}
	this.points=n;
};
KLine.prototype.generalize=function(tolerance){
	var succ=false,killNum=0,killed=new Array(this.points.length);
	for(var a=1;a<this.points.length-1;a++){
		// 1. gehe zurück zum letzten nicht gelöschten Punkt
		var aStart=a-1;while(killed[aStart]) aStart--;
		var aEnd=a+1;
		// 2. prüfe alle gelöschten Punkte, ob sie von der neuen Kante zu weit weg sind
		var killable=true;
		for(var b=aStart+1;b<aEnd;b++) if(this.points[b].distanceToLine(this.points[aStart],this.points[aEnd])>tolerance){killable=false;break};
		if(killable){killed[a]=true;succ=true};
	}
	if(succ){
		var n=[];
		for(var a=0;a<this.points.length;a++) if(!killed[a]) n.push(this.points[a]); else killNum++;
		this.points=n;
	}
	return killNum;
};
KLine.prototype.distanceToPoint=function(pt){
	var closest=Number.MAX_VALUE,d;
	for(var a=0;a<this.points.length-1;a++){
		var x12=this.points[a+1].x-this.points[a].x,y12=this.points[a+1].y-this.points[a].y,x13=pt.x-this.points[a].x;y13=pt.y-this.points[a].y;
		var d12=Math.sqrt(x12*x12+y12*y12);
		if(d12!=0){
			var pp=(x12*x13+y12*y13)/d12;
			if(pp<0)
				d=Math.sqrt(x13*x13+y13*y13);
			else if(pp>d12){
				var x23=pt.x-this.points[a+1].x,y23=pt.y-this.points[a+1].y;
				d=Math.sqrt(x23*x23+y23*y23);
			}else
				d=Math.abs((x12*y13-y12*x13)/d12);
			if(d<closest){if(d==0) return 0;else closest=d};
		}
	}
	return closest;
};
KLine.prototype.intersectsPoint=function(pt) {
	for(var a=0;a<this.points.length-1;a++)
		if(pt.isOnLine(this.points[a],this.points[a+1])) return true;
	return false;
};
KLine.prototype.intersectsLine=function(line){
	for(var a=0;a<this.points.length-1;a++)
	   for(var b=0;b<line.points.length-1;b++)
		   if(KLinesIntersect(this.points[a],this.points[a+1],line.points[b],line.points[b+1])==1) return true;
	return false;
};

/**
 * @class KShape
 * @constructor
 */
function KShape(type){
	this.type=type;
	this.meExtent=new KExtent();
	this.lines=[];
	this.mapped=false;
	this.precision=0;
}
KShape.stNull=0;
KShape.stPoint=1;
KShape.stLine=3;
KShape.stPolygon=5;

KShape.createFromKShp=function(kshp,precision){
	var shp;
	if(kshp.type==1){
		shp=new KShape(KShape.stPoint);
		var line=new KLine();
		line.points.push(new KPoint(shp.pt[0],shp.pt[1]));
		shp.lines.push(line);
	}else if(kshp.type>1){
		shp=new KShape(kshp.type==2?KShape.stLine:KShape.stPolygon);
		for(var a=0;a<kshp.pts.length;a++){
			var line=new KLine();
			for(var b=0;b<kshp.pts[a].length;b++) line.points.push(new KPoint(kshp.pts[a][b][0],kshp.pts[a][b][1]));
			shp.lines.push(line);
		}
	}else shp=new KShape(KShape.stNull);
	shp.precision=precision===undefined?0:precision;
	return shp;
};
KShape.createFromWkt=function(wkt,precision){
	var shp;
	wkt=wkt.replace(/\s\(/g,"(");
	var i=wkt.indexOf("(");
	var body=wkt.substr(i+1,wkt.length-i-2);
	switch(wkt.substr(0,i)){
	case "POINT":
		shp=new KShape(KShape.stPoint);
		KShape.createFromWktAddPart(body,shp);
		break;
	case "LINESTRING":
		shp=new KShape(KShape.stLine);
		KShape.createFromWktAddPart(body,shp);
		break;
	case "MULTILINESTRING":
		shp=new KShape(KShape.stLine);
		var parts=body.substr(1,body.length-2).split("),(");for(var a=0;a<parts.length;a++) KShape.createFromWktAddPart(parts[a],shp);
		break;
	case "POLYGON":
		shp=new KShape(KShape.stPolygon);
		var parts=body.substr(1,body.length-2).split("),(");for(var a=0;a<parts.length;a++) KShape.createFromWktAddPart(parts[a],shp);
		break;
	case "MULTIPOLYGON":
		shp=new KShape(KShape.stPolygon);
		var polygons=body.substr(2,body.length-4).split(")),((");
		for(var b=0;b<polygons.length;b++){var parts=polygons[b].split("),(");for(var a=0;a<parts.length;a++) KShape.createFromWktAddPart(parts[a],shp)};
		break;
	}
	shp.precision=precision===undefined?0:precision;
	return shp;
};
KShape.createFromWktAddPart=function(s,shp){
	var line=new KLine();
	var pts=s.split(",");
	for(var a=0;a<pts.length;a++){var pt=pts[a].split(" ");line.points.push(new KPoint(parseFloat(pt[0]),parseFloat(pt[1])))};
	shp.lines.push(line);
};

KShape.parseXML=function(gml){
	if(typeof gml=='string' || gml instanceof String){
		var p=new DOMParser(),g,errm;
		try{g=p.parseFromString(gml.replace(/gml:/g,""),"text/xml");}catch(e){};
		if(g.parseError && g.parseError.errorCode){
			errm="XML Parsing Error: "+g.parseError.reason+" at line "+g.parseError.line+" at position "+g.parseError.linepos;
		}else{
			if(g.documentElement){if(g.documentElement.nodeName=="parsererror") errm=g.documentElement.childNodes[0].nodeValue;}else errm="XML Parsing Error!";
		}
		if(errm){alert(errm);return null;}
		return g;
	}
	return gml;
};

KShape.createFromGml=function(gml,precision){
	var g=KShape.parseXML(gml);
	if(!g) return null;
	var shp;
	switch(g.firstChild.nodeName){
		case "Point":shp=new KShape(KShape.stPoint);break;
		case "Curve":case "MultiCurve":shp=new KShape(KShape.stLine);break;
		case "Polygon":case "MultiSurface":shp=new KShape(KShape.stPolygon);break;
		default:alert("Unknown GML type '"+g.nodeName+"'");return null;
	}
	if(shp.type==KShape.stPoint){
		var l=g.getElementsByTagName("pos");
		if(l.length){
			var c=l[0].childNodes[0].nodeValue.split(" ");
			var line=new KLine();
			line.points.push(new KPoint(Number(c[0]),Number(c[1])));
			shp.lines.push(line);
		}
	}else{
		var l=g.getElementsByTagName("posList");
		for(var a=0;a<l.length;a++){
			var line=new KLine();
			var c=l[a].childNodes[0].nodeValue.split(" ");
			for(var b=0;b<c.length;b+=2) line.points.push(new KPoint(Number(c[b]),Number(c[b+1])));
			shp.lines.push(line);
		}
	}
	shp.precision=precision===undefined?0:precision;
	return shp;
};

KShape.createFromCgf=function(arrayBuffer,byteOrderBig,type,precision){
	var mf=new MemoryFile(arrayBuffer,byteOrderBig);
	if(type===undefined){
		var header=mf.readByte();
		type=header & 15;
		precision=header >> 4;
	}
	var shape,fac=Math.pow(10,precision);
	switch(type){
	case 1:
		shape=new KShape(KShape.stPoint);
		shape.precision=precision;
		var line=new KLine();
		var x=mf.readInt32();var y=mf.readInt32();
		x/=fac;y/=fac;
		line.points.push(new KPoint(x,y));
		shape.lines.push(line);
		break;
	case 2:
		shape=new KShape(KShape.stLine);
		shape.precision=precision;
		shape.lines.push(KShape.createFromCgfDecodeLine(mf,fac,false,-2));
		break;
	case 3:
	case 4:
		shape=new KShape(type==3?KShape.stLine:KShape.stPolygon);
		if(type==4) shape.mapped=true;
		shape.precision=precision;
		var a=0;
		while(!mf.eof()){
			shape.lines.push(KShape.createFromCgfDecodeLine(mf,fac,shape.type==KShape.stPolygon));
			if(type==4 && a!=0) shape.lines[shape.lines.length-1].outerRing=0;
			a++;
		}
		break;
	case 5:
		shape=new KShape(KShape.stPolygon);
		shape.mapped=true;
		shape.precision=precision;
		while(!mf.eof()) {
			var numLines=mf.readUIntVarlen();
			var outerIndex=shape.lines.length;
			for(var a=0;a<numLines;a++){
				shape.lines.push(KShape.createFromCgfDecodeLine(mf,fac,true));
				if(outerIndex!=shape.lines.length-1) shape.lines[shape.lines.length-1].outerRing=outerIndex;
			}
		}
		break;
	default:
		shape=new KShape(KShape.stNull);
	}
	return shape;
};
KShape.createFromCgfDecodeLine=function(mf,fac,closePath,numPoints){
	if(numPoints===undefined) numPoints=mf.readUIntVarlen();
	var line=new KLine();
	var x=mf.readInt32();
	var y=mf.readInt32();
	line.points.push(new KPoint(x/fac,y/fac));
	for(var a=1;a<numPoints || (numPoints==-2 && !mf.eof());a++){
		x+=mf.readIntVarlen();y+=mf.readIntVarlen();
		line.points.push(new KPoint(x/fac,y/fac));
	}
	if(closePath) line.points.push(line.points[0].clone());
	return line;
};

KShape.prototype.clone=function(){
	var n=new KShape(this.type);
	n.precision=this.precision;
	for(var a=0;a<this.lines.length;a++) n.lines.push(this.lines[a].clone());
	return n;
};

KShape.prototype.extent=function(){
	if(this.meExtent.isNull) for(var a=0;a<this.lines.length;a++) this.meExtent.expand(this.lines[a].extent());
	return this.meExtent;
};
KShape.prototype.resetExtent=function(){
	this.meExtent.reset();
};
KShape.prototype.length=function(){
	var l=0;
	for(var a=0;this.lines.length;a++) l+=this.lines[a].length();
	return l;
};
KShape.prototype.area=function(){
	var area=0;
	for(var a=0;a<this.lines.length;a++)
		for(var b=0;b<this.lines[a].points.length-1;b++)
			area+=this.lines[a].points[0].x*this.lines[a].points[b].y-this.lines[a].points[0].y*this.lines[a].points[b].x+this.lines[a].points[0].y*this.lines[a].points[b+1].x-this.lines[a].points[0].x*this.lines[a].points[b+1].y+this.lines[a].points[b].x*this.lines[a].points[b+1].y-this.lines[a].points[b+1].x*this.lines[a].points[b].y;
	return -area/2;
};
KShape.prototype.snapToGrid=function(sizeX,sizeY){
	for(var a=this.lines.length-1;a>=0;a--){
		this.lines[a].snapToGrid(sizeX,sizeY);
		if((this.type==KShape.stPolygon && this.lines[a].points.length<4) || (this.type==KShape.stLine && this.lines[a].points.length<2)){
			if(this.lines.length==1){
				if(this.lines[0].points.length==0)
					this.type=KShape.stNull;
				else if(this.lines[0].points.length==1)
					this.type=KShape.stPoint;
				else
					this.type=KShape.stLine;
			}else
				this.lines.splice(a,1);
		}
	}
};
KShape.prototype.generalize=function(tolerance){
	for(var a=this.lines.length-1;a>=0;a--){
		this.lines[a].generalize(tolerance);
		if((this.type==KShape.stPolygon && this.lines[a].points.length<4) || (this.type==KShape.stLine && this.lines[a].points.length<2)){
			if(this.lines.length==1){
				if(this.lines[0].points.length==0)
					this.type=KShape.stNull;
				else if(this.lines[0].points.length==1)
					this.type=KShape.stPoint;
				else
					this.type=KShape.stLine;
			}else
				this.lines.splice(a,1);
		}
	}
};
KShape.prototype.distanceToPoint=function(pt,inPart){
	if(this.type==KShape.stNull) return Number.MAX_VALUE;
	else if(this.type==KShape.stPoint) return this.lines[0].points[0].distanceToPoint(pt);
	else if(this.type==KShape.stPolygon && this.intersectsPoint(pt,inPart)!=0) return 0;
	var closest=Number.MAX_VALUE;
	for(var a=0;a<this.lines.length;a++){
		if(inPart===undefined || inPart==a){
			var d=this.lines[a].distanceToPoint(pt);
			if(d<closest){if(d==0) return 0;else closest=d};
		}
	}
	return closest;
};
KShape.prototype.distanceToShape=function(shape,inPart){
	if(this.type==KShape.stNull) return Number.MAX_VALUE;
	if(this.type==KShape.stPoint) return shape.distanceToPoint(this.lines[0].points[0]);
	if(shape.type==KShape.stPoint) return this.distanceToPoint(shape.lines[0].points[0]);
	// for (filled) polygon check if points of the other poly are inside the polygon
	if((this.type==KShape.stPolygon || shape.type==KShape.stPolygon) && this.intersectsShape(shape,inPart)) return 0;
	// main routine:
	var closest=Number.MAX_VALUE;
	for(var a=0;a<this.lines.length;a++){
		if(inPart===undefined || inPart==a){
			var lineA=this.lines[a].points;
			for(var aa=0;aa<lineA.length-1;aa++){
				if(!lineA[aa].equals(lineA[aa+1])){
					for(var b=0;b<shape.lines.length;b++){
						var lineB=shape.lines[b].points;
						for(var bb=0;bb<lineB.length-1;bb++){
							if(!lineB[bb].equals(lineB[bb+1])){
								var d=KDistanceLineToLine(lineA[aa],lineA[aa+1],lineB[bb],lineB[bb+1]);
								if(d<closest){if(d==0) return 0;else closest=d};
							}
						}
					}
				}
			}
		}
	}
	return closest;
};
// Result values: 0=false, 1=on border line, 2=in polygon
KShape.prototype.intersectsPoint=function(pt,inPart){
	if(this.type!=KShape.stPolygon) return 0;
	var ext=this.extent();
	if(pt.x<ext.xmin || pt.x>ext.xmax || pt.y<ext.ymin || pt.y>ext.ymax) return 0;
	for(var a=0;a<this.lines.length;a++) if(inPart===undefined || inPart==a) if(this.lines[a].intersectsPoint(pt)) return 1;
	var result=false;
	if(inPart!==undefined && this.lines[inPart].isHole()) result=true;
	// Y scan:
	for(var a=0;a<this.lines.length;a++)
		if(inPart===undefined || inPart==a)
			for(var b=0;b<this.lines[a].points.length-1;b++)
				if((this.lines[a].points[b+1].y<=pt.y && pt.y<this.lines[a].points[b].y) || (this.lines[a].points[b].y<=pt.y && pt.y<this.lines[a].points[b+1].y))
					if(pt.x<(this.lines[a].points[b].x-this.lines[a].points[b+1].x)*(pt.y-this.lines[a].points[b+1].y)/(this.lines[a].points[b].y-this.lines[a].points[b+1].y)+this.lines[a].points[b+1].x)
						result=!result;
	return result?2:0;
};
KShape.prototype.intersectsShape=function(shape,inPart){
	if(this.type!=KShape.stNull && shape.type!=KShape.stNull && this.extent().overlaps(shape.extent())){
		for(var part1=0;part1<this.lines.length;part1++)
			if(inPart===undefined || inPart==part1)
				for(part2=0;part2<shape.lines.length;part2++)
					if(this.lines[part1].intersectsLine(shape.lines[part2])) return true;
		// If no line intersection was detected, check if one Poly lays completly within the other:
		if(this.type==KShape.stPolygon) {
			if(shape.type==KShape.stPoint)
				return this.intersectsPoint(shape.lines[0].points[0],inPart)!=0;
			else
				return this.intersectsShapeTest(shape,inPart);
		}
		if(shape.type==KShape.stPolygon){
			if(this.type==KShape.stPoint){
				return shape.intersectsPoint(this.lines[0].points[0])!=0;
			}else{
				if(inPart===undefined)
					return shape.intersectsShapeTest(this);
				else
					return shape.intersectsShapeTest2(this.lines[inPart]);
			}
		}
	}
	return false;
};
KShape.prototype.intersectsShapeTest2=function(line,inPart){
	for(var a=0;a<line.points.length-1;a++){
		switch(this.intersectsPoint(line.points[a],inPart)){
			case 0:return false;
			case 2:return true;
		}
	}
	return false;
};
KShape.prototype.intersectsShapeTest=function(innerPoly,inPart){
	for(var a=0;a<innerPoly.lines.length;a++)
		if(this.intersectsShapeTest2(innerPoly.lines[a],inPart)) return true;
	return false;
};
KShape.prototype.containsShape2=function(line,inPart){
	if(this.type!=KShape.stPolygon) return false;
	for(var a=0;a<line.points.length-1;a++)
		if(this.intersectsPoint(line.points[a],inPart)==0) return false;
	return true;
};
KShape.prototype.containsShape=function(shape,inPart){
	if(this.type!=KShape.stPolygon) return false;
	for(var a=0;a<shape.lines.length;a++)
		if(!this.containsShape2(shape.lines[a],inPart)) return false;
	return true;
};
KShape.prototype.mapOuterRings=function(){
	this.mapped=true;
	if(this.lines.length==1){this.lines[0].outerRing=-1;return};
	var polys=[],isHole=[],inside=[],outers=[];
	for(var a=0;a<this.lines.length;a++){
		var poly=new KShape(KShape.stPolygon);
		poly.lines.push(this.lines[a].clone());
		polys.push(poly);
		isHole.push(polys[a].lines[0].isHole());
		if(isHole[a]) polys[a].lines[0].flip();
	}
	for(var a=0;a<polys.length;a++){
		inside.push(0);
		outers.push([]);
		for(var b=0;b<polys.length;b++)
			if(a!=b && polys[b].containsShape(polys[a])){inside[a]++;outers[a].push(b)};
	}
	for(var a=0;a<polys.length;a++){
		if(inside[a] % 2==0){	// alle äußeren Ringe
			this.lines[a].outerRing=-1;
			if(isHole[a]) this.lines[a].flip();
		}else{	// alle inneren Ringe
			for(var b=0;b<outers[a].length;b++){
				if(inside[outers[a][b]]==inside[a]-1) {	// dem äußeren Ring als Loch zuordnen
					this.lines[a].outerRing=outers[a][b];
					if(!isHole[a]) this.lines[a].flip();
					break;
				}
			}
		}
	}
};

KShape.prototype.toKShp=function(){
	var me=this.cloneForExport();
	var kshp={};
	if(me.type==KShape.stPoint){
		if(me.lines.length && me.lines[0].points.length){
			kshp.type=1;
			kshp.pt=[me.lines[0].points[0].x,me.lines[0].points[0].y];
		}
	}else if(me.type==KShape.stLine || me.type==KShape.stPolygon){
		kshp.type=me.type==KShape.stLine?2:3;
		kshp.pts=[];
		for(var a=0;a<me.lines.length;a++){
			var line=[];
			for(var b=0;b<me.lines[a].points.length;b++) line.push([me.lines[a].points[b].x,me.lines[a].points[b].y]);
			kshp.pts.push(line);
		}
	}
	return kshp;
};
KShape.prototype.toWkt=function(precision){
	var me=this.cloneForExport(precision);
	switch(me.type){
	case KShape.stNull:
		return null;break;
	case KShape.stPoint:
		return me.lines[0].points.length?"POINT("+me.lines[0].points[0].x+" "+me.lines[0].points[0].y+")":null;break;
	case KShape.stLine:
		var outLines=[];
		for(var a=0;a<me.lines.length;a++){
			var pts=[];
			for(var b=0;b<me.lines[a].points.length;b++) pts.push(me.lines[a].points[b].x+" "+me.lines[a].points[b].y);
			outLines.push("("+pts.join(",")+")");
		}
		if(outLines.length==1)
			return "LINESTRING"+outLines[0];
		else
			return "MULTILINESTRING("+outLines.join(",")+")";
		break;
	case KShape.stPolygon:
		if(!me.mapped) me.mapOuterRings();
		var polys=[];
		for(var a=0;a<me.lines.length;a++){
			if(me.lines[a].outerRing==-1){
				var poly=[a];
				for(var b=0;b<me.lines.length;b++)
					if(me.lines[b].outerRing==a) poly.push(b);
				polys.push(poly);
			}
		}
		var outParts=[];
		for(var a=0;a<polys.length;a++){
			var outLines=[];
			for(var b=0;b<polys[a].length;b++){
				var line=polys[a][b],pts=[];
				for(var c=0;c<me.lines[line].points.length;c++) pts.push(me.lines[line].points[c].x+" "+me.lines[line].points[c].y);
				outLines.push("("+pts.join(",")+")");
			}
			outParts.push("("+outLines.join(",")+")");
		}
		if(outParts.length==1)
			return "POLYGON"+outParts[0];
		else if(outParts.length>1)
			return "MULTIPOLYGON("+outParts.join(",")+")";
		else
			return null;
		break;
	}
};
KShape.prototype.toGml=function(crs,precision){
	var me=this.cloneForExport(precision);
	switch(me.type){
	case KShape.stNull:
		return null;break;
	case KShape.stPoint:
		return me.lines[0].points.length?'<gml:Point srsName="'+crs+'"><gml:pos srsDimension="2">'+me.lines[0].points[0].x+' '+me.lines[0].points[0].y+'</gml:pos></gml:Point>':null;break;
	case KShape.stLine:
		var outLines=[];
		for(var a=0;a<me.lines.length;a++){
			var pts=[];
			for(var b=0;b<me.lines[a].points.length;b++) pts.push(me.lines[a].points[b].x+" "+me.lines[a].points[b].y);
			outLines.push((me.lines.length>1?"<gml:curveMember><gml:Curve>":"")+'<gml:segments><gml:LineStringSegment><gml:posList srsDimension="2">'+pts.join(" ")+"</gml:posList></gml:LineStringSegment></gml:segments>"+(me.lines.length>1?"</gml:Curve></gml:curveMember>":""));
		}
		if(outLines.length==1)
			return '<gml:Curve srsName="'+crs+'">'+outLines[0]+"</gml:Curve>";
		else
			return '<gml:MultiCurve srsName="'+crs+'">'+outLines.join("")+"</gml:MultiCurve>";
		break;
	case KShape.stPolygon:
		if(!me.mapped) me.mapOuterRings();
		var polys=[];
		for(var a=0;a<me.lines.length;a++){
			if(me.lines[a].outerRing==-1){
				var poly=[a];
				for(var b=0;b<me.lines.length;b++)
					if(me.lines[b].outerRing==a) poly.push(b);
				polys.push(poly);
			}
		}
		var outParts=[];
		for(var a=0;a<polys.length;a++){
			var outLines=[];
			for(var b=0;b<polys[a].length;b++){
				var line=polys[a][b],pts=[];
				for(var c=0;c<me.lines[line].points.length;c++) pts.push(me.lines[line].points[c].x+" "+me.lines[line].points[c].y);
				outLines.push((b?"<gml:interior>":"<gml:exterior>")+'<gml:LinearRing><gml:posList srsDimension="2">'+pts.join(" ")+"</gml:posList></gml:LinearRing>"+(b?"</gml:interior>":"</gml:exterior>"));
			}
			outParts.push((polys.length>1?"<gml:surfaceMember><gml:Polygon>":"")+outLines.join("")+(polys.length>1?"</gml:Polygon></gml:surfaceMember>":""));
		}
		if(polys.length==1)
			return '<gml:Polygon srsName="'+crs+'">'+outParts[0]+"</gml:Polygon>";
		else if(polys.length>1)
			return '<gml:MultiSurface srsName="'+crs+'">'+outParts.join("")+"</gml:MultiSurface>";
		else
			return null;
		break;
	}
};
KShape.prototype.cloneForExport=function(precision){
	var me=this.clone();
	if(me.lines.length==0) me.type==KShape.stNull;
	if(me.type==KShape.stPolygon) for(var a=0;a<me.lines.length;a++) me.lines[a].closePath();
	var fac=1/Math.pow(10,precision!=undefined?precision:me.precision);
	me.snapToGrid(fac,fac);
	me.generalize(Math.sqrt(fac/2));
	return me;
};

/**
 * @fn KDistanceLineToLine
 * @param LineA
 * @param LineB
 * @param Point
 * @returns {Array}
 */
function KDistanceLineToLine(LineA,LineB,Point){
	var x12=LineB[0]-LineA[0]; var y12=LineB[1]-LineA[1];
	var x13=Point[0]-LineA[0]; var y13=Point[1]-LineA[1];
	var d12=Math.sqrt(x12*x12+y12*y12);if(d12==0) return [Math.sqrt(x13*x13+y13*y13),LineA];
	var PP=(x12*x13+y12*y13)/d12;
	var NewPt=[LineA[0]+x12*PP/d12,LineA[1]+y12*PP/d12];
	if(PP<0)
		return [Math.sqrt(x13*x13+y13*y13),NewPt];
	else if(PP>d12){
		var x23=Point[0]-LineB[0];var y23=Point[1]-LineB[1];return [Math.sqrt(x23*x23+y23*y23),NewPt];
	}else
		return [Math.abs((x12*y13-y12*x13)/d12),NewPt];
}

/**
 * @fn KLinesIntersect
 * @param line1A
 * @param line1B
 * @param line2A
 * @param line2B
 * @returns {Number} 0 = no intersection, 1 = intersection detected, -1 = lines are parallel
 */
function KLinesIntersect(line1A,line1B,line2A,line2B){
	var rx=line1B.x-line1A.x;
	var ry=line1B.y-line1A.y;
	var sx=line2B.x-line2A.x;
	var sy=line2B.y-line2A.y;
	var det=sx*ry-sy*rx;
	if(det==0)	// lines are parallel
		return -1;
	else{
		var z=-(rx*(line1A.y-line2A.y)+ry*(line2A.x-line1A.x))/det;
		if(z<0 || z>1) return 0;	// when z=0 or z=1 intersection at end point!
		z=(sx*(line2A.y-line1A.y)+sy*(line1A.x-line2A.x))/det;
		if(z<0 || z>1) return 0; // when z=0 or z=1 intersection at end point!
		return 1;
	}
}

/**
 * @fn KLinesIntersectionPoint
 * @param line1A
 * @param line1B
 * @param line2A
 * @param line2B
 * @param intersectionPoint
 * @param snapTolerance
 * @param openEnds
 * @returns {Number} 0 = no intersection, 1 = intersection detected, -1 = lines are parallel
 */
function KLinesIntersectionPoint(line1A,line1B,line2A,line2B,intersectionPoint,snapTolerance,openEnds){
	var rx=line1B.x-line1A.x;
	var ry=line1B.y-line1A.y;
	var sx=line2B.x-line2A.x;
	var sy=line2B.y-line2A.y;
	var det=sx*ry-sy*rx;
	if(det==0)	// lines are parallel
		return -1;
	else{
		var z=-(rx*(line1A.y-line2A.y)+ry*(line2A.x-line1A.x))/det;
		if((z<0 || z>1) && !openEnds) return 0;	// when z=0 or z=1 intersection at end point!
		z=(sx*(line2A.y-line1A.y)+sy*(line1A.x-line2A.x))/det;
		if((z<0 || z>1) && !openEnds) return 0;	// when z=0 or  z=1 intersection at end point!
		if(snapTolerance===undefined) snapTolerance=0;
		if(Math.abs(z)<=snapTolerance)	// snap to start point
			intersectionPoint.set(line1A.x,line1A.y);
		else if(Math.abs(z-1)<=snapTolerance)	// snap to end point
			intersectionPoint.set(line1B.x,line1B.y);
		else
			intersectionPoint.set(line1A.x+z*rx,line1A.y+z*ry);
		return 1;
	}
}


/**
 * @class KMultiShape
 * @constructor
 */
function KMultiShape(){
	this.shapes=[];
}
KMultiShape.createFromWkt=function(wkt,precision){
	var ms=new KMultiShape();
	if(wkt.substr(0,18)=="GEOMETRYCOLLECTION"){
		var i=wkt.indexOf("(");
		wkt=wkt.substr(i+1,wkt.length-i-2);
		var stage=0,j=0;
		for(i=0;i<wkt.length;i++){
			var c=wkt.charAt(i);
			if(c=="(") stage++;else if(c==")") stage--;
			if(stage==0 && c==","){
				var shp=KShape.createFromWkt(wkt.substring(j,i),precision);
				if(shp) ms.shapes.push(shp);
				j=i+1;
			}
		}
	}else{
		var shp=KShape.createFromWkt(wkt,precision);
		if(shp) ms.shapes.push(shp);
	}
	return ms;
};
KMultiShape.createFromGml=function(gml,precision){
	var g=KShape.parseXML(gml);
	if(!g) return null;
	var ms=new KMultiShape();
	if(g.firstChild.nodeName=="MultiGeometry"){
		var l=g.getElementsByTagName("geometryMember");
		for(var a=0;a<l.length;a++){
			var shp=KShape.createFromGml(l[a],precision);
			if(shp) ms.shapes.push(shp);
		}
	}else{
		var shp=KShape.createFromGml(g,precision);
		if(shp) ms.shapes.push(shp);
	}
	return ms;
};
KMultiShape.prototype.toWkt=function(precision){
	if(this.shapes.length==1){
		return this.shapes[0].toWkt(precision);
	}else{
		var wkts=[];
		for(var a=0;a<this.shapes.length;a++) wkts.push(this.shapes[a].toWkt(precision));
		return "GEOMETRYCOLLECTION("+wkts.join(",")+")";
	}
};
KMultiShape.prototype.toGml=function(crs,precision){
	if(this.shapes.length==1){
		return this.shapes[0].toGml(crs,precision);
	}else{
		var gmls=[];
		for(var a=0;a<this.shapes.length;a++) gmls.push("<gml:geometryMember>"+this.shapes[a].toGml(crs,precision)+"</gml:geometryMember>");
		return '<gml:MultiGeometry srsName="'+crs+'">'+gmls.join("")+'</gml:MultiGeometry>';
	}
};