CODEWITHSUNDEEP
javascriptnode.jsmaps
user1500053
user1500053

Reputation: 79

How could I generate random locations with distances between each other in javascript?

I want to design a function that can generate a 'map' of sorts.

For example:

Location A is created, it is located at some position X

Location B is created, it is located at some position Y, we know the distance between X, Y

Location C is created, we know the distance from C to B, how do we calculate C to A?

Using a triangle method, I suppose I could also assign a random angle and calculate the third side, but what would I do if I added a Location D, E, F randomly? Would I be calculating multiple triangles that get exponentially worse with every addition?

Upvotes: 0

Views: 690

Answers (3)

broofa
broofa

Reputation: 38102

Yes, it gets geometrically more complicated with each point you add.

The problem is that even if you know the lengths of all three sides of a triangle, you still don't know the orientation. To illustrate your example:

enter image description here

You're defining ABC by specifying distances dAB and dBC (which gives you dAC). But you actually have two possible triangles, ABC and ABC'. Which means if you add a fourth point, D, by specifying it's distance to one of the points on ABC (e.g. dCD), you've added a 2nd triangle, which can also have one of two orientations, making for a total of four possible solutions. As you can see, orientation doesn't matter for determining distance between two points on the same triangle, but for determining distances between points on different triangles, it does.

Upvotes: 0

xiaoyi
xiaoyi

Reputation: 6741

Say you want to generate a list of locations L[1..n], you just randomly pick next location and scan over the L to guarantee the distance is over a threshold, otherwise, pick again.

Then, push this into your list L. So the total run time of generating a n elements list is O(n^2). When n < 1000, this is fast enough. The following method is guaranteed to terminate, which is designed for a relatively small read-to-pick list, say up to 1,000,000.

function generateList(orgList, numberToOutput) {
  if (orgList.length < numberToOutput)
    return false;
  var orgListClone = orgList.slice(0);
  var L = [];
  while (L.length < numberToOutput && orgListClone.length > 0) {
    var n = parseInt(Math.random() * orgListClone.length);
    // Assume we pick n-th element in the list.
    var ok = true;
    for (var j = 0; j < L.length; j++)
      if (distance(orgListClone[n], L[j]) < kThreshold) {
        // n is not an option, swap orgListClone[n] with the last element and pop it out.
        orgListClone[n] = orgListClone[orgListClone.length - 1];
        orgListClone.pop();
        ok = false;
        break;
      }
    if (ok) {
      // All tests passed
      L.push(orgListClone[n]);
      orgListClone[n] = orgListClone[orgListClone.length - 1];
      orgListClone.pop();
    }
  }
  if (L.length == numberToOutput)
    return L;
  // Failed to find the list
  return null;
}

Another solution is to calcuate distances between each of the locations ahead, and make a list of too close locations for each location.

So that after each pick, just merge the too close locations to the current set, which takes O(n). And then pick another location which is not included in this set. This method only works when the read-to-pick list is large enough, so that the probability (1 - |too close list| / |read-to-pick list|) of choosing a location not included in the set is large. This will take up to O(nm) in total, where m is the average |too close list|.

function generateList(orgList, numberToOutput) {
  if (orgList.length < numberToOutput)
    return false;
  var tooCloseSet = {};
  var L = [];
  var lastLengthOfL = 0;
  var repickCount = 0;
  for (L.length < numberToOutput) {
    if (l.length == lastLengthOfL) {
      if (++repickCount > 10)
        return false;
    } else {
      lastLengthOfL = l.length;
      repickCount = 0;
    }
    var n = parseInt(Math.random() * orgList.length);
    if (n in tooCloseSet)
      continue;
    L.push(orgList[n]);
    mergeSet(tooCloseSet, orgList[n].tooCloseList);
  }
  return L;
}

Upvotes: 1

Aesthete
Aesthete

Reputation: 18850

You could try something like this, I haven't tested it, so it's just conceptual at this point.

You could just generate an array of randomly placed points, and each point could hold it's own array of distances, calculated using basic trigonometry.

function Point(x, y) {
  return {
    x: x, 
    y:y, 
    addRelative: function(pt) {
       this.realtivePoints[pt] = abs(sqrt(pow((this.x-pt.x),2) + pow((this.y-pt.y),2)));
    },
    relativePoints: {}
};

var randPoints = []; // Lets assume this has a collection of random Point objects

for(var i=0; i<randPoints.length; i++) {
  for(var j=0; j<randPoints.length; j++) {
    randPoint[i].addRelative(randPoints[j]);
  }
}

randPoints[0].relativePoints[randPoints[1]]; // Dist from first to second point.

Upvotes: 0

Related Questions