Travelling Salesman Sketches: Cubic Scoping

script.babel

console.clear();

class Test {
  constructor(index) {
    this.loadTest(index);
  }
  
  loadTest(index) {
    let tests = this.tests();
    this.data = this.normalize(tests[index]);
  }
  
  normalize(test) {
    this.calculatePointRange(test);
    this.transformRelativePoints(test);
    
    test.points = test.points.sort((a, b) => {
      if (a.cDist > b.cDist) return -1;
      if (a.cDist < b.cDist) return 1;
      return 0;
    });

    return test;
  }

  // Transforming points to 0-1 distribution
  //  Adding distance from center
  //  Adding 5 scopes of rounding
  transformRelativePoints(test) {
    let distX = test.maxX - test.minX;  
    let distY = test.maxY - test.minY;  
    test.aspectRatio = distY / distX;

    test.points = test.points.map((point) => {
      let xOrig = point[0];
      let yOrig = point[1];
      // Normalized distribution
      let x = (xOrig - test.minX) / distX;
      let y = (yOrig - test.minY) / distY;
      // Distance from center
      let cDist = Math.hypot(0.5 - x, 0.5 - y);
      let xScopes = [x];
      let yScopes = [y];
      for (let i = 64; i >= 2; i /= 2) {
        xScopes.push(Math.round(x * i) / i);
        yScopes.push(Math.round(y * i) / i);
      }
      
      return { xOrig, yOrig, x, y, cDist, xScopes, yScopes };
    });
  }
  
  // Calculating minimum and maximum values 
  //  in order to normalize as 0-1 floats.
  calculatePointRange(test) {
    test.minX = Infinity;
    test.maxX = -Infinity;
    test.minY = Infinity;
    test.maxY = -Infinity;

    for (let i = 0; i < test.points.length; i++) {
      let point = test.points[i];
      let x = test.points[i][0];
      let y = test.points[i][1];
      if (x < test.minX) test.minX = x;
      if (x > test.maxX) test.maxX = x;
      if (y < test.minY) test.minY = y;
      if (y > test.maxY) test.maxY = y;
    }

    return test;
  }
  
  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;    
    this.initializeAnimationCanvas();
  }
  
  initializeAnimationCanvas() {
    this.$ctx = this.buildCanvas();
    this.$cvs = this.$ctx.canvas;
  }
  
  animate(points, steps, idx = 0) {
    this.$ctx.clearRect(0, 0, this.$cvs.width, this.$cvs.height);
    let perStep = 60;
    let currentIdx = Math.floor(idx / perStep) % steps;
    let percent = (idx % perStep) / perStep;
    let length = points.length;
    for (let i = 0; i < length; i++) {
      let point = points[i];
      let fill = `hsl(${(1 - i / length) * 180}, 100%, 50%)`;
      if (!point.currentX) point.currentX = point.xScopes[currentIdx];
      if (!point.currentY) point.currentY = point.yScopes[currentIdx];
      let nextX = point.xScopes[(currentIdx + 1) % steps];
      let nextY = point.yScopes[(currentIdx + 1) % steps];
      let targetX = nextX - point.currentX;
      let targetY = nextY - point.currentY;
      let x = point.currentX * this.width + this.gutter;
      let y = point.currentY * this.height + this.gutter;
      this.$ctx.fillStyle = fill;
      this.$ctx.beginPath();
      this.$ctx.arc(x, y, this.rad, 0, 2 * this.PI, false);
      this.$ctx.fill();
      let newX = point.currentX + targetX * percent;
      let newY = point.currentY + targetY * percent;
      point.currentX = newX;
      point.currentY = newY;
    }

    window.requestAnimationFrame(() => {
      this.animate(points, steps, idx + 1);
    });
  }
  
  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(points, grid) {
    let $ctx = this.buildCanvas();
    let length = points.length;
    if (grid) {
      $ctx.strokeStyle = '#f0f0f0';
      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();
      }
    }

    for (let i = 0; i < length; i++) {
      let fill = `hsl(${(1 - i / length) * 180}, 100%, 50%)`;
      let point = 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();
    }
  }
}

class Solver {
  constructor({ test }) {
    this.test = test; 
    this.initializeData();
    this.visualizer = new Visualizer({ aspectRatio: this.test.data.aspectRatio });
    this.draw();
    console.log(
      this.test.data.points.map(({ xScopes, yScopes }) => { return { xScopes, yScopes } })
    );
  }
  
  initializeData() {    
    this.scopeCount = this.test.data.points[0].xScopes.length;
    this.grids = [null];
    let finestResolution = Math.pow(2, this.scopeCount - 1);
    for (let i = finestResolution; i >= 2; i /= 2) this.grids.push(i);
  }
  
  draw() {
    this.visualizer.animate(this.test.data.points, this.scopeCount);
    for (let i = 0; i < this.scopeCount; i++) {
      let grid = this.grids[i];
      this.visualizer.draw(
        this.test.data.points.map((point) => {
          return [point.xScopes[i], point.yScopes[i]];
        }), 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: white;
  &:first-of-type {
    background: black;
  }
}

travelling-salesman-sketches-cubic-scoping.markdown

Travelling Salesman Sketches: Cubic Scoping

Dividing Points to nearest 64th, 32nd, sixteenth, eighth, quarter, and half while visualizing each step.

The thought is to generate optimal paths calculated at each step then the inferred connections applied to the original points.

A Pen by HARUN PEHLİVAN on CodePen.

License.