1 /** 2 *@namespace 3 **/ 4 var Util = { 5 /**Return the bounds for a given set of points, useful as every class uses a 6 * similar implementation. 7 *@param {Array<Point>} points - the points collected around the outside of 8 * the shape. 9 *@return {Array<Number>} - returns [minX, minY, maxX, maxY] - bounds, where 10 * all points are in the bounds. 11 *@author Maxim Georgievskiy <max.kharkov.ua@gmail.com> 12 **/ 13 getBounds:function(points){ 14 if (!points.length) 15 return null; 16 var minX = points[0].x; 17 var maxX = minX; 18 var minY = points[0].y; 19 var maxY = minY; 20 for (var i = 1; i < points.length; i++) { 21 minX = Math.min(minX, points[i].x); 22 minY = Math.min(minY, points[i].y); 23 maxX = Math.max(maxX, points[i].x); 24 maxY = Math.max(maxY, points[i].y); 25 } 26 return [minX, minY, maxX, maxY]; 27 }, 28 29 30 /***/ 31 getUnionBounds: function(shapes){ 32 //tODo 33 }, 34 35 36 /**Increase the area of a rectangle by size in any direction 37 *@param {Array} rectangle - the [topX, topY, bottomX, bottomY] 38 *@param {Number} size - the size to increase the rectangle in any direction 39 *@return {Array} - the new reactangle increased :) 40 *@author Alex Gheorghiu <alex@scriptoid.com> 41 **/ 42 feather: function(rectangle, size){ 43 return [rectangle[0] + size, rectangle[1] + size , rectangle[2] + size , rectangle[3] + size]; 44 }, 45 46 47 /**Returns the distance between 2 points 48 *@param {Point} p1 - first {Point} 49 *@param {Point} p2 - second {Point} 50 *@return {Number} - the distance between those 2 points. It is always positive. 51 *@author Alex Gheorghiu <alex@scriptoid.com> 52 **/ 53 distance: function(p1, p2){ 54 return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); 55 }, 56 57 58 round:function(number, decimals){ 59 return Math.round(number*Math.pow(10,decimals))/Math.pow(10,decimals); 60 }, 61 62 63 /**Returns the lenght between 2 points 64 *@param {Point} startPoint - one point 65 *@param {Point} endPoint - the other point 66 *@return {Number} - the distance 67 **/ 68 getLength:function(startPoint,endPoint){ 69 return Math.sqrt( Math.pow(startPoint.x-endPoint.x,2) + Math.pow(startPoint.y-endPoint.y,2) ); 70 }, 71 72 73 /**Returns the length of a Polyline that would be created with a set of points 74 *@param {Array} v - an {Array} of {Points} 75 *@return {Number} - a positive number equal with total length*/ 76 getPolylineLength:function(v){ 77 var l = 0; 78 for(var i=0;i<v.length-1; i++){ 79 l += Util.getLength(v[i], v[i+1]); 80 } 81 82 return l; 83 }, 84 85 86 /** 87 *Tests if a a line defined by 2 points intersects a rectangle 88 *@param {Point} startPoint - the starting point 89 *@param {Point} endPoint - the ending point 90 *@param {Array} bounds - the bounds of the rectangle defined by (x1, y1, x2, y2) 91 *@return true - if line intersects the rectangle, false - if not 92 *@author Alex Gheorghiu <alex@scriptoid.com> 93 **/ 94 lineIntersectsRectangle:function(startPoint, endPoint, bounds){ 95 //create the initial line/segment 96 var l = new Line(startPoint, endPoint); 97 98 //get the 4 lines/segments represented by the bounds 99 var lines = []; 100 lines.push( new Line( new Point(bounds[0], bounds[1]), new Point(bounds[2], bounds[1])) ); 101 lines.push( new Line( new Point(bounds[2], bounds[1]), new Point(bounds[2], bounds[3])) ); 102 lines.push( new Line( new Point(bounds[2], bounds[3]), new Point(bounds[0], bounds[3])) ); 103 lines.push( new Line( new Point(bounds[0], bounds[3]), new Point(bounds[0], bounds[1])) ); 104 105 //check if our line intersects any of the 4 lines 106 for(var i=0; i<lines.length; i++){ 107 if(this.lineIntersectsLine(l, lines[i])){ 108 return true; 109 } 110 } 111 112 return false; 113 }, 114 115 116 /** 117 *Test to see if 2 {Line}s intersects. They are considered finite segments 118 *and not the infinite lines from geometry 119 *@param {Line} l1 - fist line/segment 120 *@param {Line} l2 - last line/segment 121 *@return {Boolean} true - if the lines intersect or false if not 122 *@author Alex Gheorghiu <alex@scriptoid.com> 123 *@author Maxim Georgievskiy <max.kharkov.ua@gmail.com> 124 **/ 125 lineIntersectsLine: function(l1, l2){ 126 // check for two vertical lines 127 if (l1.startPoint.x == l1.endPoint.x && l2.startPoint.x == l2.endPoint.x) { 128 return l1.startPoint.x == l2.startPoint.x ? // if 'infinite 'lines do coincide, 129 // then check segment bounds for overlapping 130 l1.contains(l2.startPoint.x, l2.startPoint.y) || 131 l1.contains(l2.endPoint.x, l2.endPoint.y) : 132 // lines are paralel 133 false; 134 } 135 // if one line is vertical, and another line is not vertical 136 else if (l1.startPoint.x == l1.endPoint.x || l2.startPoint.x == l2.endPoint.x) { 137 // let assume l2 is vertical, otherwise exchange them 138 if (l1.startPoint.x == l1.endPoint.x) { 139 var l = l1; 140 l1 = l2; 141 l2 = l; 142 } 143 // finding intersection of 'infinite' lines 144 // equation of the first line is y = ax + b, second: x = c 145 var a = (l1.endPoint.y - l1.startPoint.y) / (l1.endPoint.x - l1.startPoint.x); 146 var b = l1.startPoint.y - a * l1.startPoint.x; 147 var x0 = l2.startPoint.x; 148 var y0 = a * x0 + b; 149 return l1.contains(x0, y0) && l2.contains(x0, y0); 150 } 151 152 // check normal case - both lines are not vertical 153 else { 154 //line equation is : y = a*x + b, b = y - a * x 155 var a1 = (l1.endPoint.y - l1.startPoint.y) / (l1.endPoint.x - l1.startPoint.x); 156 var b1 = l1.startPoint.y - a1 * l1.startPoint.x; 157 158 var a2 = (l2.endPoint.y - l2.startPoint.y) / (l2.endPoint.x - l2.startPoint.x); 159 var b2 = l2.startPoint.y - a2 * l2.startPoint.x; 160 161 if(a1 == a2) { //paralel lines 162 return b1 == b2 ? 163 // for coincide lines, check for segment bounds overlapping 164 l1.contains(l2.startPoint.x, l2.startPoint.y) || l1.contains(l2.endPoint.x, l2.endPoint.y) 165 : 166 // not coincide paralel lines have no chance to intersect 167 false; 168 } else { //usual case - non paralel, the 'infinite' lines intersects...we only need to know if inside the segment 169 170 /* 171 * if one of the lines are vertical, then x0 is equal to their x, 172 * otherwise: 173 * y1 = a1 * x + b1 174 * y2 = a2 * x + b2 175 * => x0 = (b2 - b1) / (a1 - a2) 176 * => y0 = a1 * x0 + b1 177 **/ 178 x0 = (b2 - b1) / (a1 - a2); 179 y0 = a1 * x0 + b1; 180 return l1.contains(x0, y0) && l2.contains(x0, y0); 181 } 182 } 183 }, 184 185 186 /** It will return the end point of a line on a given angle (clockwise). 187 * @param {Point} startPoint - the start of the line 188 * @param {Number} length - the length of the line 189 * @param {Number} angle - the angle of the line in radians 190 * @return {Point} - the endPoint of the line 191 * @autho Zack 192 */ 193 getEndPoint:function(startPoint, length, angle){ 194 var endPoint = startPoint.clone(); 195 endPoint.transform(Matrix.translationMatrix(-startPoint.x, -startPoint.y)); 196 endPoint.y -= length; 197 endPoint.transform(Matrix.rotationMatrix(angle)); 198 endPoint.transform(Matrix.translationMatrix(startPoint.x, startPoint.y)); 199 return endPoint; 200 }, 201 202 203 /** Will return the angle of rotation between 2 points, with 0 being north. 204 * Actually the angle with N on a compass 205 * @param {@link Point} centerPoint - the point that is to be considered the center of the shape 206 * @param {@link Point} outsidePoint - the point that we need to find the rotation about the center. 207 * @param {Number} round - amount to round to nearest angle (optional) 208 * @return {Number} - the angle in radians 209 * @see /documentation/specs/getAngle.png 210 * @author Alex Gheorghiu <alex@scriptoid.com> 211 * */ 212 getAngle:function(centerPoint, outsidePoint, round){ 213 centerPoint.x = Util.round(centerPoint.x, 5); 214 centerPoint.y = Util.round(centerPoint.y, 5); 215 outsidePoint.x = Util.round(outsidePoint.x, 5); 216 outsidePoint.y = Util.round(outsidePoint.y, 5); 217 var angle=Math.atan((outsidePoint.x-centerPoint.x)/(outsidePoint.y-centerPoint.y)); 218 angle=-angle; 219 220 //endAngle+=90; 221 if(outsidePoint.x>=centerPoint.x && outsidePoint.y>=centerPoint.y){ 222 angle+=Math.PI; 223 } 224 else if(outsidePoint.x<=centerPoint.x && outsidePoint.y>=centerPoint.y){ 225 angle+=Math.PI; 226 } 227 else if(outsidePoint.x<=centerPoint.x && outsidePoint.y<=centerPoint.y){ 228 angle+=Math.PI*2; 229 } 230 while(angle>=Math.PI*2){ 231 angle-=Math.PI*2; 232 } 233 if(isNaN(angle)){//Nan 234 angle=0;//we are at center point; 235 } 236 if(round){ 237 angle = Math.round(angle / round) * round 238 } 239 return angle; 240 }, 241 242 243 /** 244 *Computes the angle formed by 3 {Point}s 245 *@param {@link Point} startPoint - the start point 246 *@param {@link Point} centerPoint - the center/tid of the angle point 247 *@param {@link Point} endPoint - the end/angle point 248 *@param {Number} round - amount to round to nearest angle (optional) 249 *@author Alex Gheorghiu <alex@scriptoid.com> 250 */ 251 getAngle3Points:function(startPoint, centerPoint,endPoint, round){ 252 var a1 = Util.getAngle(centerPoint, startPoint); 253 var a2 = Util.getAngle(centerPoint, endPoint); 254 255 var angle = a2 - a1; 256 257 if(round){ 258 angle = Math.round(angle / round) * round 259 } 260 261 return angle; 262 }, 263 264 265 /** 266 /* Tests whether a point is inside the area (excluding border) determined by a set of other points. 267 * If the points is on the border of the area it will not be counted 268 * 269 * @param point {Point} the point we want to chek 270 * @param points {Array<Point>} a set of points ordered clockwise. 271 * @see <a href="http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/">http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/</a> solution 1 272 * */ 273 isPointInside:function(point, points){ 274 if(points.length < 3){ 275 return false; 276 } 277 var counter = 0; 278 var p1 = points[0]; 279 280 //calulates horizontal intersects 281 for (var i=1; i<=points.length; i++) { 282 var p2 = points[i % points.length]; 283 if (point.y > Math.min(p1.y,p2.y)) { //our point is between start(Y) and end(Y) points 284 if (point.y <= Math.max(p1.y,p2.y)) { 285 if (point.x <= Math.max(p1.x,p2.x)) { //to the left of any point 286 if (p1.y != p2.y) { //no horizontal line 287 var xinters = (point.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;//get slope of line and make it start from the same place as p1 288 if (p1.x == p2.x || point.x <= xinters){ //if vertical line or our x is before the end x of the actual line. 289 counter++; //we have an intersection 290 } 291 } 292 } 293 } 294 } 295 p1 = p2; 296 } 297 298 if (counter % 2 == 0){ 299 return false; 300 } 301 else{ 302 return true; 303 } 304 }, 305 306 307 /** 308 * Calculates the number of times the line from (x0,y0) to (x1,y1) 309 * crosses the ray extending to the right from (px,py). 310 * If the point lies on the line, then no crossings are recorded. 311 * +1 is returned for a crossing where the Y coordinate is increasing 312 * -1 is returned for a crossing where the Y coordinate is decreasing 313 */ 314 pointCrossingsForLine: function(px, py, x0, y0,x1,y1) 315 { 316 if (py < y0 && py < y1) return 0; 317 if (py >= y0 && py >= y1) return 0; 318 // assert(y0 != y1); 319 if (px >= x0 && px >= x1) return 0; 320 if (px < x0 && px < x1) return (y0 < y1) ? 1 : -1; 321 var xintercept = x0 + (py - y0) * (x1 - x0) / (y1 - y0); 322 if (px >= xintercept) return 0; 323 return (y0 < y1) ? 1 : -1; 324 }, 325 326 327 /** 328 * Calculates the number of times the cubic from (x0,y0) to (x1,y1) 329 * crosses the ray extending to the right from (px,py). 330 * If the point lies on a part of the curve, 331 * then no crossings are counted for that intersection. 332 * the level parameter should be 0 at the top-level call and will count 333 * up for each recursion level to prevent infinite recursion 334 * +1 is added for each crossing where the Y coordinate is increasing 335 * -1 is added for each crossing where the Y coordinate is decreasing 336 */ 337 pointCrossingsForCubic: function (px, py, x0, y0, xc0, yc0, xc1, yc1, x1, y1, level) 338 { 339 if (py < y0 && py < yc0 && py < yc1 && py < y1) return 0; 340 if (py >= y0 && py >= yc0 && py >= yc1 && py >= y1) return 0; 341 // Note y0 could equal yc0... 342 if (px >= x0 && px >= xc0 && px >= xc1 && px >= x1) return 0; 343 if (px < x0 && px < xc0 && px < xc1 && px < x1) { 344 if (py >= y0) { 345 if (py < y1) return 1; 346 } else { 347 // py < y0 348 if (py >= y1) return -1; 349 } 350 // py outside of y01 range, and/or y0==yc0 351 return 0; 352 } 353 // double precision only has 52 bits of mantissa 354 if (level > 52) return pointCrossingsForLine(px, py, x0, y0, x1, y1); 355 var xmid = (xc0 + xc1) / 2; 356 var ymid = (yc0 + yc1) / 2; 357 xc0 = (x0 + xc0) / 2; 358 yc0 = (y0 + yc0) / 2; 359 xc1 = (xc1 + x1) / 2; 360 yc1 = (yc1 + y1) / 2; 361 var xc0m = (xc0 + xmid) / 2; 362 var yc0m = (yc0 + ymid) / 2; 363 var xmc1 = (xmid + xc1) / 2; 364 var ymc1 = (ymid + yc1) / 2; 365 xmid = (xc0m + xmc1) / 2; 366 ymid = (yc0m + ymc1) / 2; 367 if (isNaN(xmid) || isNaN(ymid)) { 368 // [xy]mid are NaN if any of [xy]c0m or [xy]mc1 are NaN 369 // [xy]c0m or [xy]mc1 are NaN if any of [xy][c][01] are NaN 370 // These values are also NaN if opposing infinities are added 371 return 0; 372 } 373 return (Util.pointCrossingsForCubic(px, py, 374 x0, y0, xc0, yc0, 375 xc0m, yc0m, xmid, ymid, level+1) + 376 Util.pointCrossingsForCubic(px, py, 377 xmid, ymid, xmc1, ymc1, 378 xc1, yc1, x1, y1, level+1)); 379 }, 380 381 382 /**Returns the min of a vector 383 *@param {Array} v - vector of {Number}s 384 *@return {Number} - the minimum number from the vector or NaN if vector is empty 385 *@author alex@scriptoid.com 386 **/ 387 min:function(v){ 388 if(v.lenght == 0){ 389 return NaN; 390 } 391 else{ 392 var m = v[0]; 393 for(var i=0;i<v.length; i++){ 394 if(m > v[i]){ 395 m = v[i]; 396 } 397 } 398 399 return m; 400 } 401 }, 402 403 404 /**Returns the max of a vector 405 *@param {Array} v - vector of {Number}s 406 *@return {Number} - the maximum number from the vector or NaN if vector is empty 407 *@author alex@scriptoid.com 408 **/ 409 max:function(v){ 410 if(v.lenght == 0){ 411 return NaN; 412 } 413 else{ 414 var m = v[0]; 415 for(var i=0;i<v.length; i++){ 416 if(m < v[i]){ 417 m = v[i]; 418 } 419 } 420 421 return m; 422 } 423 } 424 425 426 } 427 428 /**Returns the sign of a number 429 *@param {Number} x - the number 430 *@returns {Number} 431 *@see <a href="http://en.wikipedia.org/wiki/Sign_function">http://en.wikipedia.org/wiki/Sign_function</a> 432 *@author alex@scriptoid.com 433 **/ 434 function signum(x){ 435 if(x > 0) 436 return 1; 437 else if(x < 0) 438 return -1; 439 else 440 return 0; 441 } 442 443 /** Check if a value is numeric 444 * @param {String} input - a numeric value 445 * @see <a href="http://stackoverflow.com/questions/18082/validate-numbers-in-javascript-isnumeric">http://stackoverflow.com/questions/18082/validate-numbers-in-javascript-isnumeric</a> 446 * @author Zack Newsham <zack_newsham@yahoo.co.uk> 447 * */ 448 function isNumeric(input){ 449 return (input - 0) == input && (input.length > 0 || input != ""); 450 }