JSFiddle - React, Tailwind, and code Playground

Tour Guide problem: traveling salesperson problem with moving target coordinates in javascript. Calculate time required to reach new point using quadratic equation. TODO: write a calculator that calculates all possible routes and gives a summary with the fastest solution

by Yurii Predborskyi

JavaScript

function MovingPoint(x = 0, y = 0, speed = 0, angle = 0) {
    this.x = x;
    this.y = y;
    this.angle = angle; // radians
    this.speed = speed;
}
MovingPoint.prototype.moveForward = function(time) {
    this.x += this.speed * Math.cos(this.angle) * time;
    this.y += this.speed * Math.sin(this.angle) * time;
};
MovingPoint.prototype.moveToPoint = function(destination) {
    this.x = destination.x;
    this.y = destination.y;
};

function State(mySpeed) {
    this.movingPoint = new MovingPoint(0, 0, mySpeed);
    this.timeTotal = 0;
    this.timeBuffer = 0;
}

function sq(n) {
    return Math.pow(n, 2);
}

// solve quadratic equasion and return bigger number
function solveQuadraticEquation(a, b, c) {
    let result = (-1 * b + Math.sqrt(sq(b) - (4 * a * c))) / (2 * a);
    let result2 = (-1 * b - Math.sqrt(sq(b) - (4 * a * c))) / (2 * a);
    return Math.max(result, result2);
}

// calculate the time required to reach a moving target using quadratic equasion
function getTimeToPoint(origin, target) {
    let x = target.x - origin.x;
    let y = target.y - origin.y;
    let xs = target.speed * Math.cos(target.angle);
    let ys = target.speed * Math.sin(target.angle);

    let a = sq(xs) + sq(ys) - sq(origin.speed);
    let b = 2 * x * xs + 2 * y * ys;
    let c = sq(x) + sq(y);
    return solveQuadraticEquation(a, b, c);
}

let base = new MovingPoint();
let shortestRoute = Number.MAX_SAFE_INTEGER;

let pathCollection = [];
let targetPoints = [];

// read from file
//let mySpeed = 50;
let mySpeed = 100;

// read targets from file
//let target = new MovingPoint(125, 175, 25, 1.96);
//targetPoints.push(target);
targetPoints.push(new MovingPoint(30.0, -80.0, 23.0, 2.76));
targetPoints.push(new MovingPoint(40.0, 25.0, 20.0, 5.95));
targetPoints.push(new MovingPoint(-185.0, 195.0, 6.0, 2.35));

// go over all targets and write down all possible paths
for (let start = 0; start < targetPoints.length; ++start) {
    let path = [targetPoints[start]];
    let next =...