1 /**
  2  * The Render Engine
  3  * Math2D
  4  *
  5  * @fileoverview A static 2D math library with several helper methods.
  6  *
  7  * @author: Brett Fattori (brettf@renderengine.com)
  8  * @author: $Author: bfattori@gmail.com $
  9  * @version: $Revision: 1570 $
 10  *
 11  * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com)
 12  *
 13  * Permission is hereby granted, free of charge, to any person obtaining a copy
 14  * of this software and associated documentation files (the "Software"), to deal
 15  * in the Software without restriction, including without limitation the rights
 16  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 17  * copies of the Software, and to permit persons to whom the Software is
 18  * furnished to do so, subject to the following conditions:
 19  *
 20  * The above copyright notice and this permission notice shall be included in
 21  * all copies or substantial portions of the Software.
 22  *
 23  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 24  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 25  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 26  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 27  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 28  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 29  * THE SOFTWARE.
 30  *
 31  */
 32 "use strict";
 33 
 34 // The class this file defines and its required classes
 35 R.Engine.define({
 36     "class":"R.math.Math2D",
 37     "requires":[
 38         "R.math.Rectangle2D",
 39         "R.math.Point2D",
 40         "R.math.Vector2D"
 41     ],
 42 
 43     "includes":[
 44         "/../engine/libs/sylvester.js"
 45     ]
 46 });
 47 
 48 /**
 49  * Bin object used by convex hull method.
 50  * @private
 51  */
 52 var Bin = Base.extend({
 53     B:null,
 54     constructor:function (size) {
 55         this.B = [];
 56         for (var i = 0; i < size; i++) {
 57             this.B.push({
 58                 min:0,
 59                 max:0
 60             });
 61         }
 62     }
 63 });
 64 
 65 /**
 66  * @class A static class with methods and fields that are helpful
 67  * when dealing with two dimensional mathematics.
 68  *
 69  * @static
 70  */
 71 R.math.Math2D = /** @scope R.math.Math2D.prototype */{
 72 
 73     /**
 74      * An approximation of PI (3.14159)
 75      * @type {Number}
 76      */
 77     PI:3.14159,
 78 
 79     /**
 80      * An approximation of PI*2 (6.28318)
 81      * @type {Number}
 82      */
 83     TWO_PI:6.28318,
 84 
 85     /**
 86      * An approximation of the inverse of PI (0.31831)
 87      * @type {Number}
 88      */
 89     INV_PI:0.31831,
 90 
 91     /**
 92      * Convert degrees to radians.
 93      * @param degrees {Number} An angle in degrees
 94      * @return {Number} The degrees value converted to radians
 95      */
 96     degToRad:function (degrees) {
 97         return (0.01745 * degrees);
 98     },
 99 
100     /**
101      * Convert radians to degrees.
102      * @param radians {Number} An angle in radians
103      * @return {Number} The radians value converted to degrees
104      */
105     radToDeg:function (radians) {
106         return (radians * 180 / R.math.Math2D.PI);
107     },
108 
109     /**
110      * Perform AAB (axis-aligned box) to AAB collision testing, returning <tt>true</tt>
111      * if the two boxes overlap.
112      *
113      * @param box1 {R.math.Rectangle2D} The collision box of object 1
114      * @param box2 {R.math.Rectangle2D} The collision box of object 2
115      * @return {Boolean} <tt>true</tt> if the rectangles overlap
116      */
117     boxBoxCollision:function (box1, box2) {
118         return box1.isIntersecting(box2);
119     },
120 
121     /**
122      * Perform point to AAB collision, returning <code>true</code>
123      * if a collision occurs.
124      *
125      * @param box {R.math.Rectangle2D} The collision box of the object
126      * @param point {R.math.Point2D} The point to test, in world coordinates
127      * @return {Boolean} <tt>true</tt> if the point is within the rectangle
128      */
129     boxPointCollision:function (box, point) {
130         return box.containsPoint(point);
131     },
132 
133     /**
134      * Check to see if a line intersects another
135      *
136      * @param p1 {R.math.Point2D} Start of line 1
137      * @param p2 {R.math.Point2D} End of line 1
138      * @param p3 {R.math.Point2D} Start of line 2
139      * @param p4 {R.math.Point2D} End of line 2
140      * @return {Boolean} <tt>true</tt> if the lines intersect
141      */
142     lineLineCollision:function (p1, p2, p3, p4) {
143         var d = ((p4.y - p3.y) * (p2.x - p1.x)) - ((p4.x - p3.x) * (p2.y - p1.y));
144         var n1 = ((p4.x - p3.x) * (p1.y - p3.y)) - ((p4.y - p3.y) * (p1.x - p3.x));
145         var n2 = ((p2.x - p1.x) * (p1.y - p3.y)) - ((p2.y - p1.y) * (p1.x - p3.x));
146 
147         if (d == 0.0) {
148             if (n1 == 0.0 && n2 == 0.0) {
149                 return false;  //COINCIDENT;
150             }
151             return false;   // PARALLEL;
152         }
153         var ua = n1 / d;
154         var ub = n2 / d;
155 
156         return (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0);
157     },
158 
159     /**
160      * Test to see if a line intersects a Rectangle.
161      *
162      * @param p1 {R.math.Point2D} The start of the line
163      * @param p2 {R.math.Point2D} The end of the line
164      * @param rect {R.math.Rectangle} The box to test against
165      * @return {Boolean} <tt>true</tt> if the line intersects the box
166      */
167     lineBoxCollision:function (p1, p2, rect) {
168         // Convert the line to a box itself and do a quick box box test
169         var lRect = R.math.Rectangle2D.create(p1.x, p1.y, p2.x - p1.x, p2.y - p1.y);
170         var coll = R.math.Math2D.boxBoxCollision(lRect, rect);
171         lRect.destroy();
172         return coll;
173     },
174 
175     /**
176      * A static method used to calculate a direction vector
177      * from a heading angle.
178      *
179      * @param origin {R.math.Point2D} The origin of the shape
180      * @param baseVec {R.math.Vector2D} The base vector
181      * @param angle {Number} The rotation in degrees
182      * @param [vec] {R.math.Vector2D} <i>optional</i>. If provided, the result will be stored in
183      *        this vector rather than creating a new one.
184      * @return {R.math.Vector2D} The direction vector
185      */
186     getDirectionVector:function (origin, baseVec, angle, vec) {
187         var r = R.math.Math2D.degToRad(angle);
188 
189         var x = Math.cos(r) * baseVec.x - Math.sin(r) * baseVec.y;
190         var y = Math.sin(r) * baseVec.x + Math.cos(r) * baseVec.y;
191 
192         var v = vec != null ? vec.set(x, y) : R.math.Vector2D.create(x, y);
193         return v.sub(origin).normalize();
194     },
195 
196     /**
197      * Given a {@link R.math.Rectangle2D}, generate a random point within it.
198      *
199      * @param rect {R.math.Rectangle2D} The rectangle
200      * @return {R.math.Point2D} A random point within the rectangle
201      */
202     randomPoint:function (rect) {
203         var r = rect.get();
204         return R.math.Point2D.create(Math.floor(r.x + R.lang.Math2.random() * r.w),
205             Math.floor(r.y + R.lang.Math2.random() * r.h));
206     },
207 
208     /**
209      * Returns <tt>true</tt> if the <tt>point</tt> lies on the line defined by
210      * <tt>anchor</tt> in the direction of the normalized <tt>vector</tt>.
211      *
212      * @param point {R.math.Point2D} The point to test
213      * @param anchor {R.math.Point2D} The anchor of the line
214      * @param vector {R.math.Vector2D} The normalized direction vector for the line
215      * @return {Boolean}
216      */
217     isPointOnLine:function (point, anchor, vector) {
218         var l = Line.create(anchor._vec, vector._vec);
219         return l.contains(point._vec);
220     },
221 
222 
223     /**
224      * Tests if a point is Left|On|Right of an infinite line defined by
225      * two endpoints.
226      *
227      * @param endPoint0 {R.math.Point2D} A point on the line
228      * @param endPoint1 {R.math.Point2D} A second point on the line
229      * @param testPoint {R.math.Point2D} The point to test
230      * @return {Number} <0 (to left), 0 (on), >0 (to right)
231      */
232     pointLeftOfLine:function (endPoint0, endPoint1, testPoint) {
233         var p0 = endPoint0, p1 = endPoint1, p2 = testPoint;
234         return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
235     },
236 
237     /**
238      * Calculate an approximate 2D convex hull for the given array of points.
239      * <p/>
240      * Copyright 2001, softSurfer (www.softsurfer.com)
241      * This code may be freely used and modified for any purpose
242      * providing that this copyright notice is included with it.
243      * SoftSurfer makes no warranty for this code, and cannot be held
244      * liable for any real or imagined damage resulting from its use.
245      * Users of this code must verify correctness for their application.
246      *
247      * @param pts {Array} An array of {@link R.math.Point2D} instances
248      * @param k {Number} The approximation accuracy (larger = more accurate)
249      * @return {Array} An array of {@link R.math.Point2D} which contains the
250      *     approximate hull of the given points
251      */
252     convexHull:function (pts, k) {
253 
254         var points = [];
255         for (var pz = 0; pz < pts.length; pz++) {
256             points.push(R.math.Point2D.create(pts[pz]));
257         }
258 
259         var NONE = -1;
260         var minmin = 0, minmax = 0,
261             maxmin = 0, maxmax = 0,
262             xmin = points[0].x, xmax = points[0].x,
263             cP, bot = 0, top = (-1), n = points.length, // indices for bottom and top of the stack
264             hull = [];
265 
266         // Get the points with (1) min-max x-coord, and (2) min-max y-coord
267         for (i = 1; i < n; i++) {
268             cP = points[i];
269             if (cP.x <= xmin) {
270                 if (cP.x < xmin) {        // new xmin
271                     xmin = cP.x;
272                     minmin = minmax = i;
273                 } else {                      // another xmin
274                     if (cP.y < points[minmin].y)
275                         minmin = i;
276                     else if (cP.y > points[minmax].y)
277                         minmax = i;
278                 }
279             }
280 
281             if (cP.x >= xmax) {
282                 if (cP.x > xmax) {        // new xmax
283                     xmax = cP.x;
284                     maxmin = maxmax = i;
285                 } else {                      // another xmax
286                     if (cP.y < points[maxmin].y)
287                         maxmin = i;
288                     else if (cP.y > points[maxmax].y)
289                         maxmax = i;
290                 }
291             }
292         }
293 
294         if (xmin == xmax) {      // degenerate case: all x-coords == xmin
295             hull[++top] = points[minmin];           // a point, or
296             if (minmax != minmin)           // a nontrivial segment
297                 hull[++top] = points[minmax];
298             return hull;                   // one or two points
299         }
300 
301         // Next, get the max and min points in the k range bins
302         var bin = new Bin(k + 2);   // first allocate the bins
303         bin.B[0].min = minmin;
304         bin.B[0].max = minmax;        // set bin 0
305         bin.B[k + 1].min = maxmin;
306         bin.B[k + 1].max = maxmax;      // set bin k+1
307         for (var b = 1; b <= k; b++) { // initially nothing is in the other bins
308             bin.B[b].min = bin.B[b].max = NONE;
309         }
310 
311         for (var b, i = 0; i < n; i++) {
312             var cPP = points[i];
313             cP = cPP;
314             if (cP.x == xmin || cP.x == xmax) // already have bins 0 and k+1
315                 continue;
316 
317             // check if a lower or upper point
318             if (R.math.Math2D.pointLeftOfLine(points[minmin], points[maxmin], cPP) < 0) {  // below lower line
319                 b = Math.floor((k * (cP.x - xmin) / (xmax - xmin) ) + 1);  // bin #
320                 if (bin.B[b].min == NONE)       // no min point in this range
321                     bin.B[b].min = i;           // first min
322                 else if (cP.y < points[bin.B[b].min].y)
323                     bin.B[b].min = i;           // new min
324                 continue;
325             }
326 
327             if (R.math.Math2D.pointLeftOfLine(points[minmax], points[maxmax], cPP) > 0) {  // above upper line
328                 b = Math.floor((k * (cP.x - xmin) / (xmax - xmin) ) + 1);  // bin #
329                 if (bin.B[b].max == NONE)       // no max point in this range
330                     bin.B[b].max = i;           // first max
331                 else if (cP.y > points[bin.B[b].max].y)
332                     bin.B[b].max = i;           // new max
333                 continue;
334             }
335         }
336 
337         // Now, use the chain algorithm to get the lower and upper hulls
338         // the output array hull[] will be used as the stack
339         // First, compute the lower hull on the stack hull[]
340         for (var i = 0; i <= k + 1; ++i) {
341             if (bin.B[i].min == NONE)  // no min point in this range
342                 continue;
343 
344             var cPP = points[bin.B[i].min];    // select the current min point
345             cP = cPP;
346 
347             while (top > 0) {        // there are at least 2 points on the stack
348                 // test if current point is left of the line at the stack top
349                 if (R.math.Math2D.pointLeftOfLine(hull[top - 1], hull[top], cPP) > 0)
350                     break;         // cP is a new hull vertex
351                 else
352                     top--;         // pop top point off stack
353             }
354             hull[++top] = cPP;        // push current point onto stack
355         }
356 
357         // Next, compute the upper hull on the stack H above the bottom hull
358         if (maxmax != maxmin)      // if distinct xmax points
359             hull[++top] = points[maxmax];  // push maxmax point onto stack
360 
361         bot = top;                 // the bottom point of the upper hull stack
362         for (var i = k; i >= 0; --i) {
363             if (bin.B[i].max == NONE)  // no max point in this range
364                 continue;
365 
366             var cPP = points[bin.B[i].max];   // select the current max point
367             cP = cPP;
368 
369             while (top > bot) {      // at least 2 points on the upper stack
370                 // test if current point is left of the line at the stack top
371                 if (R.math.Math2D.pointLeftOfLine(hull[top - 1], hull[top], cPP) > 0)
372                     break;         // current point is a new hull vertex
373                 else
374                     top--;         // pop top point off stack
375             }
376             hull[++top] = cPP;        // push current point onto stack
377         }
378         //if (minmax != minmin)
379         //	hull[++top] = points[minmin];  // push joining endpoint onto stack
380 
381         bin = null;                  // free bins before returning
382 
383         // See if the first and last points are identical.  This will cause a problem
384         // if the hull is used for SAT collisions.
385         if (hull[0].equals(hull[hull.length - 1])) {
386             hull.pop();
387         }
388 
389         points = null;
390         return hull;              // # of points on the stack
391     },
392 
393     /**
394      * Determine the Minkowski Difference of two convex hulls.  Useful for
395      * calculating collision response.
396      *
397      * @param hullA {Array} An array of {@link R.math.Point2D}
398      * @param hullB {Array} An array of {@link R.math.Point2D}
399      * @return {Array} An array of {@link R.math.Point2D} which are the Minkowski Difference of
400      *     the two hulls.
401      */
402     minkDiff:function (hullA, hullB) {
403         var cP = 0, minkDiff = new Array(hullA.length * hullB.length);
404         for (var a in hullA) {
405             for (var b in hullB) {
406                 var ha = hullA[a].get(), hb = hullB[b].get(),
407                     pt = R.math.Point2D.create(hb.x - ha.x, hb.y - ha.y);
408                 minkDiff[cP++] = pt;
409             }
410         }
411         return minkDiff;
412     },
413 
414     /**
415      * Helper method to determine if one circle will collide with another circle
416      * based on its direction of movement.  The circle's centers should be in
417      * world coordinates.
418      *
419      * @param circle {R.math.Circle2D} The first circle
420      * @param velocity {R.math.Vector2D} The first circle's velocity vector
421      * @param targetCircle {R.math.Circle2D} The second circle
422      * @return {R.math.Vector2D} The vector which keeps the two circles from overlapping,
423      *     or <tt>null</tt> if they cannot overlap.
424      */
425     circleCircleCollision:function (circle, velocity, targetCircle) {
426 
427         // Early out test
428         var dist = targetCircle.getCenter().dist(circle.getCenter());
429         var sumRad = targetCircle.getRadius() + circle.getRadius();
430         dist -= sumRad;
431         if (velocity.len() < dist) {
432             // No collision possible
433             return null;
434         }
435 
436         var norm = R.math.Vector2D.create(velocity).normalize();
437 
438         // Find C, the vector from the center of the moving
439         // circle A to the center of B
440         var c = R.math.Vector2D.create(targetCircle.getCenter().sub(circle.getCenter()));
441         var dot = norm.dot(c);
442 
443         // Another early escape: Make sure that A is moving
444         // towards B! If the dot product between the movevec and
445         // B.center - A.center is less that or equal to 0,
446         // A isn't isn't moving towards B
447         if (dot <= 0) {
448             norm.destroy();
449             c.destroy();
450             return null;
451         }
452 
453         var lenC = c.len();
454         var f = (lenC * lenC) - (dot * dot);
455 
456         // Escape test: if the closest that A will get to B
457         // is more than the sum of their radii, there's no
458         // way they are going collide
459         var sumRad2 = sumRad * sumRad;
460         if (f >= sumRad2) {
461             norm.destroy();
462             c.destroy();
463             return null;
464         }
465 
466         // We now have F and sumRadii, two sides of a right triangle.
467         // Use these to find the third side, sqrt(T)
468         var t = sumRad2 - f;
469 
470         // If there is no such right triangle with sides length of
471         // sumRadii and sqrt(f), T will probably be less than 0.
472         // Better to check now than perform a square root of a
473         // negative number.
474         if (t < 0) {
475             norm.destroy();
476             c.destroy();
477             return null;
478         }
479 
480         // Therefore the distance the circle has to travel along
481         // movevec is D - sqrt(T)
482         var distance = dot - Math.sqrt(t);
483 
484         // Get the magnitude of the movement vector
485         var mag = velocity.len();
486 
487         // Finally, make sure that the distance A has to move
488         // to touch B is not greater than the magnitude of the
489         // movement vector.
490         if (mag < distance) {
491             norm.destroy();
492             c.destroy();
493             return null;
494         }
495 
496         // Set the length of the vector which causes the circles
497         // to just touch
498         var moveVec = R.math.Vector2D.create(norm.mul(distance));
499         norm.destroy();
500         c.destroy();
501 
502         return moveVec;
503     },
504 
505     /**
506      * Generate an array of points which represents a regular polygon
507      * with N sides.
508      * @param sides {Number} The number of sides in the polygon, must be more than 2.
509      * @param [radius] {Number} The radius for the polygon.  Default: 100
510      * @return {Array} an array of {@link R.math.Point2D}
511      */
512     regularPolygon:function (sides, radius) {
513         Assert(sides > 2, "Math2D.regularPolygon() must be called with sides > 2");
514         radius = radius || 100;
515         var rot = R.math.Math2D.TWO_PI / sides;
516         var angle, p;
517         var points = [];
518         for (var i = 0; i < sides; i++) {
519             angle = (i * rot) + ((R.math.Math2D.PI - rot) * 0.5);
520             p = R.math.Point2D.create(Math.cos(angle) * radius, Math.sin(angle) * radius);
521             points.push(p);
522         }
523         return points;
524     },
525 
526     /**
527      * Get a point which represents the logical center of all of the
528      * given points.
529      * @param points {Array} An array of {@link R.math.Point2D}
530      * @return {R.math.Point2D}
531      */
532     getCenterOfPoints:function (points) {
533         var p = R.math.Point2D.create(0, 0);
534         for (var pt = 0; pt < points.length; pt++) {
535             p.add(points[pt]);
536         }
537         p.div(points.length);
538         return p;
539     },
540 
541     /**
542      * Calculate the smallest bounding box which contains
543      * the given set of points.
544      * @param points {Array} An array of {@link R.math.Point2D}
545      * @param [rect] {R.math.Rectangle2D} Optional rectangle to set to the bounding box
546      * @return {R.math.Rectangle2D} The bounding box of the points
547      */
548     getBoundingBox:function (points, rect) {
549         var x1 = R.lang.Math2.MAX_INT, x2 = -R.lang.Math2.MAX_INT, y1 = R.lang.Math2.MAX_INT, y2 = -R.lang.Math2.MAX_INT;
550         rect = rect || R.math.Rectangle2D.create(0, 0, 1, 1);
551 
552         for (var p = 0; p < points.length; p++) {
553             var pt = points[p];
554 
555             if (pt.x < x1) {
556                 x1 = pt.x;
557             }
558             if (pt.x > x2) {
559                 x2 = pt.x;
560             }
561             if (pt.y < y1) {
562                 y1 = pt.y;
563             }
564             if (pt.y > y2) {
565                 y2 = pt.y;
566             }
567         }
568         rect.set(0, 0, Math.abs(x1) + x2, Math.abs(y1) + y2);
569         return rect;
570     },
571 
572     /**
573      * Transform a point or an array of points by the given matrix.  This method
574      * transforms the points by mutating them.
575      * @param points {R.math.Point2D|Array} A single point or an array of {@link R.math.Point2D}
576      * @param matrix {Matrix} The matrix to transform the points with
577      */
578     transformPoints:function (points, matrix) {
579         if (points.length) {
580             for (var pt = 0; pt < points.length; pt++) {
581                 points[pt].transform(matrix);
582             }
583             return points;
584         } else {
585             return points.transform(matrix);
586         }
587     },
588 
589     /**
590      * Returns an identity matrix
591      * @return {Matrix}
592      */
593     identityMatrix:function () {
594         return $M([
595             [1, 0, 0],
596             [0, 1, 0],
597             [0, 0, 1]
598         ]);
599     },
600 
601     /**
602      * Returns a matrix which can be used to translate points by
603      * the given vector.
604      * @param vector {R.math.Vector2D} The translation vector
605      * @return {Matrix}
606      */
607     translationMatrix:function (vector) {
608         return $M([
609             [1, 0, vector.x],
610             [0, 1, vector.y],
611             [0, 0, 1]
612         ]);
613     },
614 
615     /**
616      * Returns a matrix which can be used to rotate points by
617      * the given angle.
618      * @param angle {Number} The rotation, in degrees
619      * @param [origin] {R.math.Point2D} Optional origin to rotate around
620      * @return {Matrix}
621      */
622     rotationMatrix:function (angle, origin) {
623         var rMtx;
624         if (!origin) {
625             rMtx = Matrix.Rotation(R.math.Math2D.degToRad(angle), $V([0, 0, 1]));
626         } else {
627             // Move the origin
628             rMtx = $M([
629                 [1, 0, origin.x],
630                 [0, 1, origin.y],
631                 [0, 0, 1]
632             ]);
633             // Rotate
634             rMtx = rMtx.multiply(Matrix.Rotation(R.math.Math2D.degToRad(angle), $V([0, 0, 1])));
635             // Move the origin back
636             rMtx = rMtx.multiply($M([
637                 [1, 0, -origin.x],
638                 [0, 1, -origin.y],
639                 [0, 0, 1]
640             ]));
641         }
642         return rMtx;
643     },
644 
645     /**
646      * Returns a matrix which can be used to scale points by
647      * the given amounts.  Providing neither the scale along X nor Y will
648      * return the identity matrix.
649      * @param scaleX {Number} Scale along the X axis, <tt>null</tt> for 1.0
650      * @param scaleY {Number} Scale along the Y axis, <tt>null</tt> to use the X scaling amount
651      * @return {Matrix}
652      */
653     scalingMatrix:function (scaleX, scaleY) {
654         scaleX = scaleX || 1.0;
655         scaleY = scaleY || scaleX;
656         return $M([
657             [scaleX, 0, 0],
658             [0, scaleY, 0],
659             [0, 0, 1]
660         ]);
661     },
662 
663     /**
664      * Calculates all of the points along a line using Bresenham's algorithm.
665      * This method will return an array of points which need to be cleaned up
666      * when done using them.
667      *
668      * @param start {R.math.Point2D} The starting point for the line
669      * @param end {R.math.Point2D} The ending point for the line
670      * @return {Array} An array of {@link R.math.Point2D}.  Be sure to
671      *    destroy the points in the array when done using them.
672      */
673     bresenham:function (start, end) {
674         function swap(pt) {
675             pt.set(pt.y, pt.x);
676         }
677 
678         var points = [], steep = Math.abs(end.y - start.y) > Math.abs(end.x - start.x), swapped = false;
679         if (steep) {
680             // Reflect the line
681             swap(start);
682             swap(end);
683         }
684 
685         if (start.x > end.x) {
686             // Make sure the line goes downward
687             var t = start.x;
688             start.x = end.x;
689             end.x = t;
690             t = start.y;
691             start.y = end.y;
692             end.y = t;
693             swapped = true;
694         }
695 
696         var deltax = end.x - start.x, // x slope
697             deltay = Math.abs(end.y - start.y), // y slope, positive because the lines always go down
698             error = deltax / 2, // error is used instead of tracking the y values
699             ystep, y = start.y;
700 
701         ystep = (start.y < end.y ? 1 : -1);
702         for (var x = start.x; x < end.x; x++) {   // for each point
703             if (steep) {
704                 points.push(R.math.Point2D.create(y, x));  // if it's stepp, push flipped version
705             } else {
706                 points.push(R.math.Point2D.create(x, y));  // push normal
707             }
708             error -= deltay;  // change the error
709             if (error < 0) {
710                 y += ystep;    // if the error is too much, adjust the ystep
711                 error += deltax;
712             }
713         }
714 
715         if (swapped) {
716             points.reverse();
717         }
718 
719         return points;
720     },
721 
722     /**
723      * Determine if the given <code>point</code> is within the polygon defined by the array of
724      * points in <code>poly</code>.
725      *
726      * @param point {R.math.Point2D} The point to test
727      * @param poly {Array} An array of <code>R.math.Point2D</code>
728      * @return {Boolean} <code>true</code> if the point is within the polygon
729      */
730     pointInPoly:function (point, poly) {
731         var sides = poly.length, i = 0, j = sides - 1, oddNodes = false;
732         for (i = 0; i < sides; i++) {
733             if ((poly[i].y < point.y && poly[j].y >= point.y) ||
734                 (poly[j].y < point.y && poly[i].y >= point.y)) {
735 
736                 if (poly[i].x + (point.y - poly[i].y) / (poly[j].y - poly[i].y) * (poly[j].x - poly[i].x) < point.x) {
737                     oddNodes = !oddNodes;
738                 }
739             }
740             j = i;
741         }
742         return oddNodes;
743     },
744 
745     /**
746      * Determine if the given <code>point</code> is within the circle defined by the
747      * <code>center</code> and <code>radius</code>.
748      * @param point {R.math.Point2D} The point to test
749      * @param center {R.math.Point2D} The center of the circle
750      * @param radius {Number} The radius of the circle
751      * @return {Boolean} <code>true</code> if the point is within the circle
752      */
753     pointInCircle:function (point, center, radius) {
754         // Point to circle hull test
755         var distSqr = (point.x - center.x) * (point.x - center.x) +
756             (point.y - center.y) * (point.y - center.y);
757         return (distSqr < (radius * radius));
758     }
759 
760 };
761