Travelling Salesman Sketches: Cubic Scoping II

script.babel

console.clear();

class Test {
  constructor(index) {
    this.initializeGlobals();
    this.loadTest(index);
  }
  
  initializeGlobals() {
    this.finestResolution = 64;
    // Scope Count starts at 1 because we add the original scope
    //  before programmatically generating the rest.
    this.scopeCount = 1 + Math.floor(Math.log2(this.finestResolution, 2));
    // No grid for original
    this.grids = [null];
    for (let i = this.finestResolution; i >= 2; i /= 2) this.grids.push(i);
  }
  
  loadTest(index) {
    this.normalize(this.tests()[index]);
  }
  
  normalize(test) {
    this.points = test.points;
    this.transformPointsInitial();
    this.transformPointsSecondary();
  }
  
  // Getting point ranges and setting guid on the point.
  transformPointsInitial() {
    this.minX = Infinity;
    this.maxX = -Infinity;
    this.minY = Infinity;
    this.maxY = -Infinity;

    this.pointIds = [];
    for (let i = 0; i < this.points.length; i++) {
      let point = this.points[i];
      this.calculatePointRange(point);
      let id = this.guid();
      this.pointIds.push(id);
      this.points[i] = { id, xOrig: point[0], yOrig: point[1] }
    }
  }
  
  // Transforming points to 0-1 distribution
  //  Adding distance from center
  //  Adding 6 cubic scopes of rounding
  transformPointsSecondary() {
    let distX = this.maxX - this.minX;  
    let distY = this.maxY - this.minY;  
    this.aspectRatio = distY / distX;
    this.scopeGroups = {};
    let reference = {};

    for (let i = 0; i < this.points.length; i++) {
      let point = this.points[i];
      let id = point.id;
      // Normalized distribution
      point.x = (point.xOrig - this.minX) / distX;
      point.y = (point.yOrig - this.minY) / distY;
      // Distance from center
      point.cDist = Math.hypot(0.5 - point.x, 0.5 - point.y);
      point.xScopes = [point.x];
      point.yScopes = [point.y];
      this.addToScopeGroup(1000, point.x, point.y, point.id);
      // Cubic position scopes from 64th to half
      for (let i = this.finestResolution; i >= 2; i /= 2) {
        let x = Math.round(point.x * i) / i;
        let y = Math.round(point.y * i) / i;
        point.xScopes.push(x);
        point.yScopes.push(y); 
        this.addToScopeGroup(i, x, y, point.id);
      }
      reference[id] = point;
      delete reference[id].id;
    }
    
    this.points = reference;
    this.orderByDistanceToCenter();
  }
  
  // Order pointIds from furthest to nearest
  orderByDistanceToCenter() {
    this.pointIds = this.pointIds.sort((a, b) => {
      if (this.points[a].cDist > this.points[b].cDist) return -1;
      if (this.points[a].cDist < this.points[b].cDist) return 1;
      return 0;
    });
  }
  
  // Scope groups are references
  addToScopeGroup(cubicRef, x, y, id) {
    if (!this.scopeGroups[cubicRef]) this.scopeGroups[cubicRef] = {};
    let plotRef = `${x}-${y}`;
    if (!this.scopeGroups[cubicRef][plotRef]) this.scopeGroups[cubicRef][plotRef] = [];
    this.scopeGroups[cubicRef][plotRef].push(id);
  }
  
  // Calculating minimum and maximum values 
  //  in order to normalize as 0-1 floats.
  calculatePointRange(point) {
    let x = point[0];
    let y = point[1];
    if (x < this.minX) this.minX = x;
    if (x > this.maxX) this.maxX = x;
    if (y < this.minY) this.minY = y;
    if (y > this.maxY) this.maxY = y;
  }
  
  // https://gist.github.com/Bunkerbewohner/5875991
  guid() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, (c) => {
      let r = Math.random() * 16 | 0, v = c == 'x' ? r : (r&0x3|0x8);
      return v.toString(16);
    });
  }
  
  tests() {
    return [
      {
        name: 'TEST',
        url: '',
        img: '',
        optimal: 564, time: 1000, scale: 10,
        points: [
          [13,0],[26,0],[27,0],[39,0],[0,2],[13,5],[19,5],[25,5],[31,5],
        ]
      },
      {
        name: 'DJ38',
        url: 'http://www.math.uwaterloo.ca/tsp/world/djlog.html',
        img: 'http://www.math.uwaterloo.ca/tsp/world/djtour.gif',
        optimal: 6656, time: 24, scale: 1,
        points: [
          [11003.611100, 42102.500000], [11108.611100, 42373.888900], [11133.333300, 42885.833300], [11155.833300, 42712.500000], [11183.333300, 42933.333300], [11297.500000, 42853.333300], [11310.277800, 42929.444400], [11416.666700, 42983.333300], [11423.888900, 43000.277800],
          [11438.333300, 42057.222200], [11461.111100, 43252.777800], [11485.555600, 43187.222200], [11503.055600, 42855.277800], [11511.388900, 42106.388900], [11522.222200, 42841.944400], [11569.444400, 43136.666700], [11583.333300, 43150.000000], [11595.000000, 43148.055600],
          [11600.000000, 43150.000000], [11690.555600, 42686.666700], [11715.833300, 41836.111100], [11751.111100, 42814.444400], [11770.277800, 42651.944400], [11785.277800, 42884.444400], [11822.777800, 42673.611100], [11846.944400, 42660.555600], [11963.055600, 43290.555600],
          [11973.055600, 43026.111100], [12058.333300, 42195.555600], [12149.444400, 42477.500000], [12286.944400, 43355.555600], [12300.000000, 42433.333300], [12355.833300, 43156.388900], [12363.333300, 43189.166700], [12372.777800, 42711.388900], [12386.666700, 43334.722200],
          [12421.666700, 42895.555600], [12645.000000, 42973.333300],
        ]
      },
      {
        name: 'XQF131',
        url: 'http://www.math.uwaterloo.ca/tsp/vlsi/xqf131.log.html',
        img: 'http://www.math.uwaterloo.ca/tsp/vlsi/xqf131.tour.gif',
        optimal: 564, time: 1000, scale: 10,
        points: [
          [0,13],[0,26],[0,27],[0,39],[2,0],[5,13],[5,19],[5,25],[5,31],[5,37],[5,43],[5,8],[8,0],[9,10],[10,10],[11,10],[12,10],[12,5],[15,13],[15,19],[15,25],[15,31],[15,37],[15,43],[15,8],[18,11],[18,13],[18,15],[18,17],[18,19],[18,21],[18,23],[18,25],[18,27],[18,29],[18,31],[18,33],[18,35],[18,37],[18,39],[18,41],[18,42],[18,44],[18,45],[25,11],[25,15],[25,22],[25,23],[25,24],[25,26],[25,28],[25,29],[25,9],[28,16],[28,20],[28,28],[28,30],[28,34],[28,40],[28,43],[28,47],[32,26],[32,31],[33,15],[33,26],[33,29],[33,31],[34,15],[34,26],[34,29],[34,31],[34,38],[34,41],[34,5],[35,17],[35,31],[38,16],[38,20],[38,30],[38,34],[40,22],[41,23],[41,32],[41,34],[41,35],[41,36],[48,22],[48,27],[48,6],[51,45],[51,47],[56,25],[57,12],[57,25],[57,44],[61,45],[61,47],[63,6],[64,22],[71,11],[71,13],[71,16],[71,45],[71,47],[74,12],[74,16],[74,20],[74,24],[74,29],[74,35],[74,39],[74,6],[77,21],[78,10],[78,32],[78,35],[78,39],[79,10],[79,33],[79,37],[80,10],[80,41],[80,5],[81,17],[84,20],[84,24],[84,29],[84,34],[84,38],[84,6],[107,27]
        ]
      }
    ]
  }
}

class Visualizer {
  constructor({ aspectRatio }) {
    this.PI = Math.PI;
    this.gutter = 12;
    this.di = 8;
    this.rad = this.di / 2;
    let width = 800;
    let height = width * aspectRatio;
    this.width = width;
    this.height = height;
    this.aspectRatio = aspectRatio;    
  }
  
  buildCanvas() {
    let $cvs = document.createElement('canvas');
    let $ctx = $cvs.getContext('2d');
    $cvs.width = this.width + (this.gutter * 2);
    $cvs.height = this.height + (this.gutter * 2);
    document.body.appendChild($cvs);
    return $ctx;
  }
  
  draw(pointGroups, grid) {
    let $ctx = this.buildCanvas();
    if (grid) this.drawGrid(grid, $ctx);
    for (let p = 0; p < pointGroups.length; p++) {
      let group = pointGroups[p];
      let fill = group.fill;
      for (let i = 0; i < group.points.length; i++) {
        let point = group.points[i];
        let x = (point[0] * this.width) + this.gutter;
        let y = (point[1] * this.height) + this.gutter;
        $ctx.fillStyle = fill;
        $ctx.beginPath();
        $ctx.arc(x, y, this.rad, 0, 2 * this.PI, false);
        $ctx.fill();
      }
    }
  }
  
  drawGrid(grid, $ctx) {
    $ctx.strokeStyle = '#191919';
    for (let i = 0; i <= grid; i++) {
      let x = i / grid * this.width + this.gutter;
      $ctx.beginPath();
      $ctx.moveTo(x, this.gutter);
      $ctx.lineTo(x, this.height + this.gutter);
      $ctx.stroke();

      let y = i / grid * this.height + this.gutter;
      $ctx.beginPath();
      $ctx.moveTo(this.gutter, y);
      $ctx.lineTo(this.width + this.gutter, y);
      $ctx.stroke();
    }
  }
}

class Solver {
  constructor({ test }) {
    this.test = test; 
    this.visualizer = new Visualizer({ aspectRatio: this.test.aspectRatio });
    this.draw();
  }
  
  draw() {
    let pointGroups = [];
    let fills = [];
    let scopeGroups = this.test.scopeGroups;
    let scopeGroupKeys = Object.keys(scopeGroups);
    scopeGroupKeys.reverse();
    scopeGroupKeys.forEach((scopeGroup, s) => { 
      let grid = this.test.grids[s];
      let scopeArr = [];
      let group = scopeGroups[scopeGroup];
      let keys = Object.keys(group);
      keys.forEach((key, i) => {
        scopeArr.push({
          fill: `hsl(${(1 - i / keys.length) * 300}, 100%, 50%)`,
          points: group[key].map((id) => {
            let point = this.test.points[id];
            return [point.x, point.y]
          })
        });
      })
      this.visualizer.draw(scopeArr, grid);
    });
  }
}

let test = new Test(2);
let solver = new Solver({ test });

style.scss

html, body {
  height: 100%;
}

body {
  background: #212121;
}

canvas {
  margin: 1rem auto;
  width: calc(100% - 2rem);
  max-width: 600px;
  height: auto;
  display: block;
  background: black;
}

travelling-salesman-sketches-cubic-scoping-ii.markdown

Travelling Salesman Sketches: Cubic Scoping II

Visualizing cubic scoping by coloring scoped groups

A Pen by HARUN PEHLİVAN on CodePen.

License.