0

我想设计一个可以生成各种“地图”的功能。

例如：

位置 A 已创建，它位于某个位置 X

创建位置 B，它位于某个位置 Y，我们知道 X、Y 之间的距离

创建位置 C，我们知道从 C 到 B 的距离，我们如何计算 C 到 A？

使用三角形方法，我想我也可以分配一个随机角度并计算第三边，但是如果我随机添加一个位置 D、E、F 该怎么办？我会计算多个三角形，每次添加都会变得更糟吗？

4

3 回答 3

1

假设您要生成位置列表L[1..n]，您只需随机选择下一个位置并扫描L以确保距离超过阈值，否则，再次选择。

然后，将其推送到您的列表中L。所以生成元素列表的总运行时间是 O(n^2)。当 n < 1000 时，这已经足够快了。下面的方法保证会终止，它是为相对较小的 read-to-pick 列表设计的，比如最多 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;
}

另一种解决方案是计算前方每个位置之间的距离，并为每个位置制作一个距离太近的位置列表。

因此，在每次选择之后，只需将太近的位置合并到当前集合，这需要 O(n)。然后选择另一个不包含在此集合中的位置。此方法仅在 read-to-pick 列表足够大时有效，因此1 - |too close list| / |read-to-pick list|选择未包含在集合中的位置的概率 ( ) 很大。这总共需要 O(nm)，其中 m 是平均 |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;
}
于 2012-11-10T06:47:21.400 回答
0

是的，您添加的每个点都会在几何上变得更加复杂。

问题是即使你知道三角形所有三个边的长度，你仍然不知道方向。为了说明您的示例：

在此处输入图像描述

您通过指定距离 dAB 和 dBC（它为您提供 dAC）来定义 ABC。但实际上你有两个可能的三角形，ABC 和 ABC'。这意味着如果你添加第四个点 D，通过指定它到 ABC 上的一个点的距离（例如 dCD），你就添加了第二个三角形，它也可以有两个方向之一，总共有四个可能的解决方案。如您所见，方向对于确定同一三角形上两点之间的距离无关紧要，但对于确定不同三角形上两点之间的距离，它确实如此。

于 2012-11-10T13:30:14.537 回答
0

你可以试试这样的东西，我还没有测试过，所以现在只是概念性的。

您可以只生成一个随机放置的点数组，每个点都可以保存自己的距离数组，使用基本三角法计算。

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.
于 2012-11-10T06:24:36.623 回答