addons/web_diagram/static/src/js/vec2.js

   1
   2 (function(window){
   3
   4     // A Javascript 2D vector library
   5     // conventions :
   6     // method that returns a float value do not modify the vector
   7     // method that implement operators return a new vector with the modifications without
   8     // modifying the calling vector or the parameters.
   9     //
  10     //      v3 = v1.add(v2); // v3 is set to v1 + v2, v1, v2 are not modified
  11     //
  12     // methods that take a single vector as a parameter are usually also available with
  13     // q '_xy' suffix. Those method takes two floats representing the x,y coordinates of
  14     // the vector parameter and allow you to avoid to needlessly create a vector object :
  15     //
  16     //      v2 = v1.add(new Vec2(3,4));
  17     //      v2 = v1.add_xy(3,4);             //equivalent to previous line
  18     //
  19     // angles are in radians by default but method that takes angle as parameters
  20     // or return angle values usually have a variant with a '_deg' suffix that works in degrees
  21     //
  22
  23     // The 2D vector object
  24     function Vec2(x,y){
  25         this.x = x;
  26         this.y = y;
  27     }
  28
  29     window.Vec2 = Vec2;
  30
  31     // Multiply a number expressed in radiant by rad2deg to convert it in degrees
  32     var rad2deg = 57.29577951308232;
  33     // Multiply a number expressed in degrees by deg2rad to convert it to radiant
  34     var deg2rad = 0.017453292519943295;
  35     // The numerical precision used to compare vector equality
  36     var epsilon   = 0.0000001;
  37
  38     // This static method creates a new vector from polar coordinates with the angle expressed
  39     // in degrees
  40     Vec2.new_polar_deg = function(len,angle){
  41         var v = new Vec2(len,0);
  42         return v.rotate_deg(angle);
  43     };
  44     // This static method creates a new vector from polar coordinates with the angle expressed in
  45     // radians
  46     Vec2.new_polar = function(len,angle){
  47         var v = new Vec2(len,0);
  48         v.rotate(angle);
  49         return v;
  50     };
  51     // returns the length or modulus or magnitude of the vector
  52     Vec2.prototype.len = function(){
  53         return Math.sqrt(this.x*this.x + this.y*this.y);
  54     };
  55     // returns the squared length of the vector, this method is much faster than len()
  56     Vec2.prototype.len_sq = function(){
  57         return this.x*this.x + this.y*this.y;
  58     };
  59     // return the distance between this vector and the vector v
  60     Vec2.prototype.dist = function(v){
  61         var dx = this.x - v.x;
  62         var dy = this.y - v.y;
  63         return Math.sqrt(dx*dx + dy*dy);
  64     };
  65     // return the distance between this vector and the vector of coordinates (x,y)
  66     Vec2.prototype.dist_xy = function(x,y){
  67         var dx = this.x - x;
  68         var dy = this.y - y;
  69         return Math.sqrt(dx*dx + dy*dy);
  70     };
  71     // return the squared distance between this vector and the vector and the vector v
  72     Vec2.prototype.dist_sq = function(v){
  73         var dx = this.x - v.x;
  74         var dy = this.y - v.y;
  75         return dx*dx + dy*dy;
  76     };
  77     // return the squared distance between this vector and the vector of coordinates (x,y)
  78     Vec2.prototype.dist_sq_xy = function(x,y){
  79         var dx = this.x - x;
  80         var dy = this.y - y;
  81         return dx*dx + dy*dy;
  82     };
  83     // return the dot product between this vector and the vector v
  84     Vec2.prototype.dot = function(v){
  85         return this.x*v.x + this.y*v.y;
  86     };
  87     // return the dot product between this vector and the vector of coordinate (x,y)
  88     Vec2.prototype.dot_xy = function(x,y){
  89         return this.x*x + this.y*y;
  90     };
  91     // return a new vector with the same coordinates as this
  92     Vec2.prototype.clone = function(){
  93         return new Vec2(this.x,this.y);
  94     };
  95     // return the sum of this and vector v as a new vector
  96     Vec2.prototype.add = function(v){
  97         return new Vec2(this.x+v.x,this.y+v.y);
  98     };
  99     // return the sum of this and vector (x,y) as a new vector
 100     Vec2.prototype.add_xy = function(x,y){
 101         return new Vec2(this.x+x,this.y+y);
 102     };
 103     // returns (this - v) as a new vector where v is a vector and - is the vector substraction
 104     Vec2.prototype.sub = function(v){
 105         return new Vec2(this.x-v.x,this.y-v.y);
 106     };
 107     // returns (this - (x,y)) as a new vector where - is vector substraction
 108     Vec2.prototype.sub_xy = function(x,y){
 109         return new Vec2(this.x-x,this.y-y);
 110     };
 111     // return (this * v) as a new vector where v is a vector and * is the by component product
 112     Vec2.prototype.mult = function(v){
 113         return new Vec2(this.x*v.x,this.y*v.y);
 114     };
 115     // return (this * (x,y)) as a new vector where * is the by component product
 116     Vec2.prototype.mult_xy = function(x,y){
 117         return new Vec2(this.x*x,this.y*y);
 118     };
 119     // return this scaled by float f as a new fector
 120     Vec2.prototype.scale = function(f){
 121         return new Vec2(this.x*f, this.y*f);
 122     };
 123     // return the negation of this vector
 124     Vec2.prototype.neg = function(f){
 125         return new Vec2(-this.x,-this.y);
 126     };
 127     // return this vector normalized as a new vector
 128     Vec2.prototype.normalize = function(){
 129         var len = this.len();
 130         if(len == 0){
 131             return new Vec2(0,1);
 132         }else if(len != 1){
 133             return this.scale(1.0/len);
 134         }
 135         return new Vec2(this.x,this.y);
 136     };
 137     // return a new vector with the same direction as this vector of length float l. (negative values of l will invert direction)
 138     Vec2.prototype.set_len = function(l){
 139         return this.normalize().scale(l);
 140     };
 141     // return the projection of this onto the vector v as a new vector
 142     Vec2.prototype.project = function(v){
 143         return v.set_len(this.dot(v));
 144     };
 145     // return a string representation of this vector
 146     Vec2.prototype.toString = function(){
 147         var str = "";
 148         str += "[";
 149         str += this.x;
 150         str += ",";
 151         str += this.y;
 152         str += "]";
 153         return str;
 154     };
 155     //return this vector counterclockwise rotated by rad radians as a new vector
 156     Vec2.prototype.rotate = function(rad){
 157         var c = Math.cos(rad);
 158         var s = Math.sin(rad);
 159         var px = this.x * c - this.y *s;
 160         var py = this.x * s + this.y *c;
 161         return new Vec2(px,py);
 162     };
 163     //return this vector counterclockwise rotated by deg degrees as a new vector
 164     Vec2.prototype.rotate_deg = function(deg){
 165         return this.rotate(deg * deg2rad);
 166     };
 167     //linearly interpolate this vector towards the vector v by float factor alpha.
 168     // alpha == 0 : does nothing
 169     // alpha == 1 : sets this to v
 170     Vec2.prototype.lerp = function(v,alpha){
 171         var inv_alpha = 1 - alpha;
 172         return new Vec2(    this.x * inv_alpha + v.x * alpha,
 173                             this.y * inv_alpha + v.y * alpha    );
 174     };
 175     // returns the angle between this vector and the vector (1,0) in radians
 176     Vec2.prototype.angle = function(){
 177         return Math.atan2(this.y,this.x);
 178     }
 179     // returns the angle between this vector and the vector (1,0) in degrees
 180     Vec2.prototype.angle_deg = function(){
 181         return Math.atan2(this.y,this.x) * rad2deg;
 182     };
 183     // returns true if this vector is equal to the vector v, with a tolerance defined by the epsilon module constant
 184     Vec2.prototype.equals = function(v){
 185         if(Math.abs(this.x-v.x) > epsilon){
 186             return false;
 187         }else if(Math.abs(this.y-v.y) > epsilon){
 188             return false;
 189         }
 190         return true;
 191     };
 192     // returns true if this vector is equal to the vector (x,y) with a tolerance defined by the epsilon module constant
 193     Vec2.prototype.equals_xy = function(x,y){
 194         if(Math.abs(this.x-x) > epsilon){
 195             return false;
 196         }else if(Math.abs(this.y-y) > epsilon){
 197             return false;
 198         }
 199         return true;
 200     };
 201 })(window);
 202
 203 (function(window){
 204     // A Bounding Shapes Library
 205
 206
 207     // A Bounding Ellipse
 208     // cx,cy : center of the ellipse
 209     // rx,ry : radius of the ellipse
 210     function BEllipse(cx,cy,rx,ry){
 211         this.type = 'ellipse';
 212         this.x = cx-rx;     // minimum x coordinate contained in the ellipse
 213         this.y = cy-ry;     // minimum y coordinate contained in the ellipse
 214         this.sx = 2*rx;     // width of the ellipse on the x axis
 215         this.sy = 2*ry;     // width of the ellipse on the y axis
 216         this.hx = rx;       // half of the ellipse width on the x axis
 217         this.hy = ry;       // half of the ellipse width on the y axis
 218         this.cx = cx;       // x coordinate of the ellipse center
 219         this.cy = cy;       // y coordinate of the ellipse center
 220         this.mx = cx + rx;  // maximum x coordinate contained in the ellipse
 221         this.my = cy + ry;  // maximum x coordinate contained in the ellipse
 222     }
 223     window.BEllipse = BEllipse;
 224
 225     // returns an unordered list of vector defining the positions of the intersections between the ellipse's
 226     // boundary and a line segment defined by the start and end vectors a,b
 227     BEllipse.prototype.collide_segment = function(a,b){
 228         // http://paulbourke.net/geometry/sphereline/
 229         var collisions = [];
 230
 231         if(a.equals(b)){  //we do not compute the intersection in this case. TODO ?
 232             return collisions;
 233         }
 234
 235         // make all computations in a space where the ellipse is a circle
 236         // centered on zero
 237         var c = new Vec2(this.cx,this.cy);
 238         a = a.sub(c).mult_xy(1/this.hx,1/this.hy);
 239         b = b.sub(c).mult_xy(1/this.hx,1/this.hy);
 240
 241
 242         if(a.len_sq() < 1 && b.len_sq() < 1){   //both points inside the ellipse
 243             return collisions;
 244         }
 245
 246         // compute the roots of the intersection
 247         var ab = b.sub(a);
 248         var A = (ab.x*ab.x + ab.y*ab.y);
 249         var B = 2*( ab.x*a.x + ab.y*a.y);
 250         var C = a.x*a.x + a.y*a.y - 1;
 251         var u  = B * B - 4*A*C;
 252
 253         if(u < 0){
 254             return collisions;
 255         }
 256
 257         u = Math.sqrt(u);
 258         var u1 = (-B + u) / (2*A);
 259         var u2 = (-B - u) / (2*A);
 260
 261         if(u1 >= 0 && u1 <= 1){
 262             var pos = a.add(ab.scale(u1));
 263             collisions.push(pos);
 264         }
 265         if(u1 != u2 && u2 >= 0 && u2 <= 1){
 266             var pos = a.add(ab.scale(u2));
 267             collisions.push(pos);
 268         }
 269         for(var i = 0; i < collisions.length; i++){
 270             collisions[i] = collisions[i].mult_xy(this.hx,this.hy);
 271             collisions[i] = collisions[i].add_xy(this.cx,this.cy);
 272         }
 273         return collisions;
 274     };
 275
 276     // A bounding rectangle
 277     // x,y the minimum coordinate contained in the rectangle
 278     // sx,sy the size of the rectangle along the x,y axis
 279     function BRect(x,y,sx,sy){
 280         this.type = 'rect';
 281         this.x = x;              // minimum x coordinate contained in the rectangle
 282         this.y = y;              // minimum y coordinate contained in the rectangle
 283         this.sx = sx;            // width of the rectangle on the x axis
 284         this.sy = sy;            // width of the rectangle on the y axis
 285         this.hx = sx/2;          // half of the rectangle width on the x axis
 286         this.hy = sy/2;          // half of the rectangle width on the y axis
 287         this.cx = x + this.hx;   // x coordinate of the rectangle center
 288         this.cy = y + this.hy;   // y coordinate of the rectangle center
 289         this.mx = x + sx;        // maximum x coordinate contained in the rectangle
 290         this.my = y + sy;        // maximum x coordinate contained in the rectangle
 291     }
 292
 293     window.BRect = BRect;
 294     // Static method creating a new bounding rectangle of size (sx,sy) centered on (cx,cy)
 295     BRect.new_centered = function(cx,cy,sx,sy){
 296         return new BRect(cx-sx/2,cy-sy/2,sx,sy);
 297     };
 298     //intersect line a,b with line c,d, returns null if no intersection
 299     function line_intersect(a,b,c,d){
 300         // http://paulbourke.net/geometry/lineline2d/
 301         var f = ((d.y - c.y)*(b.x - a.x) - (d.x - c.x)*(b.y - a.y));
 302         if(f == 0){
 303             return null;
 304         }
 305         f = 1 / f;
 306         var fab = ((d.x - c.x)*(a.y - c.y) - (d.y - c.y)*(a.x - c.x)) * f ;
 307         if(fab < 0 || fab > 1){
 308             return null;
 309         }
 310         var fcd = ((b.x - a.x)*(a.y - c.y) - (b.y - a.y)*(a.x - c.x)) * f ;
 311         if(fcd < 0 || fcd > 1){
 312             return null;
 313         }
 314         return new Vec2(a.x + fab * (b.x-a.x), a.y + fab * (b.y - a.y) );
 315     }
 316
 317     // returns an unordered list of vector defining the positions of the intersections between the ellipse's
 318     // boundary and a line segment defined by the start and end vectors a,b
 319
 320     BRect.prototype.collide_segment = function(a,b){
 321         var collisions = [];
 322         var corners = [ new Vec2(this.x,this.y), new Vec2(this.x,this.my),
 323                         new Vec2(this.mx,this.my), new Vec2(this.mx,this.y) ];
 324         var pos = line_intersect(a,b,corners[0],corners[1]);
 325         if(pos) collisions.push(pos);
 326         pos = line_intersect(a,b,corners[1],corners[2]);
 327         if(pos) collisions.push(pos);
 328         pos = line_intersect(a,b,corners[2],corners[3]);
 329         if(pos) collisions.push(pos);
 330         pos = line_intersect(a,b,corners[3],corners[0]);
 331         if(pos) collisions.push(pos);
 332         return collisions;
 333     };
 334
 335     // returns true if the rectangle contains the position defined by the vector 'vec'
 336     BRect.prototype.contains_vec = function(vec){
 337         return ( vec.x >= this.x && vec.x <= this.mx &&
 338                  vec.y >= this.y && vec.y <= this.my  );
 339     };
 340     // returns true if the rectangle contains the position (x,y)
 341     BRect.prototype.contains_xy = function(x,y){
 342         return ( x >= this.x && x <= this.mx &&
 343                  y >= this.y && y <= this.my  );
 344     };
 345     // returns true if the ellipse contains the position defined by the vector 'vec'
 346     BEllipse.prototype.contains_vec = function(v){
 347         v = v.mult_xy(this.hx,this.hy);
 348         return v.len_sq() <= 1;
 349     };
 350     // returns true if the ellipse contains the position (x,y)
 351     BEllipse.prototype.contains_xy = function(x,y){
 352         return this.contains(new Vec2(x,y));
 353     };
 354
 355
 356 })(window);
 357
 358