Travelling Salesman Sketches: Triangular Proximal Grouping

index.html

<header>
  <select>
    <option value="1">3 Points</option>
    <option value="2">9 Points</option>
    <option value="3" selected>27 Points</option>
    <option value="4">81 Points</option>
  </select>

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

<main>
  <div>
    <canvas height="1200" width="1200"></canvas>
  </div>
</main>

script.babel

console.clear();

const PI2 = 2 * Math.PI;

class Point {
  constructor({ x, y }) {
    this.x = x;
    this.y = y;
    this.id = generateUUID();
  }
  
  relative(minX, minY, distX, distY) {
    this.x = (this.x - minX) / distX;
    this.y = (this.y - minY) / distY;
    this.distC = this.distance({ x: 0.5, y: 0.5 });
  }
  
  relate(points, proximities) {
    this.relativePoints = Array.from(points).sort((a, b) => {
      // push this to end
      if (a.id === this.id) return 1;
      if (b.id === this.id) return -1;
      // get uniform ids
      let idA = [this.id, a.id].sort().join('+');
      let idB = [this.id, b.id].sort().join('+');
      // get or set proximities
      proximities[idA] = proximities[idA] || this.distance(a);
      proximities[idB] = proximities[idB] || this.distance(b);
      // relate based on proximity
      if (proximities[idA] < proximities[idB]) return -1;
      if (proximities[idA] > proximities[idB]) return 1;
      return 0;
    }).map((a) => { return a.id });
    return proximities;
  }
  
  distance(point) {
    return Math.hypot(point.x - this.x, point.y - this.y);
  }
}

class Group {
  constructor(p1, p2, p3) {
    this.p1 = p1;
    this.p2 = p2;
    this.p3 = p3;
    this.x = (p1.x + p2.x + p3.x) / 3;
    this.y = (p1.y + p2.y + p3.y) / 3;
    this.point = new Point({ x: this.x, y: this.y });
  }
  
  relate(points, proximities) {
    return this.point.relate(points, proximities);
  }
}

class App {
  constructor() {
    this.cvs = document.querySelector('canvas');
    this.ctx = this.cvs.getContext('2d');
  }
  
  run(genCount) {
    this.count = genCount ? Math.pow(3, genCount) : this.count;
    this.generationCount = genCount ? genCount : this.generationCount;
    this.generatePoints();
    this.groupPoints();
    this.drawGroups();
  }
  
  generatePoints() {
    this.minX = Infinity;
    this.maxX = 0;
    this.minY = Infinity;
    this.maxY = 0;
    this.points = {};
    this.pointIds = [];
    for (let i = 0; i < this.count; i++) {
      let x = Math.random(), y = Math.random();
      this.minX = Math.min(x, this.minX);
      this.maxX = Math.max(x, this.maxX);
      this.minY = Math.min(y, this.minY);
      this.maxY = Math.max(y, this.maxY);
      let point = new Point({ x, y });
      this.points[point.id] = point;
      this.pointIds.push(point.id);
    }
    this.distX = this.maxX - this.minX;
    this.distY = this.maxY - this.minY;
    this.pointIds.forEach((pointId) => {
      this.points[pointId].relative(this.minX, this.minY, this.distX, this.distY);
    });

    this.pointIds = this.pointIds.sort((a, b) => {
      let p1 = this.points[a];
      let p2 = this.points[b];
      if (p1.distC > p2.distC) return -1;
      if (p1.distC < p2.distC) return 1;
      return 0;
    });

    this.proximities = {};
    let pointsArr = this.pointIds.map((id) => { return this.points[id]; });
    this.pointIds.forEach((pointId) => {
      this.proximities = this.points[pointId].relate(pointsArr, this.proximities);
    });
  }
  
  groupPoints() {
    this.generations = {};
    let tmpIds = Array.from(this.pointIds);
    let source = this.points;

    for (let g = 0; g < this.generationCount; g++) {
      let generationKey = g;
      this.generations[generationKey] = { ids: [], groups: {} };
      let currId = tmpIds[0];
      let iterations = tmpIds.length / 3;

      for (let i = 0; i < iterations; i++) {
        let item = source[currId];
        tmpIds.splice(tmpIds.indexOf(item.id), 1);

        let group = [item];
        for (let j = 0; j < item.relativePoints.length - 1; j++) {
          let id = item.relativePoints[j];
          if (group.length < 3 && tmpIds.includes(id)) {
            tmpIds.splice(tmpIds.indexOf(id), 1);
            group.push(source[id]);
            currId = tmpIds[0];
          } else if (group.length === 3) {
            continue;
          }
        }
        let newGroup = new Group(...group);
        this.generations[generationKey].ids.push(newGroup.point.id);
        this.generations[generationKey].groups[newGroup.point.id] = newGroup;
      }

      let groupSource = {};
      let groupsAsPoints = this.generations[generationKey].ids.map((groupId) => {
        let point = this.generations[generationKey].groups[groupId].point;
        groupSource[point.id] = point;
        return point;
      });

      let groups = this.generations[generationKey].ids.map((groupId) => {
        let group = this.generations[generationKey].groups[groupId];
        this.proximities = group.relate(groupsAsPoints, this.proximities);
        return group;
      });

      tmpIds = Array.from(this.generations[generationKey].ids);
      source = groupSource;
    }
  }

  drawGroups() {
    this.w = this.cvs.width;
    this.h = this.cvs.height;
    this.ctx.clearRect(0, 0, this.w, this.h);
    
    let genIdx = 0;
    let generationArr = Object.keys(this.generations).reverse().map((id) => { return this.generations[id] });
    generationArr.forEach((generation) => {
      generation.ids.forEach((groupId, i) => {
        let gen0 = genIdx === (generationArr.length - 1);
        let group = generation.groups[groupId];
        let ratio1 = genIdx / (this.generationCount - 1);
        let ratio2 = 1 - ratio1;
        let ratio3 = i / (generation.ids.length - 1);
        let hue = 320 * ratio3;
        let lit = (ratio1 * 0.9 + 0.1) * 100;
        let color = gen0 ? `hsla(${hue}, 100%, 60%, 1)` : `hsla(0, 0%, ${lit}%, 1)`;
        let fill = `hsla(${hue}, 100%, 60%, 1)`;
        let lineW = Math.pow(ratio2,2) * 8 + 2;
        this.path(group.p1, group, color, lineW);
        this.path(group.p2, group, color, lineW);
        this.path(group.p3, group, color, lineW);
        if (gen0) {
          this.point(group.p1.x, group.p1.y, fill, 8);
          this.point(group.p2.x, group.p2.y, fill, 8);
          this.point(group.p3.x, group.p3.y, fill, 8);
        }
      });
      genIdx++;
    });
  }
  
  path(p1, p2, stroke = 'rgba(255,0,0,0.5)', lineWidth = 1) {
    this.ctx.strokeStyle = stroke;
    this.ctx.lineWidth = lineWidth;
    this.ctx.beginPath();
    this.ctx.moveTo(this.relX(p1.x), this.relY(p1.y));
    this.ctx.lineTo(this.relX(p2.x), this.relY(p2.y));
    this.ctx.stroke();
  }
  
  point(x, y, fill = 'red', rad = 4) {
    this.ctx.fillStyle = fill;
    this.ctx.beginPath();
    this.ctx.arc(this.relX(x), this.relY(y), rad, 0, PI2);
    this.ctx.fill();
  }
  
  relX(x) {
    return x * (this.w * 0.8) + (this.w * 0.1);
  }

  relY(y) {
    return y * (this.h * 0.8) + (this.h * 0.1);
  }
}

let complexity = 2;
let app = new App();

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

function 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);
  });
}

style.scss

html,body {
  height: 100%;
}

body {
  background: #121212;
}

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

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;
  margin: 0 auto;
  width: 95%;
  max-width: 600px;
  div {
    position: relative;
    width: 100%;
  }
}

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

travelling-salesman-sketches-triangular-proximal-grouping.markdown

Travelling Salesman Sketches: Triangular Proximal Grouping

The principal is that a triangle only has one real path around it: ABC or ACB.

The approach here is to group all points in proximal groups of three, prioritizing furthest distance from the center of the points. This pass is Generation0. Generation0 groups are then proximally grouped (Generation1), and so on until there is only one group of three left (GenerationN). Then you connect each groups' three points to the group's center to get the web you see here.

This is basically a cheat solution for TSP and currently requires Math.pow(3, x) points.

The logic is based on how much of TSP is visual, so it takes advantage of that fact.

If you are walking from one group of three locations in the direction of the next closest group of three locations, you can visibly tell which location in the next group is closest. Then you hit the other two locations in that group and move on.

This will not tell you which point in a given group you want to hit first, it will just get you in its vicinity. It also requires looping over each point for each point and is O(n^2).

A Pen by HARUN PEHLİVAN on CodePen.

License.