Travelling Salesman Sketches: Optimal 3-6 Vector Pathing

index.html

<header>
  <select>
    <option value="3">3 Points</option>
    <option value="4" selected>4 Points</option>
    <option value="5">5 Points</option>
    <option value="6">6 Points</option>
  </select>

  <button>Refresh</button>
</header>

<main></main>

script.babel

console.clear();

const PI2 = Math.PI * 2;
const PERMUTATIONS = {
  3: [[0,1,2]],
  4: [[0,1,2,3], [0,1,3,2], [0,2,1,3]],
  5: [
    [0,1,2,3,4], [0,1,2,4,3], [0,1,3,2,4], [0,1,3,4,2], [0,1,4,2,3], [0,1,4,3,2], 
    [0,2,1,3,4], [0,2,1,4,3], [0,2,3,1,4], [0,2,4,1,3], 
    [0,3,1,2,4], [0,3,2,1,4],
  ],
  6: [
    [0,1,2,3,4,5], [0,1,2,3,5,4], [0,1,2,4,3,5], [0,1,2,4,5,3], [0,1,2,5,3,4], [0,1,2,5,4,3], 
      [0,1,3,2,4,5], [0,1,3,2,5,4], [0,1,3,4,2,5], [0,1,3,4,5,2], [0,1,3,5,2,4], [0,1,3,5,4,2],
      [0,1,4,2,3,5], [0,1,4,2,5,3], [0,1,4,3,2,5], [0,1,4,3,5,2], [0,1,4,5,2,3], [0,1,4,5,3,2],
      [0,1,5,2,3,4], [0,1,5,2,4,3], [0,1,5,3,2,4], [0,1,5,3,4,2], [0,1,5,4,2,3], [0,1,5,4,3,2],
    [0,2,1,3,4,5], [0,2,1,3,5,4], [0,2,1,4,3,5], [0,2,1,4,5,3], [0,2,1,5,3,4], [0,2,1,5,4,3],
      [0,2,3,1,4,5], [0,2,3,1,5,4], [0,2,3,4,1,5], [0,2,3,5,1,4], [0,2,4,1,3,5], [0,2,4,1,5,3],
      [0,2,4,3,1,5], [0,2,4,5,1,3], [0,2,5,1,3,4], [0,2,5,1,4,3], [0,2,5,3,1,4], [0,2,5,4,1,3],
    [0,3,1,2,4,5], [0,3,1,2,5,4], [0,3,1,4,2,5], [0,3,1,5,2,4], [0,3,2,1,4,5], [0,3,2,1,5,4],
      [0,3,2,4,1,5], [0,3,2,5,1,4], [0,3,4,1,2,5], [0,3,4,2,1,5], [0,3,5,1,2,4], [0,3,5,2,1,4],
    [0,4,1,2,3,5], [0,4,1,3,2,5], [0,4,2,1,3,5], [0,4,2,3,1,5], [0,4,3,1,2,5], [0,4,3,2,1,5],
  ]
};

class MathHelper {
  static distance(x1, y1, x2, y2) {
    return Math.hypot(x1 - x2, y1 - y2);
  }
  
  static heron(len1, len2, len3) {
    let s = (len1 + len2 + len3) / 2;
    return Math.sqrt(s * len1 * len2 * len3);
  }
  
  // https://stackoverflow.com/a/2117523
  static generateUUID() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, (c) => {
      let r = Math.random() * 16 | 0;
      let v = c == 'x' ? r : (r & 0x3 | 0x8);
      return v.toString(16);
    });
  }
}

class Point {
  constructor({ x, y }) {
    this.id = MathHelper.generateUUID();
    this.relX = x;
    this.relY = y;
  }
  
  // relative vectors after all vectors are known
  relate({ realW, realH, relW, relH, minX, minY }) {
    this.relX = (this.relX - minX) / relW;
    this.relY = (this.relY - minY) / relH;
    this.setRealVectors(realW, realH);
  }

  // normal vectors relative to real realH and realW of canvas
  setRealVectors(realW, realH) {
    let a = 80;
    let b = a / 2;
    this.realX = this.relX * (realW - a) + b;
    this.realY = this.relY * (realH - a) + b;
    this.realDist = MathHelper.distance(realW / 2, realH / 2, this.realX, this.realY);
  }
}

class Route {
  constructor() {
    this.sequenceIds = [];
    this.sequences = {};
  }
  
  sequence(idx) {
    let id = this.sequenceIds[idx];
    return id ? this.sequences[id] : null;
  }

  traverse(points) {
    let permutations = PERMUTATIONS[Object.keys(points).length];
    for (let i = 0; i < permutations.length; i++) {
      let dist = 0;
      let sequenceIdxs = permutations[i];
      let sequence = { distance: 0, points: [] };
      let id = MathHelper.generateUUID();
      for (let j = 0; j < sequenceIdxs.length; j++) {
        let p1 = points[sequenceIdxs[j]];
        let p2 = points[sequenceIdxs[(j + 1) % sequenceIdxs.length]];
        let distance = MathHelper.distance(p1.realX, p1.realY, p2.realX, p2.realY);
        sequence.points.push(p1.id);
        sequence.distance += distance;
      }
      this.sequenceIds.push(id); 
      this.sequences[id] = sequence;
    }
    this.sequenceIds.sort((a, b) => {
      let seqA = this.sequences[a];
      let seqB = this.sequences[b];
      if (seqA.distance > seqB.distance) return 1;
      if (seqA.distance < seqB.distance) return -1;
      return 0;
    })
  }
}

class Visualizer {
  constructor(count) {
    document.querySelector('main').innerHTML = '';
    this.canvases = [];
    this.contexts = [];
    this.current = 0;
    for (let i = 0; i < count; i++) {
      let div = document.createElement('div');
      this.canvases[i] = document.createElement('canvas');
      this.contexts[i] = this.canvases[i].getContext('2d');
      div.appendChild(this.canvases[i]);
      document.querySelector('main').appendChild(div);
    }
  }
  
  get context() { return this.contexts[this.current]; }
  get canvas()  { return this.canvases[this.current]; }
  
  update(idx) {
    this.current = idx;
  }
  
  size(width, height) {
    this.width = width;
    this.height = height;
    this.canvases.forEach((canvas) => {
      canvas.width = width;
      canvas.height = height;
    });
  }
  
  text(text) {
    let span = document.createElement('span');
    span.innerHTML = text;
    this.canvas.parentNode.appendChild(span);
  }
  
  clear() {
    this.contexts.forEach((context) => { context.clearRect(0, 0, this.width, this.height) });
  }
  
  line(x1, y1, x2, y2, color = 'red', dotted) {
    this.context.strokeStyle = color;
    this.context.lineWidth = 2;
    if (dotted) this.context.setLineDash([2, 8]);

    this.context.beginPath();
    this.context.moveTo(x1, y1);
    this.context.lineTo(x2, y2);
    this.context.stroke();
    this.context.setLineDash([]);
  }
  
  point(x, y, fill = 'red') {
    this.context.fillStyle = fill;
    this.context.beginPath();
    this.context.arc(x, y, 4, 0, PI2);
    this.context.fill();
  }
  
  orbit(radius) {
    this.context.lineJoin = 'round';
    this.context.lineWidth = 1;
    this.context.strokeStyle = 'rgba(255,255,255,0.2)';

    this.context.beginPath();
    this.context.arc(this.width / 2, this.height / 2, radius, 0, PI2);
    this.context.stroke();
  }
}

class App {
  constructor() {
    this.overrideIdx = null;
  }
  
  print() {
    console.log(JSON.stringify(this.pointIds.map((pointId) => {
      let point = this.points[pointId];
      return [
        Math.round(point.relX * 100) / 100,
        Math.round(point.relY * 100) / 100
      ];
    })));
  }
  
  run(count) {
    this.pointCount = count ? count : this.pointCount || 4;
    let cvsCount = PERMUTATIONS[this.pointCount].length;
    this.visualizer = new Visualizer(cvsCount);
    this.route = new Route();
    this.generateCluster();
    this.traverse();
    this.drawSequences();
    // this.print();
  }
  
  get overrides() {
    return [
      [[0,0],[1,1],[0.18,0.69],[0.55,0.75]],
      [[0.1,0.1],[0.6,0.4],[0.91,0.91],[0.82,0.8]],
      [[0.1,0.1],[0.9,0.4],[0.8,0.9],[0.4,0.7],],
      [[0.1,0.1],[0.9,0.45],[0.3,0.7],[0.2,0.8],],
      [[0,0],[1,0.91],[0.071,0.047],[0.42,1]],
      [[0,1],[1,0.74],[0.72,0],[0.75,0.76]],
      [[1,0],[0,1],[0.15,0.14],[0.68,0.09]],
      [[0,1],[1,0],[0.61,0.58],[0.35,0.5]],
      [[1,0.06],[0.21,0],[0.69,1],[0,0.44]],
      [[1,1],[0,0.17],[0.21,0],[0.78,0.6]],
    ];    
  }
  
  generateCluster() {
    this.initializeMinMax();
    this.pointIds = [];
    this.points = {};
    // For specific overriding of tough paths
    let override;
    if (typeof this.overrideIdx === 'number') {
      override = this.overrides[(this.overrideIdx) % this.overrides.length];
      this.overrideIdx++;
    }

    for (let i = 0; i < this.pointCount; i++) {
      let x = override ? override[i][0] : Math.random();
      let y = override ? override[i][1] : Math.random();
      let point = new Point({ x, y });
      this.pointIds.push(point.id);
      this.points[point.id] = point;
      this.updateMinMax(x, y);
    }
    let minDi = 400;
    let maxDi = 400;
    let diffDi = maxDi - minDi;
    let relW = this.maxX - this.minX;
    let relH = this.maxY - this.minY;
    let realW = relW * diffDi + minDi;
    let realH = relH * diffDi + minDi;
    this.visualizer.clear();
    this.visualizer.size(realW, realH);
    let minX = this.minX;
    let minY = this.minY;
    this.pointIds.forEach((id) => {
      this.points[id].relate({ realW, realH, relW, relH, minX, minY });
    });
  }
  
  traverse() {
    let points = this.pointIds.map((id) => { return this.points[id]; });
    this.route.traverse(points);
  }
  
  drawSequences() {
    for (let i = 0; i < this.route.sequenceIds.length; i++) {
      this.visualizer.update(i);
      let sequence = this.route.sequence(i);
      let color = i > 0 ? 'red' : 'white';
      this.visualizer.text(Math.round(sequence.distance * 100) / 100);
      sequence.points.forEach((pointId, i) => {
        let point = this.points[pointId];
        this.drawPath(pointId, sequence.points[(i + 1) % this.pointCount], color);
        this.visualizer.orbit(point.realDist);
        this.visualizer.point(point.realX, point.realY, color);
      });
    }    
  }
  
  drawPath(id1, id2, color, dashed) {
    let p1 = this.points[id1];
    let p2 = this.points[id2];
    this.visualizer.line(p1.realX, p1.realY, p2.realX, p2.realY, color, dashed);
  }
  
  initializeMinMax() {
    this.maxX = 0;
    this.maxY = 0;
    this.minX = Infinity;
    this.minY = Infinity;
  }

  updateMinMax(x, y) {
    this.maxX = Math.max(x, this.maxX);
    this.minX = Math.min(x, this.minX);
    this.maxY = Math.max(y, this.maxY);
    this.minY = Math.min(y, this.minY);
  }
}

let app = new App();
app.run();
document.querySelector('select').addEventListener('change', (e) => {
  app.run(parseInt(e.target.value))
});
document.querySelector('button').addEventListener('click', () => { app.run(); });

style.scss

html,body {
  height: 100%;
}

body {
  background: #121212;
}

header, main {
  text-align: center;
  width: 95%;
  max-width: 1200px;
  margin: 2rem auto;
}

button, select {
  border-radius: 4px;
  padding: 0.5rem 0.75rem;
  appearance: none;
  background: black;
  color: white;
  border: 2px solid #444;
  &:hover {
    border-color: white;
  }
  cursor: pointer;
}

main {
  user-select: none;
  display: flex;
  flex-wrap: wrap;
  align-content: center;
  justify-content: center;
  div {
    padding: 0.5rem;
    box-sizing: border-box;
    position: relative;
    width: calc(50% - 1rem);
    @media (min-width: 700px) {
      width: calc(25% - 1rem);
    }
    span {
      color: white;
      font-size: 0.7rem;
      position: absolute;
      bottom: 0.75rem;
      right: 0.75rem;
    }
  }
}

canvas {
  display: block;
  height: auto;
  width: 100%;
  background: black;
}

travelling-salesman-sketches-optimal-3-6-vector-pathing.markdown

Travelling Salesman Sketches: Optimal 3-6 Vector Pathing

Optimally drawing round trip path between three to six points using brute force

A Pen by HARUN PEHLİVAN on CodePen.

License.