0

ある種の「マップ」を生成できる関数を設計したいと思います。

例えば：

場所Aが作成され、ある位置Xに配置されます

場所Bが作成され、ある位置Yに配置され、XとYの間の距離がわかります。

場所Cが作成され、CからBまでの距離がわかっていますが、CからAまでをどのように計算しますか？

三角形の方法を使用すると、ランダムな角度を割り当てて3番目の辺を計算することもできると思いますが、場所D、E、Fをランダムに追加した場合はどうなりますか？追加するたびに指数関数的に悪化する複数の三角形を計算しますか？

4

3 に答える 3

1

場所のリストを生成したい場合はL[1..n]、次の場所をランダムに選択してスキャンしL、距離がしきい値を超えていることを確認します。それ以外の場合は、もう一度選択します。

次に、これをリストにプッシュしますL。したがって、要素リストを生成する合計実行時間はO（n ^ 2）です。n <1000の場合、これは十分に高速です。次のメソッドは確実に終了します。これは、読み取りから選択までのリストが比較的小さく、たとえば最大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;
}

もう1つの解決策は、前方の各場所間の距離を計算し、各場所に対して近すぎる場所のリストを作成することです。

そのため、各ピックの後で、近すぎる場所を現在のセットにマージします。これにより、O（n）が使用されます。次に、このセットに含まれていない別の場所を選択します。この方法は、read-to-pickリストが十分に大きい場合にのみ機能するため1 - |too close list| / |read-to-pick list|、セットに含まれていない場所を選択する確率（）が大きくなります。これには合計で最大O（nm）がかかります。ここで、mは平均|近すぎるリスト|です。

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

あなたはこのようなことを試すことができます、私はそれをテストしていません、それでそれはこの時点でただ概念的です。

ランダムに配置されたポイントの配列を生成するだけで、各ポイントは、基本的な三角法を使用して計算された独自の距離の配列を保持できます。

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 に答える
0

はい、追加するポイントごとに幾何学的に複雑になります。

問題は、三角形の3つの辺すべての長さを知っていても、方向がわからないことです。あなたの例を説明するために：

ここに画像の説明を入力してください

あなたは距離dABとdBC（あなたにdACを与える）を指定することによってABCを定義しています。しかし、実際には、ABCとABC'の2つの可能な三角形があります。つまり、ABC上のポイントの1つ（dCDなど）までの距離を指定して4番目のポイントDを追加すると、2番目の三角形が追加されます。これも2つの方向のいずれかを持つことができ、合計4つになります。可能な解決策。ご覧のとおり、同じ三角形上の2つのポイント間の距離を決定する場合は向きは重要ではありませんが、異なる三角形上のポイント間の距離を決定する場合は重要です。

于 2012-11-10T13:30:14.537 に答える