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