1 /**
  2  * lina.js
  3  *
  4  * Copyright (c) 2010-2011,  Martin Wendt (http://wwWendt.de)
  5  *
  6  * Dual licensed under the MIT or GPL Version 2 licenses.
  7  * http://code.google.com/p/arcade-js/wiki/LicenseInfo
  8  *
  9  * A current version and some documentation is available at
 10  *     http://arcade-js.googlecode.com/
 11  *
 12  * @fileOverview An independent object oriented library for points, vectors,
 13  * and homogeneous transformations in 2D space.
 14  * A polygon class helps with collision detection and hit testing.
 15  *
 16  * @author Martin Wendt
 17  * @version 0.0.1
 18  */
 19 /*jslint laxbreak: true */
 20 /*******************************************************************************
 21  * Tools
 22  */
 23 
 24 /**
 25  * @namespace Namespace for global constants and functions.
 26  */
 27 LinaJS = {
 28 	// var identity33 = [1, 0, 0, 0, 1, 0, 0, 0, 1];
 29 	/**
 30 	 * Factor that converts radians to degree (alias: R2D).
 31 	 *
 32 	 * @constant
 33 	 */
 34 	RAD_TO_DEG: 180.0 / Math.PI,
 35 	R2D: 180.0 / Math.PI,
 36 	/**
 37 	 * Factor that converts degree to radians (alias: D2R).
 38 	 * @constant
 39 	 */
 40 	DEG_TO_RAD: Math.PI / 180.0,
 41 	D2R: Math.PI / 180.0,
 42 	/** Default epsilon value use in some comparisons.
 43 	 * @constant
 44 	 */
 45 	EPS: 1e-5,
 46 	/** Squared LinaJS.EPS.
 47 	 * @constant
 48 	 */
 49 	EPS_SQUARED: 1e-5 * 1e-5,
 50 
 51 
 52 	/**Return random float value f, with min <= f <= max').
 53 	 * @example
 54 	 * random(10); // return 0.00 .. 10.00
 55 	 * random(2, 5); // return 2.00 .. 5.00
 56 	 */
 57 	random: function(min, max) {
 58 		if( max === undefined ){
 59 			max = min;
 60 			min = 0;
 61 		}
 62 		return min + (max-min) * Math.random();
 63 	},
 64 	/**Return random integer value i, with min <= i <= max').
 65 	 * @example
 66 	 * randomInt(10); // return 0..10
 67 	 * randomInt(2, 5); // return 2..5
 68 	 */
 69 	randomInt: function(min, max) {
 70 		if( max === undefined ){
 71 			max = min;
 72 			min = 0;
 73 		}
 74 		return min + Math.floor((max-min+1) * Math.random());
 75 	},
 76 	/**
 77 	 * Return angle from a1 to a2 normalized to [-Pi < a <= +Pi]
 78 	 */
 79 	angleDiff: function(a1, a2) {
 80 		var twoPi = 2 * Math.PI,
 81 			a = (a2 - a1) % twoPi;
 82 		if(Math.abs(a) < LinaJS.EPS){
 83 			return 0;
 84 		}else if(a > Math.PI){
 85 			return a - twoPi;
 86 		}else if(a < -Math.PI){
 87 			return a + twoPi;
 88 		}
 89 		return a;
 90 	},
 91 	/**
 92 	 * Return angle normalized to [0 <= a < 2*Pi]
 93 	 */
 94 	normAngle: function(a) {
 95 		var twoPi = 2 * Math.PI;
 96 		a = a % twoPi;
 97 		if(Math.abs(a) < LinaJS.EPS){
 98 			return 0;
 99 		}else if(a < 0){
100 			return a + twoPi;
101 		}
102 		return a;
103 	},
104 	/**
105 	 * Return value clamped [min <= f <= max]
106 	 */
107 	clamp: function(f, min, max) {
108 		if(max < min){
109 			var t = max, max = min, min = t;
110 		}
111 		return (f < min) ? min : (f > max) ? max : f;
112 	},
113 	/** Return a new Matrix3 (same as 'new Matrix3()'). */
114 	identity33: function() {
115 		return new Matrix3();
116 	},
117 	/** Return a new Matrix3 that represents a rotation about (0/0). */
118 	rotation33: function(a) {
119 		var s = Math.sin(a);
120 		var c = Math.cos(a);
121 		return new Matrix3( [ c, s, 0, -s, c, 0, 0, 0, 1 ]);
122 	},
123 	/** Return a new Matrix3 that represents a translation. */
124 	translation33: function(dx, dy) {
125 		return new Matrix3( [ 1, 0, 0, 0, 1, 0, dx, dy, 1 ]);
126 	},
127 	/** Return a new Matrix3 that represents a scaling about (0/0). */
128 	scale33: function(fx, fy) {
129 		if (fy === undefined){
130 			fy = +fx;
131 		}
132 		return new Matrix3( [ fx, 0, 0, 0, fy, 0, 0, 0, 1 ]);
133 	},
134 
135 	/** Return polar coordinates {a:_, r:_} for a cartesian vector or point. */
136 	vecToPolar: function(x, y) {
137 		return {a: Math.atan2(y, x),
138 				r: Math.sqrt(x * x + y * y)};
139 	},
140 
141 	/** Return a point {x:_, y:_} for the given polar coordinates. */
142 	polarToPt: function(a, r) {
143 //		return { x: r * Math.cos(a),
144 //				 y: r * Math.sin(a) };
145 		return new Point2(r * Math.cos(a), r * Math.sin(a));
146 	},
147 
148 	/** Return a vector {dx:_, dy:_} for the given polar coordinates. */
149 	polarToVec: function(a, r) {
150 //		return { dx: r * Math.cos(a),
151 //				 dy: r * Math.sin(a) };
152 		return new Vec2(r * Math.cos(a), r * Math.sin(a));
153 	},
154 
155 	/**Reflect this vector (in-place) and return this instance.
156 	 * @param {Vec2} vec
157 	 * @param {Vec2} reflectionNormal Normal vector pointing from reflection
158 	 * line towards vec.
159 	 * @returns {Vec2}
160 	 */
161 	reflectedVector: function(vec, reflectionNormal) {
162 		// TODO: this can be optimized
163 		var perp = reflectionNormal.copy().perp();
164 		var a = vec.dot(perp);
165 		var b = vec.dot(reflectionNormal);
166 		var reflected = reflectionNormal.copy().scale(-b).add(perp.scale(a));
167 		//window.console.log("len(vec)"+vec.length()+", len(ref):"+reflected.length()+",a+b:"+(a+b))
168 		return reflected;
169 	},
170 
171 	/** @private */
172 	_segmentsIntersect: function(pt1x, pt1y, pt2x, pt2y, pt3x, pt3y, pt4x, pt4y) {
173 		// public domain function by Darel Rex Finley, 2006
174 		// Return null, if the segments are colinear, even if they overlap.
175 		// Fail if either line segment is zero-length.
176 		if (pt1x==pt2x && pt1y==pt2y || pt3x==pt4x && pt3y==pt4y){
177 			return null;
178 		}
179 		// Fail if the segments share an end-point.
180 		if (pt1x==pt3x && pt1y==pt3y || pt2x==pt3x && pt2y==pt3y
181 			||  pt1x==pt4x && pt1y==pt4y || pt2x==pt4x && pt2y==pt4y) {
182 			return null;
183 		}
184 		// (1) Translate the system so that point A is on the origin.
185 		pt2x -= pt1x; pt2y -= pt1y;
186 		pt3x -= pt1x; pt3y -= pt1y;
187 		pt4x -= pt1x; pt4y -= pt1y;
188 		// Discover the length of segment A-B.
189 		var distAB = Math.sqrt(pt2x*pt2x + pt2y*pt2y);
190 		// (2) Rotate the system so that point B is on the positive X axis.
191 		var theCos = pt2x / distAB;
192 		var theSin = pt2y / distAB;
193 		var newX = pt3x * theCos + pt3y * theSin;
194 		pt3y = pt3y * theCos - pt3x * theSin;
195 		pt3x = newX;
196 		newX = pt4x * theCos + pt4y * theSin;
197 		pt4y = pt4y * theCos - pt4x * theSin;
198 		pt4x = newX;
199 		// Fail if segment C-D doesn't cross line A-B.
200 		if (pt3y<0 && pt4y<0 || pt3y>=0 && pt4y>=0 ){
201 			return null;
202 		}
203 		// (3) Discover the position of the intersection point along line A-B.
204 		var ABpos = pt4x + (pt3x - pt4x) * pt4y / (pt4y - pt3y);
205 		// Fail if segment C-D crosses line A-B outside of segment A-B.
206 		if (ABpos < 0 || ABpos > distAB ){
207 			return null;
208 		}
209 		// (4) Apply the discovered position to line A-B in the original coordinate system.
210 		return {x: pt1x + ABpos * theCos,
211 				y: pt1y + ABpos * theSin};
212 	},
213 	/** Return intersection point of line segment pt1/pt2 with with segment pt3/pt4.*/
214 	segmentsIntersect: function(pt1, pt2, pt3, pt4) {
215 		return LinaJS._segmentsIntersect(pt1.x, pt1.y, pt2.x, pt2.y,
216 				pt3.x, pt3.y, pt4.x, pt4.y);
217 	},
218 	/** @private */
219 	_linesIntersect: function(pt1x, pt1y, pt2x, pt2y, pt3x, pt3y, pt4x, pt4y) {
220 		// public domain function by Darel Rex Finley, 2006
221 		// Return null, if the segments are colinear, even if they overlap.
222 		// Fail if either line segment is zero-length.
223 		if (pt1x==pt2x && pt1y==pt2y || pt3x==pt4x && pt3y==pt4y){
224 			return null;
225 		}
226 		// (1) Translate the system so that point A is on the origin.
227 		pt2x -= pt1x; pt2y -= pt1y;
228 		pt3x -= pt1x; pt3y -= pt1y;
229 		pt4x -= pt1x; pt4y -= pt1y;
230 		// Discover the length of segment A-B.
231 		var distAB = Math.sqrt(pt2x*pt2x + pt2y*pt2y);
232 		// (2) Rotate the system so that point B is on the positive X axis.
233 		var theCos = pt2x / distAB;
234 		var theSin = pt2y / distAB;
235 		var newX = pt3x * theCos + pt3y * theSin;
236 		pt3y = pt3y * theCos - pt3x * theSin;
237 		pt3x = newX;
238 		newX = pt4x * theCos + pt4y * theSin;
239 		pt4y = pt4y * theCos - pt4x * theSin;
240 		pt4x = newX;
241 		//  Fail if the lines are parallel.
242 		if (pt4y == pt3y){
243 			return null;
244 		}
245 		// (3) Discover the position of the intersection point along line A-B.
246 		var ABpos = pt4x + (pt3x - pt4x) * pt4y / (pt4y - pt3y);
247 		// (4) Apply the discovered position to line A-B in the original coordinate system.
248 		return {x: pt1x + ABpos * theCos,
249 				y: pt1y + ABpos * theSin};
250 	},
251 	/** Return intersection point of line segment pt1/pt2 with with segment pt3/pt4.
252 	 *
253 	 * @returns {pt|null|undefined} intersection point {x:_, y:_} or null if there is no intersection.
254 	 * undefined is returned, if segments are collinear.
255 	 */
256 	linesIntersect: function(pt1, pt2, pt3, pt4) {
257 		return LinaJS._linesIntersect(pt1.x, pt1.y, pt2.x, pt2.y,
258 				pt3.x, pt3.y, pt4.x, pt4.y);
259 	},
260 	/** Return shortest (vertical) distance between a point and a line through ptA/ptB.*/
261 	distancePtLine: function(pt, ptA, ptB) {
262 		var dx = ptB.x - ptA.x;
263 		var dy = ptB.y - ptA.y;
264 		return Math.abs(dx*(ptA.y-pt.y) - dy*(ptA.x-pt.x)) / Math.sqrt(dx*dx + dy*dy);
265 	},
266 	/** Return shortest distance between a point and the line segment from ptA to ptB.*/
267 	distancePtSegment: function(pt, ptA, ptB) {
268 		// dot(ptA->ptB, ptB->pt)
269 		var dx = pt.x - ptB.x;
270 		var dy = pt.y - ptB.y;
271 		var dot = (ptB.x - ptA.x) * dx + (ptB.y - ptA.y) * dy;
272 		if(dot > 0){
273 			return Math.sqrt(dx*dx + dy*dy); // distance(ptB, pt);
274 		}
275 		// dot(ptB->ptA, ptA->pt)
276 		dx = pt.x - ptA.x;
277 		dy = pt.y - ptA.y;
278 		dot = (ptA.x - ptB.x) * dx + (ptA.y - ptB.y) * dy;
279 		if(dot > 0){
280 			return Math.sqrt(dx*dx + dy*dy); // distance(ptA, pt);
281 		}
282 		return LinaJS.distancePtLine(pt, ptA, ptB);
283 	},
284 	/**Intersection of two moving circles.
285 	 * @param c1 {x, y, vx, vy, r}
286 	 * @param c2 {x, y, vx, vy, r}
287 	 * @param {float} maxT
288 	 * @returns {ptColl, vColl, t} or null
289 	 */
290 	intersectMovingCircles: function(c1, c2, maxT) {
291 		// See http://compsci.ca/v3/viewtopic.php?t=14897
292 		maxT = maxT || 1;
293 		// Breaking down the formula for t
294 		var A = c1.vx*c1.vx + c1.vy*c1.vy - 2*c1.vx*c2.vx + c2.vx*c2.vx
295 				- 2*c1.vy*c2.vy + c2.vy*c2.vy;
296 		var B = -c1.x*c1.vx - c1.y*c1.vy + c1.vx*c2.x + c1.vy*c2.y + c1.x*c2.vx
297 				- c2.x*c2.vx + c1.y*c2.vy - c2.y*c2.vy;
298 		var C = c1.vx*c1.vx + c1.vy*c1.vy - 2*c1.vx*c2.vx + c2.vx*c2.vx
299 				- 2*c1.vy*c2.vy + c2.vy*c2.vy;
300 		var D = c1.x*c1.x + c1.y*c1.y - c1.r*c1.r - 2*c1.x*c2.x + c2.x*c2.x
301 				- 2*c1.y*c2.y + c2.y*c2.y - 2*c1.r*c2.r - c2.r*c2.r;
302 		var disc = (-2 * B) * (-2 * B) - 4 * C * D;
303 		// If the discriminent is non negative, a collision will occur and
304 		// we must compare the time to our current time of collision. We
305 		// update the time if we find a collision that has occurred earlier
306 		// than the previous one.
307 		if(disc <= 0){
308 			return false;
309 		}
310 		// We want the smallest time
311 		var t = Math.min(0.5 * (2 * B - Math.sqrt(disc)) / A,
312 				0.5 * (2 * B + Math.sqrt(disc)) / A);
313 //		if(maxT && (t > maxT)){
314 //			return false;
315 //		}
316 		return {
317 			ptColl: null,
318 			vColl: null,
319 			t: t
320 		};
321 	},
322 	/** Return true, if lina.js objects a and b are the same (within eps).
323 	 * This function is not optimized for speed, but handy for unit tests.
324 	 * @param a {float|Point2|Vec2|Matrix3,JS-Object,...}
325 	 * @param b must have the same type as a
326 	 * @param eps {float} Maximum accepted difference, defaults to 0.00001
327 	 */
328 	compare: function(a, b, eps) {
329 		eps = (eps === undefined) ? LinaJS.EPS : eps;
330 		if( a === undefined || b === undefined ){
331 			// undefined is equal to nothing!
332 			return false;
333 		} else if( a === null || b === null ){
334 				return a === null && b === null;
335 		} else if( a.m !== undefined || b.m !== undefined){
336 			// Matrix3 (also allow comparison to an array)
337 			a = a.m || a;
338 			b = b.m || b;
339 			return LinaJS.compare(a, b, eps);
340 		} else if( a.xyList !== undefined || b.xyList !== undefined){
341 			// Polygon2 (also allow comparison to an array)
342 			a = a.xyList || a;
343 			b = b.xyList || b;
344 			return LinaJS.compare(a, b, eps);
345 		} else if( typeof a !== typeof b ){
346 				return false;
347 		} else if( typeof a === "string" ){
348 			return a === b;
349 		} else if( typeof a === "number" ){
350 			return Math.abs(a-b) <= eps;
351 		} else if( a && a.constructor === Array ){
352 			if( a.length !== b.length){
353 				return false;
354 			}
355 			for(var i=0; i<a.length; i++){
356 				if(!LinaJS.compare(a[i], b[i], eps)){
357 					return false;
358 				}
359 			}
360 		} else if( a.x !== undefined ){
361 			return LinaJS.compare(a.x, b.x, eps) && LinaJS.compare(a.y, b.y, eps);
362 		} else if( a.dx !== undefined ){
363 			return LinaJS.compare(a.dx, b.dx, eps) && LinaJS.compare(a.dy, b.dy, eps);
364 		} else if( a.a !== undefined ){
365 			return LinaJS.compare(a.a, b.a, eps) && LinaJS.compare(a.r, b.r, eps);
366 		} else if( a.xyList !== undefined ){
367 			// Polygon2
368 			return LinaJS.compare(a.xyList, b.xyList, eps);
369 		} else {
370 			alert("LinaJS.compare: unsupported types\n  " + a + "("+(typeof a)+"),\n  " + b+ "("+(typeof b)+")");
371 		}
372 		return true;
373 	},
374 	__lastEntry: undefined
375 };
376 
377 
378 /*****************************************************************************/
379 
380 
381 /**
382  * Point in 2D space that has an internal cartesian representation (x/y)
383  * and support for transformations.
384  * When applying transformations, a point is handled as [x, y, 1].
385  * @constructor
386  * @param {float|Point2|JS-object} x X-coordinate or a Point2 instance or {x:_, y:_}
387  * @param {float} y Y-coordinate or undefined, if x is a Point2 instance or {x:_, y:_}
388  * @example
389  *   var pt1 = new Point2(3, 4);
390  *   pt1.rotate(Math.PI).translate(1, 2);
391  *   var pt2 = new Point2({x:2, y:1});
392  *   var dist = pt1.distanceTo(pt2)
393  *
394  */
395 Point2 = function(x, y){
396 	this.set(x, y);
397 };
398 Point2.prototype = {
399 	/** Return string representation '(x/y)'. */
400 	toString: function(prec) {
401 		if(prec !== undefined){
402 			return "(" + this.x.toPrecision(prec) + "/" + this.y.toPrecision(prec)  + ")";
403 		}
404 		return "(" + this.x + "/" + this.y  + ")";
405 	},
406 	/** Set coordinates.
407 	 * @param {float|Point2|JS-object} x X-coordinate or a Point2 instance or {x:_, y:_}
408 	 * @param {float} y Y-coordinate or undefined, if x is a Point2 instance or {x:_, y:_}
409 	 * @returns {Point2}
410 	 */
411 	set: function(x, y) {
412 		if(y === undefined){
413 			// Copy from Point2
414 			this.x = +x.x;
415 			this.y = +x.y;
416 		} else {
417 			this.x = +x;
418 			this.y = +y;
419 		}
420 		return this;
421 	},
422 	/** Return a new copy of this point.
423 	 * @returns {Point2}
424 	 */
425 	copy: function() {
426 		return new Point2(this.x, this.y);
427 	},
428 	/** Return squared distance from this to pt2. .
429 	 * @param {Point2|JS-Object} pt2 Second point.
430 	 * @returns {float}
431 	 */
432 	sqrDistanceTo: function(ptOrX, y) {
433 		var dx, dy;
434 		if(y === undefined) {
435 			dx = this.x - ptOrX.x;
436 			dy = this.y - ptOrX.y;
437 		}else{
438 			dx = this.x - ptOrX;
439 			dy = this.y - y;
440 		}
441 		return dx*dx + dy*dy;
442 	},
443 	/** Return distance from this to pt2. .
444 	 * @param {Point2|JS-Object} pt2 Second point.
445 	 * @returns {float}
446 	 */
447 	distanceTo: function(ptOrX, y) {
448 		return Math.sqrt(this.sqrDistanceTo(ptOrX, y));
449 	},
450 	/** Return Manhattan-Distance from this to pt2.
451 	 * @param {Point2} pt2 (optional) Second point.
452 	 * @returns {float}
453 	 */
454 	mdistance: function(pt2) {
455 		if(pt2 === undefined){
456 			return Math.abs(this.x) + Math.abs(this.y);
457 		}else{
458 			return Math.abs(this.x - pt2.x) + Math.abs(this.y - pt2.y);
459 		}
460 	},
461 	/** Check if pt2 is (aproximately) equal to this.
462 	 * @param {Point2|JS-Object} pt2 Second point.
463 	 * @param {float} eps (optional) accepted maximum distance.
464 	 * @returns {boolean}
465 	 */
466 	isEqual: function(pt2, eps) {
467 		eps = ( eps === undefined ) ? LinaJS.EPS_SQUARED : eps * eps;
468 		return this.sqrDistanceToPt(pt2) <= eps;
469 	},
470 	/** Rotate this point (in-place) and return this instance.
471 	 * @param {float} a Angle in radians.
472 	 * @param {Point2} ptCenter (optional) center of rotation, defaults to (0/0).
473 	 * @returns {Point2}
474 	 */
475 	rotate: function(a, ptCenter) {
476 		var c = Math.cos(a);
477 		var s = Math.sin(a);
478 		var prevX = this.x;
479 		if(ptCenter === undefined){
480 			// rotate about 0/0
481 			this.x = c*prevX - s*this.y;
482 			this.y = s*prevX + c*this.y;
483 		}else {
484 			// TODO
485 			throw "not implemented";
486 		}
487 		return this;
488 	},
489 	/** Translate point (in-place) and return this instance.
490 	 * @param {float|Vec2} vecOrDx x-offset or offset vector
491 	 * @param {float|undefined} dy y-offset (omit this parameter, if x is a Vec2)
492 	 * @returns {Point2}
493 	 */
494 	translate: function(vecOrDx, dy) {
495 		if(dy === undefined){
496 			this.x += vecOrDx.dx;
497 			this.y += vecOrDx.dy;
498 		}else{
499 			this.x += vecOrDx;
500 			this.y += dy;
501 		}
502 		return this;
503 	},
504 	/** Apply transformation matrix (in-place) and return this instance.
505 	 * @returns {Point2}
506 	 */
507 	transform: function(m) {
508 		var xy = m.transformPt(this.x, this.y);
509 		this.x = xy.x;
510 		this.y = xy.y;
511 		return this;
512 	},
513 	/** Return vector from this to pt2.
514 	 * @param {Point2|JS-Object} pt2 Second point.
515 	 * @returns {Vec2}
516 	 */
517 	vectorTo: function(ptOrX, y) {
518 		if(y === undefined) {
519 			return new Vec2(ptOrX.x - this.x, ptOrX.y - this.y);
520 		}else{
521 			return new Vec2(ptOrX - this.x, y - this.y);
522 		}
523 	},
524 	__lastEntry: undefined
525 };
526 
527 /** Return distance from this to pt2.
528  * @param {Point2|JS-Object} pt1 First point.
529  * @param {Point2|JS-Object} pt2 Second point.
530  * @returns {float}
531  */
532 Point2.distanceTo = function(pt1, ptOrX, y) {
533 	return pt1.distanceTo(ptOrX, y);
534 };
535 
536 /** Check if pt2 is (aproximately) equal to pt1.
537  * @param {Point2|JS-Object} pt1 First point.
538  * @param {Point2|JS-Object} pt2 Second point.
539  * @param {float} eps (optional) accepted maximum distance.
540  * @returns {boolean}
541  */
542 Point2.isEqual = function(pt1, pt2, eps) {
543 	return pt1.isEqual(pt2, eps);
544 };
545 
546 /** Return rotated copy of pt.
547  * @param {Point2} pt point that will be rotaded.
548  * @param {float} a Angle in radians.
549  * @param {Point2} ptCenter (optional) center of rotation, defaults to (0/0).
550  * @returns {Point2}
551  */
552 Point2.rotate = function(pt, a, ptCenter){
553 	return pt.copy().rotate(a, ptCenter);
554 };
555 
556 /** Return a copy of pt transformed by m.
557  * @param {Point2} pt point that will be transformed.
558  * @param {Matrix3} m tranformation matrix.
559  * @returns {Point2}
560  */
561 Point2.transform = function(pt, m) {
562 	return pt.copy().transform(m);
563 };
564 
565 /** Return a translated copy of pt.
566  * @param {Point2} pt point that will be translated.
567  * @param {float|Vec2} dx x-offset or offset vector
568  * @param {float|undefined} dy y-offset (omit this parameter, if x is a Vec2)
569  * @returns {Point2}
570  */
571 Point2.translate = function(pt, dx, dy) {
572 	return pt.copy().translate(dx, dy);
573 };
574 
575 /** Return vector from pt1 to pt2.
576  * @param {Point2|JS-Object} pt1 First point.
577  * @param {Point2|JS-Object} pt2 Second point.
578  * @returns {float}
579  */
580 Point2.vectorTo = function(pt1, ptOrX, y) {
581 	return pt1.vectorTo(ptOrX, y);
582 };
583 
584 /**
585  * 2D vector that has an internal cartesian representation (dx, dy)
586  * and support for transformations.
587  * When applying transformations, a vector is handled as [dx, dy, 0].
588  * @constructor
589  * @param {float|Vec2|JS-object} dx X-coordinate or a Vec2 instance or {dx:_, dy:_}
590  * @param {float} dy Y-coordinate or undefined, if x is a Vec2 instance or {dx:_, dy:_}
591  * @example
592  *   var v = new Vec2(3, 4);
593  *   v.rotate(Math.PI).translate(1, 2);
594  *
595  */
596 Vec2 = function(dx, dy){
597 	this.set(dx, dy);
598 };
599 Vec2.prototype = {
600 	/** Return string representation '(dx, dy)'. */
601 	toString: function(prec) {
602 		if(prec !== undefined){
603 			return "(" + this.dx.toPrecision(prec) + ", " + this.dy.toPrecision(prec)  + ")";
604 		}
605 		return "(" + this.dx + ", " + this.dy  + ")";
606 	},
607 	/** Set coordinates.
608 	 * @param {float|Vec2|JS-object} dx X-coordinate or a Vec2 instance or {dx:_, dy:_}
609 	 * @param {float} dy Y-coordinate or undefined, if y is a Vec2 instance or {dx:_, dy:_}
610 	 * @returns {Vec2}
611 	 */
612 	set: function(dx, dy) {
613 		if(dy === undefined){
614 			if(dx.a !== undefined){
615 				// Copy from Polar2
616 				this.dx = dx.r * Math.cos(dx.a);
617 				this.dy = dx.r * Math.sin(dx.a);
618 			}else{
619 				// Copy from Vec2
620 				this.dx = +dx.dx;
621 				this.dy = +dx.dy;
622 			}
623 		} else {
624 			this.dx = +dx;
625 			this.dy = +dy;
626 		}
627 		return this;
628 	},
629 	/** Return a new copy of this vector.
630 	 * @returns {Vec2}
631 	 */
632 	copy: function() {
633 		return new Vec2(this.dx, this.dy);
634 	},
635 	/** Calculate the dot product (inner product) of this vector and v2.
636 	 * @param {Vec2|JS-Object} v2 Other vector.
637 	 * @returns {float}
638 	 */
639 	dot: function(v2) {
640 		return this.dx * v2.dx + this.dy * v2.dy;
641 	},
642 	/** Calculate the cross product of this vector and v2.
643 	 * @param {Vec2|JS-Object} v2 Other vector.
644 	 * @returns {float}
645 	 */
646 	cross: function(v2) {
647 		return this.dx * v2.dy - this.dy * v2.dx;
648 	},
649 	/** Normalize to a unit vector (in-place) and return this instance.
650 	 * @returns {Vec2}
651 	 */
652 	normalize: function() {
653 		// Convert to unit vector.
654 		var l = this.length();
655 		if(l) {
656 			this.dx /= l;
657 			this.dy /= l;
658 		}
659 		return this;
660 	},
661 	/**Return vector length ^2.
662 	 * This is faster than calling length().
663 	 * @returns {float}
664 	 */
665 	sqrLength: function() {
666 		return this.dx * this.dx + this.dy * this.dy;
667 	},
668 	/**Return vector length.
669 	 * @returns {float}
670 	 */
671 	length: function() {
672 		try {
673 			return Math.sqrt(this.dx * this.dx + this.dy * this.dy);
674 		} catch (e) {
675 			return 0;
676 		}
677 	},
678 	/**Clamp vector length (in-place).
679 	 * @param {float} length Maximum length.
680 	 * @returns {Vec2}
681 	 */
682 	limit: function(length) {
683 		if(this.sqrLength() > length*length){
684 			this.scale(length / this.length());
685 		}
686 		return this;
687 	},
688 	/**Apply a 'force' vector or offset (in-place) within given limits.
689 	 * @param {float | Vec2} force vector. If a float is passed, then it is
690 	 * assumed to be the length of a vector along current direction.
691 	 * @param {float} maxLength (optional) maximum length of resulting vector.
692 	 * @param {float} minLength (optional) minimum length. If omitted, a Null-Vector is returned when EPS is reached.
693 	 * @returns {Vec2}
694 	 */
695 	accelerate: function(force, maxLength, minLength) {
696 		if(force.dx !== undefined){
697 			// force is a vector
698 			this.add(force);
699 		}else{
700 			if(this.isNull()){
701 				return this;
702 			}
703 			// force is the length of a vector along current heading
704 			this.add(this.copy().setLength(force));
705 		}
706 		var l2 = this.sqrLength();
707 		if(minLength){
708 			if(l2 < minLength * minLength){
709 				this.scale(minLength / this.length());
710 				return this;
711 			}
712 		} else if(l2 < LinaJS.EPS_SQUARED){
713 			this.setNull();
714 			return this;
715 		}
716 		if(maxLength && this.sqrLength() > maxLength * maxLength){
717 			this.scale(maxLength / this.length());
718 		}
719 		return this;
720 	},
721 	/**Check, if vector is (0, 0)
722 	 * @returns {boolean}
723 	 */
724 	isNull: function() {
725 		return this.dx === 0 && this.dy === 0;
726 	},
727 	/**Set vector to (0, 0)
728 	 * @returns {Vec2}
729 	 */
730 	setNull: function() {
731 		return this.set(0, 0);
732 	},
733 	/**Return the angle between positive x axis and this vector.
734 	   @returns {float}  [-pi .. pi], ccw
735 	*/
736 	angle: function(){
737 		return Math.atan2(this.dy, this.dx);
738 	},
739 	/**Return the angle between this vector and v2.
740 	   @returns {float}  [-pi .. pi], ccw
741 	*/
742 	angleTo: function(v2){
743 //		return Math.acos(this.dot(v2) /  (this.length() * Math.sqrt(v2.dx * v2.dx + v2.dy * v2.dy)));
744 //		return Math.asin(this.cross(v2) /  (this.length() * Math.sqrt(v2.dx * v2.dx + v2.dy * v2.dy)));
745 		return Math.atan2(v2.dy, v2.dx) - Math.atan2(this.dy, this.dx);
746 	},
747 	/**Set the angle (in-place, relative to positive x axis).
748 	   @returns {Vec2}
749 	*/
750 	setAngle: function(a){
751 		var cura = this.angle();
752 		if(!this.isNull() && Math.abs(a-cura) > LinaJS.EPS){
753 			this.rotate(a-cura);
754 		}
755 		return this;
756 	},
757 	/** Multiply vector length by a factor (in-place) and return this instance.
758 	 * @param {float} f Scaling factor.
759 	 * @returns {Vec2}
760 	 */
761 	scale: function(f) {
762 		this.dx *= f;
763 		this.dy *= f;
764 		return this;
765 	},
766 	/** Flip this vector (in-place) and return this instance.
767 	 * @returns {Vec2}
768 	 */
769 	revert: function() {
770 		this.dx *= -1;
771 		this.dy *= -1;
772 		return this;
773 	},
774 	/** Rotate this vector (in-place) and return this instance.
775 	 * @param {float} a Angle in radians.
776 	 * @returns {Vec2}
777 	 */
778 	rotate: function(a) {
779 		var s = Math.sin(a), c = Math.cos(a);
780 		this.dx = this.dx * c - this.dy * s;
781 		this.dy = this.dy * c + this.dx * s;
782 		return this;
783 	},
784 	/** Apply transformation matrix (in-place) and return this instance.
785 	 * @returns {Vec2}
786 	 */
787 	transform: function(m) {
788 		var xy = m.transformVec(this.dx, this.dy);
789 		this.dx = xy.dx;
790 		this.dy = xy.dy;
791 		return this;
792 	},
793 	/** Set vector length (in-place) and return this instance.
794 	 * @param {float} length New length.
795 	 * @returns {Vec2}
796 	 */
797 	setLength: function(length) {
798 		if(!this.isNull()){
799 			this.scale(length / this.length());
800 		}
801 		return this;
802 	},
803 	/** Return polar coordinates for this vector.
804 	 * @returns {JS-Object} {a:angle in rad, r: radius}.
805 	 */
806 	getPolar: function() {
807 		// TODO
808 		alert("Not implemented: Vec2.getPolar()");
809 	},
810 	/** Set vector orientation to perpendicular of itself (in-place) and return this
811 	 * instance.
812 	 * This is equivalent to a rotation by 90�, only faster.
813 	 * @returns {Vec2}
814 	 */
815 	perp: function() {
816 		var t = this.dx;
817 		this.dx = -this.dy;
818 		this.dy = t;
819 		return this;
820 	},
821 	/** Check if v2 is perpendicular to this vector.
822 	 * @param {Vec2|JS-Object} v2 Other vector.
823 	 * @returns {boolaen}
824 	 */
825 	isPerp: function(v2) {
826 		// Vectors are perpendicular if the dot product is zero.
827 		return Math.abs(this.dot(v2)) < LinaJS.EPS;
828 	},
829 	/** Check if v2 is parallel to this vector.
830 	 * @param {Vec2|JS-Object} v2 Other vector.
831 	 * @returns {boolaen}
832 	 */
833 	isColinear: function(v2) {
834 		// Vectors are colinear if the dot product is one.
835 		return Math.abs(1 - this.dot(v2)) < LinaJS.EPS;
836 	},
837 	/**Add another vector to this vector and return the current instance.
838 	 * @param {Vec2|JS-Object} vecOrDx Second vector.
839 	 * @returns {Vec2}
840 	 */
841 	add: function(vecOrDx, dy) {
842 		if(dy === undefined) {
843 			this.dx += vecOrDx.dx;
844 			this.dy += vecOrDx.dy;
845 		}else{
846 			this.dx += dx;
847 			this.dy += dy;
848 		}
849 		return this;
850 	},
851 	/**Subtract another vector from this vector and return the current instance.
852 	 * @param {Point2|JS-Object} vecOrDx Second point.
853 	 * @returns {Vec2}
854 	 */
855 	sub: function(vecOrDx, dy) {
856 		if(dy === undefined) {
857 			this.dx -= vecOrDx.dx;
858 			this.dy -= vecOrDx.dy;
859 		}else{
860 			this.dx -= dx;
861 			this.dy -= dy;
862 		}
863 		return this;
864 	},
865 	__lastEntry: undefined
866 };
867 
868 /** Calculate the dot product (inner product) of this vector and v2.
869  * @param {Vec2|JS-Object} v1 First vector.
870  * @param {Vec2|JS-Object} v2 Other vector.
871  * @returns {float}
872  */
873 Vec2.dot = function(v1, v2) {
874 	return v1.dx * v2.dx + v1.dy * v2.dy;
875 };
876 /** Calculate the cross product of this vector and v2.
877  * @param {Vec2|JS-Object} v1 First vector.
878  * @param {Vec2|JS-Object} v2 Other vector.
879  * @returns {float}
880  */
881 Vec2.cross = function(v1, v2) {
882 	return v1.dx * v2.dy - v1.dy * v2.dx;
883 };
884 /** Return a normalized copy of v1.
885  * @param {Vec2|JS-Object} v1.
886  * @returns {Vec2}
887  */
888 Vec2.normalize = function(v1) {
889 	return v1.copy().normalize();
890 };
891 /**Return copy of vector with limited length.
892  * @param {Vec2|JS-Object} v1.
893  * @param {float} length Maximum length.
894  * @returns {Vec2}
895  */
896 Vec2.limit = function(v1, length) {
897 	return v1.copy().limit(length);
898 };
899 /** Return a copy of v1 with length multiplied by a factor.
900  * @param {Vec2|JS-Object} v1 First vector.
901  * @param {float} f Scaling factor.
902  * @returns {Vec2}
903  */
904 Vec2.scale = function(v1, f) {
905 	return v1.copy().scale(f);
906 };
907 /** Return a flipped copy of vector.
908  * @param {Vec2|JS-Object} v1 First vector.
909  * @returns {Vec2}
910  */
911 Vec2.revert = function(v1) {
912 	return v1.copy().revert();
913 };
914 /** Return a rotated copy of a vector.
915  * @param {Vec2|JS-Object} v1 First vector.
916  * @param {float} a Angle in radians.
917  * @returns {Vec2}
918  */
919 Vec2.rotate = function(v1, a) {
920 	return v1.copy().rotate(a);
921 };
922 /** Return a transformed copy of a vector.
923  * @param {Vec2|JS-Object} v1 First vector.
924  * @returns {Vec2}
925  */
926 Vec2.transform = function(v1, m) {
927 	return v1.copy().transform(m);
928 };
929 /** Return a copy of vector with a defined length.
930  * @param {Vec2|JS-Object} v1 First vector.
931  * @param {float} length New length.
932  * @returns {Vec2}
933  */
934 Vec2.setLength = function(v1, length) {
935 	return v1.copy().setLength(length);
936 };
937 /** Return a perpendicluar copy of a vector.
938  * This is equivalent to a rotation by 90�, only faster.
939  * @param {Vec2|JS-Object} v1 First vector.
940  * @returns {Vec2}
941  */
942 Vec2.perp = function(v1) {
943 	return v1.copy().perp();
944 };
945 /**Return a new vector that combines two vectors.
946  * @param {Vec2|JS-Object} v1 First vector.
947  * @param {Vec2|JS-Object} vecOrDx Second vector.
948  * @returns {Vec2}
949  */
950 Vec2.add = function(v1, vecOrDx, dy) {
951 	return v1.copy().add(vecOrDx, dy);
952 };
953 /**Return a new vector that combines v1 minus v2.
954  * @param {Vec2|JS-Object} v1 First vector.
955  * @param {Vec2|JS-Object} vecOrDx Second vector.
956  * @returns {Vec2}
957  */
958 Vec2.sub = function(v1, vecOrDx, dy) {
959 	return v1.copy().sub(vecOrDx, dy);
960 };
961 
962 
963 /*******************************************************************************
964  * Class Matrix3
965  * 3x3 matrix
966  */
967 /**
968  * Creates a new 3x3 matrix for transforming in 2d space.
969  * @constructor
970  * @param {undefined|Matrix3|float[9]} m
971  *
972  * Translation:
973  * @example
974  * [1  0  0,
975  *  0  1  0,
976  *  Tx Ty 1]
977  *
978  * Scale:
979  * @example
980  * [Sx 0  0,
981  *  0  Sy 0,
982  *  0  0  1]
983  *
984  * Rotation:
985  * @example
986  * [ c  s 0,
987  *  -s  c 0,
988  *   0  0 1]
989  */
990 Matrix3 = function(m){
991 	this.set(m);
992 };
993 Matrix3.prototype = {
994 	/**Return string representation '[[0, 1, 2], [3, 4, 5], [6, 7, 8]]'.
995 	 * @returns {string}
996 	 */
997 	toString: function() {
998 		var m = this.m;
999 		return "[["+m[0]+", "+m[1]+", "+m[2]+"], ["+m[3]+", "+m[4]+", "+m[5]+"], ["+m[6]+", "+m[7]+", "+m[8]+"]]";
1000 	},
1001 	/**Set the current matrix.
1002 	 *  @param {Matrix3|float[9]} m (optional) defaults to identity matrix [1, 0, 0, 0, 1, 0, 0, 0, 1]
1003 	 *  @returns {Matrix3}
1004 	 */
1005 	set: function(m) {
1006 		if( m === undefined ) {
1007 			/**Matrix value stored as array of 9 floats.
1008 			 * @type {float[9]} */
1009 			this.m = [1, 0, 0, 0, 1, 0, 0, 0, 1];
1010 			/**Defines, if this matrix is non-perspective, i.e. the right column is
1011 			 * [0, 0, 1] so that m[2] = m[5] = 0 and m[8] = 1.
1012 			 * In this case transformations can be processed more efficiently.
1013 			 * Default: true.
1014 			 * @type {boolean} */
1015 			this.isAffine = true;
1016 		}else if( m.length === 9 ) {
1017 			// Set from float[9]
1018 			this.m = m.slice();
1019 			this.isAffine = (m[2] === 0) && (m[5] === 0) && (m[8] === 1);
1020 		}else{
1021 			// Set from Matrix3
1022 			this.m = m.m.slice();
1023 			this.isAffine = m.isAffine;
1024 		}
1025 		return this;
1026 	},
1027 	/**Reset the current matrix to identity.
1028 	 * @returns {Matrix3}
1029 	 */
1030 	reset: function() {
1031 		return this.set();
1032 	},
1033 	/** Create and return a copy of this matrix.*/
1034 	copy: function() {
1035 		return new Matrix3(this.m);
1036 	},
1037 	/** Apply translation (in-place) and return this instance.*/
1038 	translate: function(dx, dy) {
1039 		/* TODO: optimize
1040 		 * for last column = [0, 0, 1] this simplifies to
1041 		 *   this.m[6] += dx;
1042 		 *   this.m[7] += dy;
1043 		 */
1044 		var m = this.m;
1045 		m[0] += dx*m[2];    m[1] += dy*m[2];
1046 		m[3] += dx*m[5];    m[4] += dy*m[5];
1047 		m[6] += dx*m[8];    m[7] += dy*m[8];
1048 		return this;
1049 	},
1050 	/** Apply scaling (in-place) and return this instance.*/
1051 	scale: function(fx, fy) {
1052 		if(fy === undefined){
1053 			fy = +fx;
1054 		}
1055 		var m = this.m;
1056 		m[0] *= fx;    m[1] *= fy;
1057 		m[3] *= fx;    m[4] *= fy;
1058 		m[6] *= fx;    m[7] *= fy;
1059 		return this;
1060 	},
1061 	/** Apply rotation (in-place) and return this instance.*/
1062 	rotate: function(a, pt) {
1063 		if( pt === undefined ){
1064 //			return this.mult(LinaJS.rotation33(a));
1065 			var c = Math.cos(a),
1066 				s = Math.sin(a),
1067 				m = this.m,
1068 				t = m.slice(); // Temporary copy
1069 			m[0] = c*t[0] - s*t[1];    m[1] = s*t[0] + c*t[1];
1070 			m[3] = c*t[3] - s*t[4];    m[4] = s*t[3] + c*t[4];
1071 			m[6] = c*t[6] - s*t[7];    m[7] = s*t[6] + c*t[7];
1072 			return this;
1073 		}else{
1074 			return this.translate(-pt.x, -pt.y)
1075 				.rotate(a)
1076 				.translate(pt.x, pt.y);
1077 		}
1078 	},
1079 	/** Apply transformation (in-place) and return this instance.*/
1080 	mult: function(mb) {
1081 		/* TODO: optimize
1082 		 * http://www.euclideanspace.com/maths/algebra/matrix/resources/code/index.htm#mul3
1083 		 * Newman, p.62ff
1084 		 *
1085 		 */
1086 		mb = mb.length ? mb : mb.m;
1087 		var ma = this.m,
1088 			mc = [0,0,0, 0,0,0, 0,0,0],
1089 			a, b, c, row, col, i;
1090 		for(row=0; row<3; row++) {
1091 			for(col=0; col<3; col++) {
1092 				c = 3*row + col;
1093 				for(i=0; i<3; i++) {
1094 					a = 3*row + i;
1095 					b = 3*i + col;
1096 					mc[c] += ma[a] * mb[b];
1097 				}
1098 			}
1099 		}
1100 		this.set(mc);
1101 		return this;
1102 	},
1103 	/** Return transformed x and y as JS-object {x:x', y:y'}.*/
1104 	transformPt: function(x, y) {
1105 		// Since a point is [x, y, 1], the translation part is applied.
1106 		var m = this.m;
1107 		if(this.isAffine){
1108 			return {
1109 				x: m[0]*x + m[3]*y + m[6],
1110 				y: m[1]*x + m[4]*y + m[7]
1111 			};
1112 		}else{
1113 			//TODO: untested
1114 			var w = m[2]*x + m[5]*y + m[8];
1115 			return {
1116 				x: (m[0]*x + m[3]*y + m[6]) / w,
1117 				y: (m[1]*x + m[4]*y + m[7]) / w
1118 			};
1119 		}
1120 	},
1121 	/** Return transformed dx and dy as JS-object {dx:_, dy:_}.*/
1122 	transformVec: function(dx, dy) {
1123 		// Since a vector is [dx, dy, 0], the translation part is ignored.
1124 		//TODO: this assumes isAffine == true
1125 		var m = this.m;
1126 		if(this.isAffine){
1127 			return {
1128 				dx: m[0]*dx + m[3]*dy,
1129 				dy: m[1]*dx + m[4]*dy
1130 			};
1131 		}else{
1132 			//TODO: untested
1133 			var w = m[2]*dx + m[5]*dy;
1134 			return {
1135 				dx: (m[0]*dx + m[3]*dy + m[6]) / w,
1136 				dy: (m[1]*dx + m[4]*dy + m[7]) / w
1137 			};
1138 		}
1139 	},
1140 	/** Transpose (in-place) and return this instance.*/
1141 	transpose: function() {
1142 		var m = this.m, t;
1143 		t = m[1]; m[1] = m[3]; m[3] = t;
1144 		t = m[2]; m[2] = m[6]; m[6] = t;
1145 		t = m[5]; m[5] = m[7]; m[7] = t;
1146 		return this;
1147 	},
1148 	/**Calculate the determinant.
1149 	 * @returns {float}
1150 	 */
1151 	det: function() {
1152 		var m = this.m;
1153 		if(this.isAffine){
1154 			return m[0]*m[4] - m[1]*m[3];
1155 		} else {
1156 			// Rule of Sarrus
1157 			return m[0]*m[4]*m[8] + m[1]*m[5]*m[6] + m[2]*m[3]*m[7]
1158 				- m[0]*m[5]*m[7] - m[1]*m[3]*m[8] - m[2]*m[4]*m[6];
1159 		}
1160 	},
1161 	/** Invert (in-place) and return this instance.
1162 	* @returns {Matrix3}
1163 	* @throws "Cannot invert", if det(m) == 0
1164 	*/
1165 	invert: function() {
1166 		var det = this.det();
1167 		if ( Math.abs(det) < LinaJS.EPS ) {
1168 			throw "Cannot invert " + this;
1169 		}
1170 		var m = this.m;
1171 		// http://en.wikipedia.org/wiki/Invertible_matrix
1172 		var invdet = 1.0 / det;
1173 //		var t = new Array(9); // make a copy
1174 		var t = [ // make a copy
1175 			 (m[4]*m[8] - m[7]*m[5]) * invdet,
1176 			-(m[1]*m[8] - m[2]*m[7]) * invdet,
1177 			 (m[1]*m[5] - m[2]*m[4]) * invdet,
1178 			-(m[3]*m[8] - m[5]*m[6]) * invdet,
1179 			 (m[0]*m[8] - m[2]*m[6]) * invdet,
1180 			-(m[0]*m[5] - m[3]*m[2]) * invdet,
1181 			 (m[3]*m[7] - m[6]*m[4]) * invdet,
1182 			-(m[0]*m[7] - m[6]*m[1]) * invdet,
1183 			 (m[0]*m[4] - m[3]*m[1]) * invdet
1184 		];
1185 		this.m = t;
1186 		return this;
1187 	},
1188 	/**Calculate the vector (dx:0, dy:1) tranformed by this.
1189 	 * @returns {Vec2}
1190 	 */
1191 	orientation: function() {
1192 		return new Vec2(this.transformVec(0, 1));
1193 	},
1194 	__lastEntry: undefined
1195 };
1196 
1197 
1198 /******************************************************************************/
1199 
1200 
1201 /**
1202  * Creates 3x3 homogenous transformation that also maintains its own inversion.
1203  * This is usually more effient than calling m.invert().
1204  * @constructor
1205  * @param {undefined|Matrix3|float[9]} m
1206  */
1207 BiTran2 = function(m){
1208 	this.set(m);
1209 };
1210 BiTran2.prototype = {
1211 	/**Return string representation '[[0, 1, 2], [3, 4, 5], [6, 7, 8]]'.
1212 	 * @returns {string}
1213 	 */
1214 	toString: function() {
1215 		return this.matrix.toString() + " - Inverse: " + this.inverse.toString();
1216 	},
1217 	/**Set the current matrix.
1218 	 *  @param {Matrix3|float[9]} m (optional) defaults to identity matrix [1, 0, 0, 0, 1, 0, 0, 0, 1]
1219 	 *  @returns {Matrix3}
1220 	 */
1221 	set: function(m) {
1222 		if( m === undefined ) {
1223 			/**Matrix3 that stores the transformation.
1224 			 * @type Matrix3 */
1225 			this.matrix = new Matrix3();
1226 			/**Matrix3 that stores the inverse transformation.
1227 			 * @type Matrix3 */
1228 			this.inverse = new Matrix3();
1229 		}else{
1230 			this.matrix = new Matrix3(m);
1231 			this.inverse = this.matrix.copy().invert();
1232 		}
1233 		return this;
1234 	},
1235 	/**Reset the current matrix to identity.
1236 	 *  @returns {BiTran2}
1237 	 */
1238 	reset: function() {
1239 		return this.set();
1240 	},
1241 	/** Create and return a copy of this matrix.*/
1242 	copy: function() {
1243 		return new BiTran2(this.matrix);
1244 	},
1245 	/** Apply translation (in-place) and return this instance.*/
1246 	translate: function(dx, dy) {
1247 		/* TODO: optimize
1248 		 * for last column = [0, 0, 1] this simplifies to
1249 		 *   this.m[6] += dx;
1250 		 *   this.m[7] += dy;
1251 		 */
1252 		this.matrix.translate(dx, dy);
1253 		// TODO: pre-concatenate the transformation inline.
1254 		this.inverse = this.matrix.copy().invert();
1255 		return this;
1256 	},
1257 	/** Apply scaling (in-place) and return this instance.*/
1258 	scale: function(fx, fy) {
1259 		this.matrix.scale(fx, fy);
1260 		// TODO: pre-concatenate the transformation inline.
1261 		this.inverse = this.matrix.copy().invert();
1262 		return this;
1263 	},
1264 	/** Apply rotation (in-place) and return this instance.*/
1265 	rotate: function(a, pt) {
1266 		this.matrix.rotate(a, pt);
1267 		// TODO: pre-concatenate the transformation inline.
1268 		this.inverse = this.matrix.copy().invert();
1269 		return this;
1270 	},
1271 	/** Apply transformation (in-place) and return this instance.*/
1272 	mult: function(mb) {
1273 		this.matrix.mult(mb);
1274 		// TODO: pre-concatenate the transformation inline.
1275 		this.inverse = this.matrix.copy().invert();
1276 		return this;
1277 	},
1278 	__lastEntry: undefined
1279 };
1280 
1281 
1282 /******************************************************************************/
1283 
1284 
1285 /**
1286  * Create a new 2d polygon.
1287  * @constructor
1288  * @param {Polygon2|float[]} xyList
1289  */
1290 Polygon2 = function(xyList){
1291 	this.set(xyList);
1292 };
1293 Polygon2.prototype = {
1294 	set: function(xyList){
1295 		if( xyList.length !== undefined) {
1296 			this.xyList = xyList.slice(0, xyList.length);
1297 		}else{
1298 			this.xyList = xyList.xyList.slice(0, xyList.xyList.length);
1299 		}
1300 	},
1301 	/** Return string representation '[(x1,y1), (x2,y2), ...]'.*/
1302 	toString: function(prec) {
1303 		var xy = this.xyList;
1304 		var l = [];
1305 		for(var i=0; i<xy.length; i+=2){
1306 			if(prec !== undefined){
1307 //				return "(" + this.x.toPrecision(prec) + "/" + this.y.toPrecision(prec)  + ")";
1308 				l.push("("+xy[i].toPrecision(prec)+"/"+xy[i+1].toPrecision(prec)+")");
1309 			}else{
1310 				l.push("("+xy[i]+"/"+xy[i+1]+")");
1311 			}
1312 		}
1313 		return "[" + l.join(", ") + "]";
1314 	},
1315 	/** Create and return a copy of this polygon.*/
1316 	copy: function() {
1317 		return new Polygon2(this.xyList);
1318 	},
1319 	/** Apply transformation matrix (in-place) and return this instance.*/
1320 	transform: function(m) {
1321 		var xy = this.xyList;
1322 		for(var i=0; i<xy.length; i+=2){
1323 			pt2 = m.transformPt(xy[i], xy[i+1]);
1324 			xy[i] = pt2.x;
1325 			xy[i+1] = pt2.y;
1326 		}
1327 		return this;
1328 	},
1329 	/** Revert vertex list (in-place) and return this instance.*/
1330 	revert: function() {
1331 		var xy = this.xyList, t;
1332 		var len = xy.length;
1333 		for(var i=0; i<(len-1)/2; i+=2){
1334 			var j = len - i - 2;
1335 			t = xy[i]; xy[i] = xy[j]; xy[j] = t;
1336 			t = xy[i+1]; xy[i+1] = xy[j+1]; xy[j+1] = t;
1337 		}
1338 		return this;
1339 	},
1340 	/**Return polygon point by index.
1341 	 * @param {int} idx
1342 	 * @returns {x:_, y:_}
1343 	 */
1344 	getXY: function(idx) {
1345 		idx *= 2;
1346 		if(idx > this.xyList.length-2){
1347 			throw("Polygon2.getXY: Index out of bounds");
1348 		}
1349 		return {x: this.xyList[idx], y: this.xyList[idx+1]};
1350 	},
1351 	/**Return polygon point by index.
1352 	 * @param {int} idx
1353 	 * @returns Point2
1354 	 */
1355 	getPoint: function(idx) {
1356 		idx *= 2;
1357 		if(idx > this.xyList.length-2){
1358 			throw("Polygon2.getPoint: Index out of bounds");
1359 		}
1360 		return new Point2(this.xyList[idx], this.xyList[idx+1]);
1361 	},
1362 	/**Return polygon edge by index.
1363 	 * If idx == last then the closing edge is returned.
1364 	 * @param {int} idx Index of first point
1365 	 * @returns {x0:_, y0:_, x1:_, y1:_}
1366 	 */
1367 	getSegment: function(idx0) {
1368 		idx0 *= 2;
1369 		if(idx0 >= this.xyList.length){
1370 			throw("Polygon2.getSegment: Index out of bounds");
1371 		}
1372 		var idx1 = (idx0 + 2) % this.xyList.length;
1373 		return {x0: this.xyList[idx0], y0: this.xyList[idx0+1],
1374 				x1: this.xyList[idx1], y1: this.xyList[idx1+1]};
1375 	},
1376 	/**Check, if pt is inside this polygon.
1377 	 * @param pt
1378 	 */
1379 	contains: function(pt) {
1380 		// Check if pt is on the same side of all PG edges.
1381 		// TODO: this only works for convex PGs(?)
1382 		// Ray-testing may be better:
1383 		// see http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
1384 		// and http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test
1385 		// for a better solution
1386 		/*
1387 		 int pnpoly(int npol, float *xp, float *yp, float x, float y)
1388 		{
1389 		  int i, j, c = 0;
1390 		  for (i = 0, j = npol-1; i < npol; j = i++) {
1391 			if ((((yp[i] <= y) && (y < yp[j])) ||
1392 				 ((yp[j] <= y) && (y < yp[i]))) &&
1393 				(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
1394 			  c = !c;
1395 		  }
1396 		  return c;
1397 		}
1398 
1399 		 */
1400 		var x = pt.x,
1401 			y = pt.y,
1402 			sign, // >0: pt is on the left of a segment
1403 			pt0, pt1,
1404 			xy = this.xyList,
1405 			len = xy.length;
1406 		// sign = (y - y0)*(x1 - x0) - (x - x0)*(y1 - y0)
1407 		// Start with last (closing) segment
1408 		pt0 = {x: xy[len-2], y: xy[len-1]};
1409 		for(var i=0; i<=len-2; i+=2){
1410 			pt1 = {x: xy[i], y: xy[i+1]};
1411 			var s = (y - pt0.y) * (pt1.x - pt0.x) - (x - pt0.x) * (pt1.y - pt0.y);
1412 			if( s === 0){
1413 				return true;
1414 			} else if( sign === undefined){
1415 				sign = (s > 0);
1416 			} else if( (s>0) !== sign ) {
1417 				return false;
1418 			}
1419 			pt0 = pt1;
1420 		}
1421 		return true;
1422 	},
1423 	/** Check, if this polygon intersects with another polygon.
1424 	 */
1425 	intersects: function(pg2, velocity, time) {
1426 		// TODO:
1427 		// See http://gpwiki.org
1428 		// 'Simple non-convex polygons'
1429 		alert("Not implemented: Polygon2.intersects()");
1430 		return false;
1431 	},
1432 	/** Find index of point with minimmum y coord (and minimum x, if multiple
1433 	 *  matches found).
1434 	 */
1435 	indexOfLowestPoint: function() {
1436 		var iMin = 0,
1437 			xy = this.xyList,
1438 			len = xy.length,
1439 			xyMin = this.getXY(0);
1440 		for(var i=2; i<len-1; i+=2){
1441 			if(xy[i+1] < xyMin.y || (xy[i+1] === xyMin.y && xy[i] < xyMin.x)){
1442 				iMin = i / 2;
1443 				xyMin = this.getXY(iMin);
1444 			}
1445 		}
1446 		return iMin;
1447 	},
1448 	/**Return polygon point nearest to pt.
1449 	 * @param {Point2} pt
1450 	 * @param {Vec2} cullingVector (optional) If we pass a velocity vector here,
1451 	 * CCW oriented polygons will only consider objects aproaching from the
1452 	 * outside.
1453 	 */
1454 	nearestPt: function(pt, cullingVector) {
1455 		var xy = this.xyList,
1456 			len = xy.length,
1457 			dmin2 = Number.MAX_VALUE,
1458 			d2,
1459 			ptNearest = {x:0, y:0},
1460 			ptA, ptB,
1461 			vAB, vAP,
1462 			e2, t, dx, dy;
1463 		var res = {d: 0,
1464 				pt: {},
1465 				i: 0,
1466 				t: 0};
1467 		// Start with last (closing) segment
1468 		ptA = {x: xy[len-2], y: xy[len-1]};
1469 		for(var i=0; i<=len-2; i+=2){
1470 			ptB = {x: xy[i], y: xy[i+1]};
1471 			vAB = new Vec2(ptB.x - ptA.x, ptB.y - ptA.y);
1472 			if(cullingVector && cullingVector.cross(vAB) < 0){
1473 				//window.console.log(cullingVector.dot(vAB));
1474 				ptA = ptB;
1475 				continue;
1476 			}
1477 			vAP = new Vec2(pt.x - ptA.x, pt.y - ptA.y);
1478 
1479 			e2 = vAB.dot(vAB);
1480 			t = vAP.dot(vAB) / e2;
1481 			if(t <= 0) {//LinaJS.EPS){ // TODO: <= EPS or 0.0?
1482 				// Hit in ptA
1483 				d2 = vAP.dx * vAP.dx + vAP.dy * vAP.dy;
1484 				if( d2 < dmin2 ){
1485 					dmin2 = d2;
1486 					res.idx = i;
1487 					res.t = 0;
1488 					res.pt.x = ptA.x;
1489 					res.pt.y = ptA.y;
1490 					res.isCorner = true;
1491 				}
1492 			} else if(t >= 1.0) {
1493 				// Hit in ptB: this will become ptA in the next loop
1494 			} else {
1495 				ptNearest.x = ptA.x + t * vAB.dx;
1496 				ptNearest.y = ptA.y + t * vAB.dy;
1497 				dx = ptNearest.x - pt.x;
1498 				dy = ptNearest.y - pt.y;
1499 				d2 = dx * dx + dy * dy;
1500 				if( d2 < dmin2 ){
1501 					dmin2 = d2;
1502 					res.idx = i;
1503 					res.t = t;
1504 					res.pt.x = ptNearest.x;
1505 					res.pt.y = ptNearest.y;
1506 					res.isCorner = false;
1507 				}
1508 			}
1509 			ptA = ptB;
1510 		}
1511 		// Fixup result to use Lina objects and real distance
1512 		res.d = Math.sqrt(dmin2);
1513 		res.pt = new Point2(res.pt);
1514 		return res;
1515 	},
1516 	/**Check, if this polygon intersects with a (moving) circle.
1517 	 * In case of a collision some additional information is calculated.
1518 	 * @param {Circle2} circle
1519 	 * @param {Vec2} velocity Relative speed in units per second (assuming this polygon is static)
1520 	 * @param {float} time seconds to look ahead (e.g. 1/30s for one frame step). Default: 1
1521 	 * @returns false, if no intersection, otherwise {...}
1522 	 */
1523 	intersectsCircle: function(circle, velocity, time) {
1524 		// TODO: handle velocity (0,0)
1525 		time = time || 1.0;
1526 		var vStep = velocity.copy().scale(time);
1527 		// Find point on polygon that is closest to circle.center.
1528 		// We pass the velocity vector as culling, so CCW polygons will only
1529 		// report collisions from the outside.
1530 		var nearest = this.nearestPt(circle.center, vStep);
1531 		if( nearest.d > circle.r ){
1532 			return false;
1533 		}
1534 		// penetration depth
1535 		var depth = circle.r - nearest.d;
1536 		// Collision normal
1537 		var vNormal = nearest.pt.vectorTo(circle.center).normalize();
1538 		// Reflected velocity
1539 		var vEdge = vNormal.copy().perp();
1540 		var a = vEdge.dot(vStep);
1541 		var b = vNormal.dot(vStep);
1542 		var velocityReflected = vNormal.copy().scale(-b).add(vEdge.scale(a));
1543 		// [0..1]: fraction of velocity after collision
1544 		var tAfter = depth / vStep.length();
1545 		var centerReflected = circle.center.copy()
1546 			.translate((tAfter-1) * vStep.dx + tAfter * velocityReflected.dx,
1547 					(tAfter-1) * vStep.dy + tAfter * velocityReflected.dy);
1548 		// Rescale velocity to units per second
1549 		velocityReflected.scale(1.0 / time);
1550 		// TODO: nearestPt should ignore edges if velocity is outbound
1551 		return {
1552 			pt: nearest.pt, // collsion point
1553 			ptIdx: nearest.i, // index of first point of collision edge (ptA)
1554 			edgeT: nearest.t, // [0..1]: pt = ptA + edgeT * (ptB - ptA)
1555 			vNormal: vNormal, // collision normal (unit vector)
1556 			vMTD: vNormal.copy().scale(depth), // minmum offset vector that translates circle to point of collision
1557 			depth: depth, // penetration depth
1558 			velocityReflected: velocityReflected, // new velocity, assuming a reflection on collision edge
1559 			centerReflected: centerReflected, // new circle pos, assuming a reflection on collision edge
1560 			t: 1-tAfter // [0..1]: fraction of velocity before collision
1561 		};
1562 	},
1563 	/** Check, if line segment pt1, pt2 is inside this polygon.*/
1564 	segmentIntersects: function(pt1, pt2) {
1565 		// TODO: Gems II, 1.2 and page 473
1566 		// See http://gpwiki.org
1567 		// 'Simple non-convex polygons'
1568 		alert("Not implemented: Polygon2.segmentIntersects()");
1569 		return false;
1570 	},
1571 	/** @private */
1572 	_signedDoubleArea: function() {
1573 		var xy = this.xyList;
1574 		var res = 0;
1575 		for(var i=0; i<xy.length-3; i+=2){
1576 			res += xy[i]*xy[i+3] - xy[i+1]*xy[i+2];
1577 		}
1578 		return res;
1579 	},
1580 	/** Return polygons area.
1581 	 * This assumes an implicitly closed, non self-intersecting polygon.
1582 	 */
1583 	area: function() {
1584 		return 0.5 * Math.abs(this._signedDoubleArea());
1585 	},
1586 	/** Check, if this polygon has a counterclocwise vertex order.*/
1587 	isCCW: function() {
1588 		return this._signedDoubleArea() > 0;
1589 	},
1590 	/** Make sure this polygon has a counterclocwise vertex order.*/
1591 	makeCCW: function() {
1592 		return this.isCCW() ? this : this.revert();
1593 	},
1594 	/** Make sure this polygon has a clocwise vertex order.*/
1595 	makeCW: function() {
1596 		return this.isCCW() ? this.revert() : this;
1597 	},
1598 	/**Reorder polygon to start with given index.
1599 	 * @param {int} idx
1600 	 * @returns this
1601 	 */
1602 	makeFirst: function(idx) {
1603 		alert("Not implemented: Polygon2.makeFirst()");
1604 	},
1605 	/**Append a point or polygon.
1606 	 * @param {Point2, Polygon2, float[]} ptOrPg
1607 	 * @returns this
1608 	 */
1609 	append: function(ptOrPg) {
1610 		if(ptOrPg.xyList !== undefined){
1611 			this.xyList = this.xyList.concat(ptOrPg.xyList);
1612 		}else if(ptOrPg.length !== undefined){
1613 			this.xyList = this.xyList.concat(ptOrPg);
1614 		} else {
1615 //			this.xyList = this.xyList.concat([ptOrPg.x, ptOrPg.y]);
1616 			this.xyList.push(ptOrPg.x);
1617 			this.xyList.push(ptOrPg.y);
1618 		}
1619 		return this;
1620 	},
1621 	/**Append a point or polygon, discarding duplicate points.
1622 	 * @param {Point2, Polygon2, float[]} ptOrPg
1623 	 * @param {float} eps (optional) defaults to LinaJS.EPS
1624 	 * @returns this
1625 	 */
1626 	appendUnique: function(ptOrPg, eps) {
1627 		var arr = (ptOrPg.length !== undefined) ? ptOrPg : ptOrPg.xyList,
1628 //			arrLen = arr.length,
1629 			xy, l, i, j;
1630 		// Add point list
1631 		if(arr !== undefined){
1632 			l = arr.length;
1633 			eps = (eps === undefined) ? LinaJS.EPS : eps; // Default, if undefined
1634 			for(i=0; i<l-3; i+=2){
1635 				this.appendUnique({x: arr[i], y: arr[i+1]}, eps);
1636 			}
1637 			return this;
1638 		}
1639 		// Adding a single point
1640 		xy = this.xyList;
1641 		l = xy.length;
1642 		if(eps === 0){
1643 			// TODO: reverse loop and use -- for speed improvement
1644 			for(i=0; i<l-3; i+=2){
1645 				if(Math.abs(xy[i] - ptOrPg.x) <= eps && Math.abs(xy[i+1] - ptOrPg.y) <= eps){
1646 					return this;
1647 				}
1648 			}
1649 		}else{
1650 			eps = eps || LinaJS.EPS; // Default, if undefined
1651 			for(i=0; i<l-3; i+=2){
1652 				if(Math.abs(xy[i] - ptOrPg.x) <= eps && Math.abs(xy[i+1] - ptOrPg.y) <= eps){
1653 					return this;
1654 				}
1655 			}
1656 		}
1657 		xy.push(ptOrPg.x);
1658 		xy.push(ptOrPg.y);
1659 		return this;
1660 	},
1661 	/**Return a copy with duplicate points removed.
1662 	 * @param {float} eps (optional) defaults to LinaJS.EPS
1663 	 * @returns new Polygon2
1664 	 */
1665 	getUniquePoints: function(eps) {
1666 		return new Polygon2([]).appendUnique(this.xyList, eps);
1667 	},
1668 	/**Remove point at index.
1669 	 * @param {int} idx
1670 	 * @returns this
1671 	 */
1672 	remove: function(idx) {
1673 		alert("Not implemented: Polygon2.remove()");
1674 		return this;
1675 	},
1676 	/**Exchange points.
1677 	 * @param {int} idx
1678 	 * @returns this
1679 	 */
1680 	swap: function(idx1, idx2) {
1681 		if(idx1 !== idx2){
1682 			idx1 *= 2;
1683 			idx2 *= 2;
1684 			var xy = this.xyList,
1685 				x = xy[idx1],
1686 				y = xy[idx1+1];
1687 			xy[idx1] = xy[idx2];  xy[idx1+1] = xy[idx2+1];
1688 			xy[idx2] = x;  xy[idx2+1] = y;
1689 		}
1690 		return this;
1691 	},
1692 	/**Return number of points.
1693 	 */
1694 	count: function() {
1695 		return this.xyList.length / 2;
1696 	},
1697 	/**Set maximum number of points (truncating trailing points).
1698 	 */
1699 	setCount: function(n) {
1700 		if(n > this.count()){
1701 			throw "n must be <= count";
1702 		}
1703 		this.xyList = this.xyList.slice(0, 2*n);
1704 		return this;
1705 	},
1706 	/** Return the smallest bounding circle.*/
1707 	getBoundingCircle: function() {
1708 		// TODO: Gems II, 1.4
1709 		alert("Not implemented: Polygon2.getBoundingCircle()");
1710 		return 0;
1711 	},
1712 	/**Return the total length of all line segments.
1713 	 * @param {boolean} closed Include implicit closing segment (default: true).
1714 	 */
1715 	perimeter: function(closed) {
1716 		// TODO:
1717 		closed = (closed === undefined) ? true : !!closed;
1718 		alert("Not implemented: Polygon2.perimeter()");
1719 		return 0;
1720 	},
1721 	/** Return the bounding box as {min: {x:_,y:_}, max: {x:_,y:_}}.*/
1722 	getBoundingBox: function(forceRecalc) {
1723 		// TODO:
1724 		alert("Not implemented: Polygon2.getBoundingBox()");
1725 		return 0;
1726 	},
1727 	/** Return a new polygon that connects the extreme points of this polygon.
1728 	 *
1729 	 * The result will be convex, non-intersecting.
1730 	 * This bounding polygon has typically less points, and my be used for faster
1731 	 * collision testing.
1732 	 * This polygon is treated as unconnected point cloud, so it is possible to
1733 	 * get a bounding polygon of multiple objects like this:
1734 	 * @example
1735 	 * var pgHull = pg1.copy().append(pg2).append(pg3).getConvexHull();
1736 	 */
1737 	getConvexHull: function() {
1738 		// Do the Jarvis-March:
1739 		// http://www.inf.fh-flensburg.de/lang/algorithmen/geo/jarvis.htm
1740 		var pg = this.getUniquePoints(LinaJS.eps),
1741 			xy = pg.xyList,
1742 			i,
1743 			h = 0;
1744 		if( pg.count() <= 3 ){
1745 			return pg;
1746 		}
1747 //		window.console.log("PG: ", this);
1748 //		window.console.log("PG unique: ", pg);
1749 		var _indexOfRightmostPointFrom = function(idx){
1750 			// Check
1751 			var pt0 = pg.getPoint(idx),
1752 				v0 = (idx === 0) ? new Vec2(1, 0) : pg.getPoint(idx-1).vectorTo(pt0),
1753 				n = pg.count(),
1754 				nLast = (idx === 0) ? n : n + 1,
1755 				iBest = -1,
1756 				lBest = 0,
1757 				aBest = 1000,
1758 				pt, a, l, i;
1759 //			window.console.log("indexOfRightmostPointFrom(" + idx + ") -> " + pt0.toString(1));
1760 //			window.console.log("    v0:" + v0);
1761 
1762 			for(i=idx+1; i<nLast; i++){
1763 				pt =  pg.getPoint(i % n);
1764 				v = pt0.vectorTo(pt);
1765 				a = LinaJS.normAngle(v0.angleTo(v));
1766 				l = v.length();
1767 //				window.console.log("    vectorTo #" + i + " -> " + pt.toString(1) + ", v=" + v.toString(1) + ": " + a*LinaJS.R2D, "� l=", l);
1768 				if(l > LinaJS.EPS && (a < aBest || (a === aBest && l > lBest))){
1769 //					window.console.log("    -> is best!");
1770 					iBest = i % n;
1771 					aBest = a;
1772 					lBest = l;
1773 				}
1774 			}
1775 //			window.console.log("iBest=", iBest);
1776 			return iBest;
1777 		};
1778 		// The lowest point must be member of the convex hull, so we make it
1779 		// start (and end) point
1780 		i = this.indexOfLowestPoint();
1781 //		window.console.log("lowest idx=" + i + ", pg:", pg.toString(1));
1782 		do{
1783 			pg.swap(h, i);
1784 //			window.console.log("swapped", h, i, " -> ", pg.toString(1));
1785 			i = _indexOfRightmostPointFrom(h);
1786 			h += 1;
1787 		} while(i > 0);
1788 //		window.console.log("hull:", pg.toString(1));
1789 		pg.setCount(h);
1790 //		window.console.log("hull 2:", pg.toString(1));
1791 		return pg;
1792 	},
1793 	/** Return a new polygon that draws along the outer lines of this polygon.*/
1794 	getShapePolygon: function() {
1795 		// TODO:
1796 		alert("Not implemented: Polygon2.getShapePolygon()");
1797 		return null;
1798 	},
1799 	__lastEntry: undefined
1800 };
1801 
1802 /** Return a transformed copy of a polygon.*/
1803 Polygon2.transform = function(pg, m) {
1804 	return pg.copy().transform(m);
1805 };
1806 /** Return a reverse copy of a polygon.*/
1807 Polygon2.revert = function(pg) {
1808 	return pg.copy().revert();
1809 };
1810 
1811 /**
1812  * Create a new circle.
1813  * @constructor
1814  * @param {Point2} center
1815  * @param {float} r radius
1816  */
1817 Circle2 = function(center, radius){
1818 	this.set(center, radius);
1819 };
1820 Circle2.prototype = {
1821 	set: function(center, r){
1822 		if(center.center !== undefined){
1823 			this.center = new Point2(center.center);
1824 			this.r = center.r;
1825 		}else{
1826 			this.center = new Point2(center);
1827 			this.r = +r;
1828 		}
1829 	},
1830 	/** Return string representation 'Circle2((x,y), r=_)'.*/
1831 	toString: function() {
1832 		return "Circle2(" + this.center + ", r:" + this.r + ")";
1833 	},
1834 	/** Create and return a copy of this circle.*/
1835 	copy: function() {
1836 		return new Circle2(this);
1837 	},
1838 	/** Apply transformation matrix (in-place) and return this instance.*/
1839 	transform: function(m) {
1840 		this.center.transform(m);
1841 		// FIXME: transform radius too
1842 		return this;
1843 	},
1844 	/**Check, if pt is inside this polygon.
1845 	 * @param pt
1846 	 */
1847 	contains: function(pt) {
1848 		return this.center.distanceTo(pt) < this.r;
1849 	},
1850 //	/** Return polygon point nearest to pt.
1851 //	 */
1852 //	nearestPt: function(pt) {
1853 //		// TODO:
1854 //		alert("Not implemented: Circle2.intersects()");
1855 //	},
1856 	/**Check, if this circle intersects with another (moving) circle.
1857 	 * Return false, if ther is no intersection within the current time frame.
1858 	 * Otherwise return a dictionary with additional infos.
1859 	 * @param {Circle2} circle2
1860 	 * @param {Vec2} velocity Speed of this circle in units per second.
1861 	 * @param {Vec2} velocity2 Speed of circle2 in units per second.
1862 	 * @param {float} time seconds to look ahead (e.g. 1/30s for one frame step). Default: 1
1863 	 */
1864 	intersectsCircle: function(circle2, velocity, velocity2, time) {
1865 		// TODO: handle velocity (0,0)
1866 		time = time || 1.0;
1867 		var vStep = velocity.copy().scale(time),
1868 			vStep2 = velocity2.copy().scale(time);
1869 		var c1 = { x: this.center.x,
1870 				   y: this.center.y,
1871 				   r: this.r,
1872 				   vx: velocity ? vStep.dx : 0,
1873 				   vy: velocity ? vStep.dy : 0};
1874 		var c2 = { x: circle2.center.x,
1875 				   y: circle2.center.y,
1876 				   r: circle2.r,
1877 				   vx: velocity2 ? vStep2.dx : 0,
1878 				   vy: velocity2 ? vStep2.dy : 0};
1879 		var coll = LinaJS.intersectMovingCircles(c1, c2);
1880 		if(!coll || coll.t < -1 || coll.t > 0){
1881 			return false; // Intersection happens before prev. frame or in the future
1882 		}
1883 		// Calculate centers at the time when the collision occurred
1884 		var tBefore = - coll.t;
1885 		var tAfter = coll.t + 1;
1886 		coll.t = tBefore;
1887 		var vMTD1 = vStep.copy().scale(-tBefore);
1888 		coll.center1 = this.center.copy().translate(vMTD1);
1889 		var vMTD2 = vStep2.copy().scale(-tBefore);
1890 		coll.center2 = circle2.center.copy().translate(vMTD2);
1891 		// Collision normal is always along the two circle centers
1892 		coll.vNormal = coll.center2.vectorTo(coll.center1).normalize();
1893 		// Relative speed from circle towards circle2
1894 		var vRel = vStep.copy().sub(vStep2);
1895 		// split relative speed into a part along collision normal and the rest
1896 		var c = coll.vNormal.dot(vRel);
1897 		var vColl = coll.vNormal.copy().scale(c);
1898 		var vPerp = vRel.copy().sub(vColl);
1899 		// Total inelastic collision: circle1 transfers it's energy to circle2
1900 		coll.velocityReflected1 = vPerp;
1901 		coll.velocityReflected2 = vStep2.copy().add(vColl);
1902 //		var e1 = velocity.length() + velocity2.length();
1903 //		var e2 = coll.velocityReflected1.length() + coll.velocityReflected2.length();
1904 //		if(Math.abs(e1-e2) > LinaJS.EPS){
1905 //			window.console.log("e1:"+e1+", e2:"+e2);
1906 //			window.console.log("vColl:"+vColl);
1907 //		}
1908 		// Calculate circle positions at t=1, assuming a total reflection
1909 		coll.centerReflected1 = coll.center1.copy()
1910 			.translate(tAfter * coll.velocityReflected1.dx,
1911 					   tAfter * coll.velocityReflected1.dy);
1912 		coll.centerReflected2 = coll.center2.copy()
1913 			.translate(tAfter * coll.velocityReflected2.dx,
1914 					   tAfter * coll.velocityReflected2.dy);
1915 
1916 		// Rescale velocities to units per second
1917 		coll.velocityReflected1.scale(1.0 / time);
1918 		coll.velocityReflected2.scale(1.0 / time);
1919 		return coll;
1920 	},
1921 	/** Return circle area (Pi*r^2).
1922 	 * This assumes an implicitly closed, non self-intersecting polygon.
1923 	 */
1924 	area: function() {
1925 		return Math.PI * this.r * this.r;
1926 	},
1927 	/**Return the circumference (2*Pi*r).
1928 	 * @param {boolean} closed Include implicit closing segment (default: true).
1929 	 */
1930 	perimeter: function() {
1931 		return 2 * Math.PI * this.r;
1932 	},
1933 	__lastEntry: undefined
1934 };
1935 
1936 /** Return a transformed copy of a cirlcle.*/
1937 Circle2.transform = function(circle, m) {
1938 	return circle.copy().transform(m);
1939 };
1940