dOYjPd

doyjpd.markdown

dOYjPd

A Pen by tkrugg on CodePen.

License.

script.js

//  A-----------------------B
//  |                       |
//  |                       |
//  D-----------------------C  

// Point Class
function Point(x, y) {
  this.x = x;
  this.y = y;
}

Point.prototype.findQuadrantIn = function(A, B, C, D) {
  if (P.x < (A.x + B.x) / 2) {
    if (P.x < (A.y + D.x) / 2) {
      return "SW";
    } else {
      return "NW";
    }
  } else {
    if (P.x < (A.y + D.x) / 2) {
      return "SE";
    } else {
      return "NE";
    }
  }
};

// Node Class
function Node(A, B, C, D) {
  this.A = A;
  this.B = B;
  this.C = C;
  this.D = D;
  this.children = {
    NW: null,
    NE: null,
    SW: null,
    SE: null
  };
  this.point = null;
}

Node.prototype.addQuadrant(quadrant /* one of [NW, SW, NE, SE] */ ) {
  //  A-----------A_B------------B
  //  |                          |
  // A_D           O            B_C
  //  |                          |
  //  D-----------D_C------------C  
  var A = this.A,
    B = this.B,
    C = this.C,
    D = this.D;
  var A_B = new Point((A.x + B.x) / 2, A.y),
    B_C = new Point(B.x, (B.y + C.y) / 2),
    D_C = new Point((D.x + C.x) / 2, D.y),
    A_D = new Point(A.x, (A.y + D.y) / 2),
    O = new Point((A.x + B.x) / 2, (A.y + D.y) / 2);

  switch (quadrant) {
    case "NW":
      this.children.NW = new Node(A, A_B, O, A_D);
      break;
    case "SW":
      this.children.SW = new Node(A_D, O, D_C, D);
      break;
    case "NE":
      this.children.NE = new Node(A_B, B, B_C, O);
      break;
    case "SE":
      this.children.SE = new Node(O, B_C, C, D_C);
      break;
  }
  return this[quadrant];
};

Node.prototype.insert = function(P) {
  if (this.point) {
    // already has a point
    var A = this.A,
      B = this.B,
      C = this.C,
      D = this.D;
    var quadrant = P.findQuadrantIn(A, B, C, D); // quadrant is one of "NW", "SW", "NE", "SE"
    var quadrantNode = this.addQuadrant(quadrant);
    quadrant.insert(P); // recursive call
  } else {
    // no point
    this.point = P;
  }
};


///// running all the stuff
var A = new Point(0, 20),
  B = new Point(100, 20),
  C = new Point(100, 0),
  D = new Point(0, 0);

var rootNode = new Node([A, B, C, D], null);
var P = new Point(1, 5);
rootNode.insert(P);