Guest User

Neghbourhood search algorithm

a guest
Jun 26th, 2016
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //To run, call getNonEmptyCells with desired integer N.
  2. //Grab results from foundCells var.
  3. //If needed, add new non-empty points to getCell method;
  4.  
  5. var foundCells = {};
  6. var processedCells = {};
  7.  
  8. function getNonEmptyCells(N) {
  9.     var processingQueue = [];
  10.     processingQueue.push(new Point(0, 0));
  11.     while(processingQueue.length > 0) {
  12.         processNeighbours(processingQueue.pop(), processingQueue, N);
  13.     }
  14.     //Change to other output if needed
  15.     //console.log(foundCells);
  16. }
  17.  
  18. function processNeighbours(point, queue, N) {
  19.     var searchAreaLeftBound = point.x - N - 1;
  20.     var searchAreaRightBound = point.x + N + 1;
  21.     var searchAreaUpperBound = point.y - N - 1;
  22.     var searchAreaLowerBound = point.y + N + 1;
  23.     for (var pX = searchAreaLeftBound; pX <= searchAreaRightBound; pX++) {
  24.         for(var pY = searchAreaUpperBound; pY <= searchAreaLowerBound; pY++) {
  25.             var potentialPoint = new Point(pX, pY);
  26.             if (!processedCells[potentialPoint.toString()]) {
  27.                 processedCells[potentialPoint.toString()] = true;
  28.                 if(getCellByPoint(potentialPoint)) {
  29.                     foundCells[potentialPoint.toString()] = true;
  30.                     queue.push(potentialPoint);
  31.                 }
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. ///// HELPER STRUCTURES /////
  38.  
  39. function Point(x, y) {
  40.     this.x = x;
  41.     this.y = y;
  42. }
  43.  
  44. Point.prototype.toString = function() {
  45.     return this.x + ";" + this.y;
  46. }
  47.  
  48. function getCellByPoint(point) { return getCell(point.x, point.y); }
  49.  
  50. function getCell(x, y) {
  51.     //Black box, returns true for predifined pairs of x and y
  52.     switch (x + ";" + y) {
  53.         case "-2;2": return true;
  54.         case "1;6": return true;
  55.         case "8;9": return true;
  56.         case "-8;0": return true;
  57.         case "-7;0": return true;
  58.         case "-6;0": return true;
  59.         case "-5;0": return true;
  60.         case "-4;0": return true;
  61.         case "-3;0": return true;
  62.         case "-2;0": return true;
  63.         case "-1;0": return true;
  64.         case "0;0": return true;
  65.         case "1;0": return true;
  66.         case "2;0": return true;
  67.         case "3;0": return true;
  68.         case "4;0": return true;
  69.         case "5;0": return true;
  70.         case "6;0": return true;
  71.         case "7;0": return true;
  72.         case "8;0": return true;
  73.         case "0;8": return true;
  74.         case "0;7": return true;
  75.         case "0;6": return true;
  76.         case "0;5": return true;
  77.         case "0;4": return true;
  78.         case "0;3": return true;
  79.         case "0;2": return true;
  80.         case "0;1": return true;
  81.         case "0;-1": return true;
  82.         case "0;-2": return true;
  83.         case "0;-2": return true;
  84.         case "0;-3": return true;
  85.         case "0;-4": return true;
  86.         case "0;-5": return true;
  87.         case "0;-6": return true;
  88.         case "0;-7": return true;
  89.         case "0;-8": return true;
  90.         default: return false;
  91.     }
  92. }
RAW Paste Data