Travelling Salesman Sketches: Point-out Proximal Checker

index.html

<div>
  <select id="scale"></select>
  <select id="start"></select>
</div>
<canvas height="800" width="800"></canvas>

script.babel

console.clear();
const PI = Math.PI;
const PI2 = PI * 2;

class Canvas {
  constructor() {
    this.element = document.querySelector('canvas');
    this.context = this.element.getContext('2d');
    this.diameter = this.element.width;
    this.gutter = this.diameter * 0.05;;
  }

  clear() {
    this.context.clearRect(0, 0, this.diameter, this.diameter);
  }
  
  point(x, y, color = 'red', radius = 4) {
    this.context.fillStyle = color;
    this.context.beginPath();
    this.context.arc(this.relative(x), this.relative(y), radius, 0, PI2);
    this.context.fill();
    this.context.closePath();
  }

  line(from, to, color = 'red', width = 1) {
    this.context.beginPath();
    this.context.strokeStyle = color;
    this.context.lineWidth = width;
    this.context.moveTo(this.relative(from[0]), this.relative(from[1]));
    this.context.lineTo(this.relative(to[0]), this.relative(to[1]));
    this.context.stroke();
    this.context.closePath();
  }
  
  relative(pos) {
    return pos * (this.diameter - (this.gutter * 2)) + this.gutter;
  }
}

class Solver {
  constructor({ scale, start }) {
    this.canvas = new Canvas();
    this.update({ scale, start });
    this.draw();
  }

  update({ scale = 0.125, start = 'C' }) {
    this.scale = scale;
    this.radius = Math.round(scale * 6) + 1;
    this.speed = Math.round(scale * 100);
    let startPlots = {
      C: [0.5, 0.5],
      NE: [1 - scale, scale],
      SE: [1 - scale, 1 - scale],
      SW: [scale, 1 - scale],
      NW: [scale, scale],
    }[start];
    this.startX = startPlots[0];
    this.startY = startPlots[1];
    this.NW = this.startX <= 0.5 && this.startY <= 0.5;
    this.NE = this.startX >  0.5 && this.startY <= 0.5;
    this.SE = this.startX >  0.5 && this.startY >  0.5;
    this.SW = this.startX <= 0.5 && this.startY >  0.5;
    this.generate();
    this.progress = 0;
    this.pointIdx = 0;
  }

  generate() {
    this.points = [];
    let steps = 1 / this.scale;
    let rad = this.scale / 2;
    let points = [];
    for (let y = 0; y <= steps; y++) {
      let relY = y * this.scale;
      for (let x = 0; x <= steps; x++) {
        let relX = x * this.scale;
        this.addPoint(relX, relY);
        if (x < steps && y < steps) {
          this.addPoint(relX + rad, relY + rad);
          
        }
      }
    }
    this.pointCount = this.points.length;
    this.sortPoints();
  }
  
  sortPoints() {
    this.points = this.points.sort((a, b) => {
      let ax = a[0], bx = b[0];
      let ay = a[1], by = b[1];
      let aprox = a[2], bprox = b[2];

      // perfer proximity to center
      if (aprox.C > bprox.C) return 1;
      if (aprox.C < bprox.C) return -1;
      
      // prefer radial proximity
      if (aprox.R > bprox.R) return 1;
      if (aprox.R < bprox.R) return -1;

      return 0;
    });
  }

  addPoint(x, y) {
    let prox = {
      C: Math.hypot(this.startX - x, this.startY - y),
      R: Math.atan((0.5 - y) / (0.5 - x)) * (180 / PI)
    }
    this.points.push([x, y, prox]);
  }

  draw() {
    this.canvas.clear();
    this.points.forEach((point) => {
      this.canvas.point(point[0], point[1], '#222', this.radius);
    });
    let point1 = this.points[this.pointIdx % this.pointCount];
    let point2 = this.points[(this.pointIdx + 1) % this.pointCount];
    if ((this.pointIdx + 1) % this.pointCount > 0) {
      let x1 = point1[0],
          y1 = point1[1];
      let x2 = point2[0],
          y2 = point2[1];
      let ratio = (this.progress % this.speed) / (this.speed - 1);
      let distX = (x1 - x2) * ratio;
      let distY = (y1 - y2) * ratio;
      let dx = x1 - distX;
      let dy = y1 - distY;

      let fuzz1 = 2;
      let fuzz2 = this.pointCount;
      // future points
      for (let i = 1; i < 2 + fuzz1; i++) {
        let id = (this.pointIdx % this.pointCount) + i;
        if (id < this.pointCount) {
          let point = this.points[id];
          this.canvas.point(point[0], point[1], 'white', this.radius);
        }
      }

      // previous points
      for (let i = 1; i < 1 + fuzz2; i++) {
        let id = (this.pointIdx % this.pointCount) - i;
        if (id >= 0) {
          let point = this.points[id];
          let x = point[0],
              y = point[1];
          let point3 = this.points[id + 1];
          if (point3) {
            let x3 = point3[0],
                y3 = point3[1];

            if (i >= fuzz1) {
              this.canvas.line([x, y], [x3, y3], '#222');
            } else {
              this.canvas.line([x, y], [x3, y3]);
            }
            if (i === fuzz1) {
              let distX = (x3 - x) * (1-ratio);
              let distY = (y3 - y) * (1-ratio);
              let dx2 = x3 - distX;
              let dy2 = y3 - distY;
              this.canvas.line([dx2, dy2], [x3, y3], 'red', 2);
            }
          }
        }
      }

      this.canvas.line([x1, y1], [dx, dy], 'red', 2);
      this.canvas.point(x1, y1, 'red', this.radius); // previous
      this.canvas.point(dx, dy, 'red', this.radius * 2); // head
    }
    this.progress++;
    if (this.progress % this.speed === 0) this.pointIdx++;

    window.requestAnimationFrame(this.draw.bind(this));
  }
}

// let scales = [0.03125, 0.0625, 0.125, 0.25, 0.5, 1];
let scales = [0.0625, 0.125, 0.25, 0.5, 1];
let starts = ['C', 'NW', 'NE', 'SE', 'SW'];
let currScale = 1;
let currStart = 0;
let $scale = document.querySelector('#scale');
let $start = document.querySelector('#start');

buildScale();
buildStart();

$scale.addEventListener('change', update);
$start.addEventListener('change', update);

let solver = new Solver({ scale: scales[currScale], start: starts[currStart] });

function update() {
  let scale = parseFloat($scale.value);
  let start = $start.value;
  solver.update({ scale, start });
}

function buildScale() {
  for (let i = 0; i < scales.length; i++) {
    let $opt = document.createElement('option');
    $opt.value = scales[i];
    $opt.innerHTML = scales[i];
    if (i === currScale) $opt.setAttribute('selected', true);
    $scale.appendChild($opt);
  }
}

function buildStart() {
  for (let i = 0; i < starts.length; i++) {
    let $opt = document.createElement('option');
    $opt.value = starts[i];
    $opt.innerHTML = starts[i];
    if (i === currStart) $opt.setAttribute('selected', true);
    $start.appendChild($opt);
  }
}

style.scss

body {
  background: #121212;
}
div {
  margin: 1rem 0 0;
  text-align: center;
}

canvas {
  height: auto;
  width: 95%;
  max-width: 600px;
  margin: 1rem auto;
  display: block;
  background: black;
}

travelling-salesman-sketches-point-out-proximal-checker.markdown

Travelling Salesman Sketches: Point-out Proximal Checker

A visualization of a node proximity detection tool. Given a normalized range of points, from a given point, proceed in sequence through points from nearest to furthest with an alternating radial preference.

In my Travelling Salesman optimization work, I have been rounding and grouping points to their nearest Hamiltonian coordinate at different scales (0.03125, 0.0625, 0.125, 0.25, 0.5, and 1). I then optimize that group's path and need to connect to its nearest group. This is for finding the nearest group. At each point, I would check for the presence of a group and if one exists, I stop, if one doesn't, I would continue the path.

A Pen by HARUN PEHLİVAN on CodePen.

License.