Draw Map in Browser out of 2 Dimensional Array of Distances

Question

I'm receiving all distances between a random number of points in a 2 dimensional coordinate system.

How can I visualize this as coordinates on a map in my browser? In case there are many solutions I just want to see the first possible one that my algorithm can come up with.

So here's an extremely easy example:

PointCount = 3  
Distances:  
0-1 = 2  
0-2 = 4  
1-2 = 2  

Does anyone know an easy way (existing solution/framework maybe) to do it using whatever is out there to make it easier to implement?
I was thinking maybe using the html canvas element for drawing, but I don't know how to create an algorithm that could come up with possible coordinates for those points.

The above example is simplified -
Real distance values could look like this:

       (0)  (1)     (2)     (3)
   (0)  0   2344    3333    10000   
   (1)      0       3566    10333   
   (2)              0       12520   

Answer 1

I'm not sure this is relevant for SO, but anyway...

The way to do this is quite simply to place the points one by one using the data:

• Pick a random location for the first point (let's say it's 0,0).

• The second point is on a circle with radius d(0,1) with the first point as its center, so you can pick any point on the circle. Let's pick (d(0,1),0).

• The third point is at the intersection of a circle with radius d(0,2) and center point 1, and a circle with radius d(1,2) and center point 2. You will get either 0, 1, 2 or an infinity of solutions. If the data comes from real points, 0 shouldn't happen. 1 and infinity are edge cases, but you should still handle them. Pick any of the solutions.

• The fourth point is at the intersection of 3 circles. Unless you're very unlucky (but you should account for it), there should be only one solution.

• Continue like this until all points have been placed.

Note that this doesn't mean you'll get the exact locations of the original points: you can have any combination of a translation (the choice of your first point), rotation (the choice of your second point) and symmetry (the choice of your third point) making the difference.

A quick and dirty implementation (not handling quite a few cases, and tested very little):

function distance(p1, p2) {
  return Math.sqrt(Math.pow(p2[0] - p1[0], 2) + Math.pow(p2[1] - p1[1], 2));
}

// adapted from https://stackoverflow.com/a/12221389/3527940
function intersection(x0, y0, r0, x1, y1, r1) {
  var a, dx, dy, d, h, rx, ry;
  var x2, y2;

  /* dx and dy are the vertical and horizontal distances between
   * the circle centers.
   */
  dx = x1 - x0;
  dy = y1 - y0;

  /* Determine the straight-line distance between the centers. */
  d = Math.sqrt((dy * dy) + (dx * dx));

  /* Check for solvability. */
  if (d > (r0 + r1)) {
/* no solution. circles do not intersect. */
return false;
  }
  if (d < Math.abs(r0 - r1)) {
/* no solution. one circle is contained in the other */
return false;
  }

  /* 'point 2' is the point where the line through the circle
   * intersection points crosses the line between the circle
   * centers.  
   */

  /* Determine the distance from point 0 to point 2. */
  a = ((r0 * r0) - (r1 * r1) + (d * d)) / (2.0 * d);

  /* Determine the coordinates of point 2. */
  x2 = x0 + (dx * a / d);
  y2 = y0 + (dy * a / d);

  /* Determine the distance from point 2 to either of the
   * intersection points.
   */
  h = Math.sqrt((r0 * r0) - (a * a));

  /* Now determine the offsets of the intersection points from
   * point 2.
   */
  rx = -dy * (h / d);
  ry = dx * (h / d);

  /* Determine the absolute intersection points. */
  var xi = x2 + rx;
  var xi_prime = x2 - rx;
  var yi = y2 + ry;
  var yi_prime = y2 - ry;

  return [
[xi, yi],
[xi_prime, yi_prime]
  ];
}

function generateData(nbPoints) {
  var i, j, k;
  var originalPoints = [];

  for (i = 0; i < nbPoints; i++) {
originalPoints.push([Math.random() * 20000 - 10000, Math.random() * 20000 - 10000]);
  }
  var data = [];
  var distances;
  for (i = 0; i < nbPoints; i++) {
distances = [];
for (j = 0; j < i; j++) {
  distances.push(distance(originalPoints[i], originalPoints[j]));
}
data.push(distances);
  }
  //console.log("original points", originalPoints);
  //console.log("distance data", data);
  return data;
}

function findPointsForDistances(data, threshold) {
  var points = [];
  var solutions;
  var solutions1, solutions2;
  var point;
  var i, j, k;

  if (!threshold)
threshold = 0.01;

  // First point, arbitrarily set at 0,0
  points.push([0, 0]);

  // Second point, arbitrarily set at d(0,1),0
  points.push([data[1][0], 0]);

  // Third point, intersection of two circles, pick any solution
  solutions = intersection(
points[0][0], points[0][1], data[2][0],
points[1][0], points[1][1], data[2][1]);
  //console.log("possible solutions for point 3", solutions);
  points.push(solutions[0]);

  //console.log("solution for points 1, 2 and 3", points);
  found = true;

  // Subsequent points, intersections of n-1 circles, use first two to find 2 solutions,
  // the 3rd to pick one of the two
  // then use others to check it's valid
  for (i = 3; i < data.length; i++) {
// distances to points 1 and 2 give two circles and two possible solutions
solutions = intersection(
  points[0][0], points[0][1], data[i][0],
  points[1][0], points[1][1], data[i][1]);
//console.log("possible solutions for point " + (i + 1), solutions);
// try to find which solution is compatible with distance to point 3
found = false;
for (j = 0; j < 2; j++) {
  if (Math.abs(distance(solutions[j], points[2]) - data[i][2]) <= threshold) {
    point = solutions[j];
    found = true;
    break;
  }
}
if (!found) {
  console.log("could not find solution for point " + (i + 1));
  console.log("distance data", data);
  console.log("solution for points 1, 2 and 3", points);
  console.log("possible solutions for point " + (i + 1), solutions);
  console.log("distances to point 3",
   distance(solutions[0], points[2]),
    distance(solutions[1], points[2]),
    data[i][2]
    );

  break;
}
// We have found a solution, we need to check it's valid
for (j = 3; j < i; j++) {
  if (Math.abs(distance(point, points[j]) - data[i][j]) > threshold) {
    console.log("Could not verify solution", point, "for point " + (i + 1) + " against distance to point " + (j + 1));
    found = false;
    break;
  }
}
if (!found) {
  console.log("stopping");
  break;
}
points.push(point);
  }
  if (found) {
//console.log("complete solution", points);
return points;
  }
}

console.log(findPointsForDistances([
  [],
  [2344],
  [3333, 3566],
  [10000, 10333, 12520],
]));
console.log(findPointsForDistances([
  [],
  [2],
  [4, 2],
]));
console.log(findPointsForDistances([
  [],
  [4000],
  [5000, 3000],
  [3000, 5000, 4000]
]));
console.log(findPointsForDistances([
  [],
  [2928],
  [4938, 3437],
  [10557, 10726, 13535]
]));

var nbPoints, i;
for (nbPoints = 4; nbPoints < 8; nbPoints++) {
  for (i = 0; i < 10; i++) {
console.log(findPointsForDistances(generateData(nbPoints)));
  }
}

Fiddle here: https://jsfiddle.net/jacquesc/82aqmpnb/15/

Answer 2

Minimum working example. Remember that in canvas coordinates, the y value is inverted but you could do something like:

y = canvasHeight - y

If you also have negative points then if would take a little bit of extra work. Also it may be helpful in that case to draw lines and tick marks to visualize the axis.

let canvas = document.getElementById("canvas");
let ctx = canvas.getContext("2d");

let scale = 10;
let radius = 10;

function point(x, y) {
    ctx.fillRect(x*scale, y*scale, radius, radius);
}

// test
point(10, 15);
point(20, 8);

<html>
<body>
<canvas id="canvas" width=1000 height=1000></canvas>
</body>
</html>

Answer 3

There are plenty of libraries out there.

chartist.js is easy to use and responsive JavaS cript library. I used it last year for basic charts after trying many others but it was the only one that scaling easily in different screen sizes.

chartJS is another better looking library.

And you can use html5 canvas it's easy and fun but it will take time especially in scaling.

To scale and position, you should use the minimum and maximum values for x and y.

Good luck