/* Global variables go here */ var map; var startPoint; var waypoints = []; var startingPointMode; var waypointMode; var removeWaypointMode; const PointRadius = 10; /* Global variables */ /* Classes go here */ class Coordinates { constructor(x, y) { this.x = x; this.y = y; } } class Point { constructor(coordinates) { this.coordinates = coordinates; this.radius = PointRadius; } vectorLength() { return Math.sqrt( this.coordinates.x * this.coordinates.x + this.coordinates.y * this.coordinates.y ); } } class Startpoint extends Point { constructor(coordinates) { super(coordinates); this.colour = "#008000"; } } class Waypoint extends Point { constructor(coordinates, index) { super(coordinates); this.index = index; this.colour = "#ff3333"; } } /* Classes */ /* Helper functions go here */ function currentMousePosition(event) { var m = document.getElementById("map"); var obj_left = 0; var obj_top = 0; var posX; var posY; while (m.offsetParent) { obj_left += map.offsetLeft; obj_top += map.offsetTop; m = m.offsetParent; } if (event) { posX = event.pageX; posY = event.pageY; } else { posX = window.event.x + document.body.scrollLeft - 2; posY = window.event.y + document.body.scrollTop - 2; } posX -= obj_left; posY -= obj_top; return { x:posX, y:posY }; } function calculateDistance(pointA, pointB) { let tempPoint = new Point ( new Coordinates ( pointB.coordinates.x - pointA.coordinates.x, pointB.coordinates.y - pointA.coordinates.y ) ); return tempPoint.vectorLength(); } function calculateTourDistance(arr) { let distance = 0; for (let i = 0; i < arr.length - 1; ++i) { distance += calculateDistance( arr[i], arr[i + 1] ); } return distance; } function getIndexOfFarestPoint(route, points) { let indexOfFarestPoint = 0; let indexOfTourPoint = 0; for (let i = 0; i < points.length; ++i) { let j = 0; let distance = calculateDistance( points[i], route[j] ); for ( ; j < route.length - 1; ++j) { let currentDistance = calculateDistance( points[i], route[j] ); if (currentDistance < distance) { distance = currentDistance; } } if ( distance > calculateDistance( points[indexOfFarestPoint], route[indexOfTourPoint] ) ) { indexOfFarestPoint = i; indexOfTourPoint = j; } } return indexOfFarestPoint; } function getIndexOfBestInsert(route, point) { let indexOfBestInsert = 1; route.splice(indexOfBestInsert, 0, point); let distance = calculateTourDistance( route ); route.splice(indexOfBestInsert, 1); for (let i = 2; i < route.length; ++i) { route.splice(i, 0, point); let currentDistance = calculateTourDistance( route ); route.splice(i, 1); if (currentDistance < distance) { indexOfBestInsert = i; distance = currentDistance; } } return indexOfBestInsert; } function approximateTour() { let tour = [startPoint, startPoint]; let remainingPoints = waypoints.slice(); while (remainingPoints.length !== 0) { let indexOfFarestPoint = getIndexOfFarestPoint(tour, remainingPoints); let point = remainingPoints[indexOfFarestPoint]; let indexOfBestInsert = getIndexOfBestInsert (tour, point); tour.splice(indexOfBestInsert, 0, point); remainingPoints.splice(indexOfFarestPoint, 1); } return tour; } function updateIDs() { let points = document.getElementsByClassName("waypoint"); for (let i = 0; i < points.length; ++i) { points[i].id = i; } } function updateIndexes() { for (let i = 0; i < waypoints.length; ++i) { waypoints[i].index = i; } } function removeConnections() { let lines = document.getElementsByClassName("connection"); let i = lines.length; while (i--) { lines[i].parentNode.removeChild( lines[i] ); } } function drawConnection(pointA, pointB) { let svg = document.getElementById("background"); let line = document.createElementNS("http://www.w3.org/2000/svg", "line"); line.setAttribute("x1", pointA.coordinates.x + PointRadius / 2); line.setAttribute("y1", pointA.coordinates.y + PointRadius / 2); line.setAttribute("x2", pointB.coordinates.x + PointRadius / 2); line.setAttribute("y2", pointB.coordinates.y + PointRadius / 2); line.setAttribute("class", "connection"); line.style.stroke = "#ff3333"; line.style.strokeWidth = "3"; svg.appendChild(line); } function drawConnections(arr) { for (let index = 0; index < arr.length - 1; ++index) { drawConnection( arr[index], arr[index + 1] ); } } function disableModes() { startingPointMode = false; waypointMode = false; removeWaypointMode = false; } function setStyle(element, point) { element.style.width = point.radius + "px"; element.style.height = point.radius + "px"; element.style.left = point.coordinates.x + "px"; element.style.top = point.coordinates.y + "px"; element.style.backgroundColor = point.colour; } function setStartPoint(event) { let mousePos = currentMousePosition(event); startPoint = new Startpoint( new Coordinates(mousePos.x - PointRadius / 2, mousePos.y - PointRadius / 2) ); let div = document.getElementById("startPoint"); div.style.display = "block"; setStyle(div, startPoint); } function createWaypoint(event) { let mousePos = currentMousePosition(event); let newWaypoint = new Waypoint( new Coordinates(mousePos.x - PointRadius / 2, mousePos.y - PointRadius / 2), waypoints.length ); let newChild = document.createElement("div"); newChild.setAttribute("id", newWaypoint.index); newChild.setAttribute("class", "waypoint"); newChild.setAttribute("onclick", "removeWaypoint(this)"); setStyle(newChild, newWaypoint); map.appendChild(newChild); waypoints.push(newWaypoint); } /* Helper functions */ /* Functions go here */ function initVariables() { map = document.getElementById("map"); startPoint = null; disableModes(); } /* Functions */ /* Event functions go here */ window.onload = function() { initVariables(); map.addEventListener ( "click", addPoint ); alert ( "Short GUI explanation:\n\nTap the top bar (yeah, the little white thing) for different options to set points.\nA green point represents the starting (and ending) point.\nRed points represent waypoints.\nYou can add or remove single points.\nThe Go button draws the route.\nThe Reset button removes all waypoints.\n\n~Whenever people see birds flying through the sky, it's said that they get the urge to go on a journey.~" ); } function removeWaypoint(point) { if (removeWaypointMode) { removeConnections(); point.parentNode.removeChild(point); waypoints.splice(point.id, 1); updateIDs(); updateIndexes(); } } function setStartingPointMode() { disableModes(); startingPointMode = true; } function setWaypointMode() { disableModes(); waypointMode = true; } function setRemoveWaypointMode() { disableModes(); removeWaypointMode = true; } function addPoint(event) { if (startingPointMode === true) { removeConnections(); setStartPoint(event); } else if (waypointMode === true) { if (removeWaypointMode === false) { removeConnections(); createWaypoint(event); } } } function findRoute() { if (startPoint === null) { alert("Please make sure to set a starting point!"); } else if (waypoints.length > 0) { removeConnections(); let sortedWaypoints = approximateTour().slice(); let points = document.getElementsByClassName("waypoint"); for (let i = 1; i < sortedWaypoints.length - 1; ++i) { points[ sortedWaypoints[i].index ].innerHTML = i; } drawConnections(sortedWaypoints); } } function resetPoints() { removeConnections(); waypoints.splice(0, waypoints.length); let points = document.getElementsByClassName("waypoint"); let i = points.length; while (i--) { points[i].parentNode.removeChild( points[i] ); } } /* Event functions */

Round Trip Problem (Visualized)