javascripthtmlgraph-drawing

Draw Map in Browser out of 2 Dimensional Array of Distances


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  

enter image description here

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   

Solution

  • 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:

    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/