如何在javascript中生成彼此之間距離的隨機位置？

Question

我想設計一個可以生成各種「映射」的函數。

例如：

位置A被創建，它位於一些位置X被創建

位置B，它位於一些位置Y，我們知道X之間的距離，Y

位置C已創建，我們知道從C到B的距離，我們如何計算C到A？

使用三角形方法，我想我也可以指定一個隨機角度並計算第三面，但如果隨機添加位置D，E，F，我該怎麼辦？我會計算多個三角形，每增加一個指數級的差異？

Answer 1

說你要生成的位置L[1..n]列表，你只是隨機挑選下一個位置，並掃描整個L，以保證傳輸距離超過閾值，否則，重新選取。

然後，將其推入列表L。所以生成一個n元素列表的總運行時間是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; 
} 

另一種解決方法是計算每個位置之間的距離，併爲每個位置列出太近的位置。

因此，在每次選擇後，只需將O（n）合併到當前集合太近的位置。然後選擇另一個不包含在這個集合中的位置。此方法僅適用於讀取選擇列表足夠大時，以便選擇未包含在該集合中的位置的概率（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; 
} 

Answer 2

你可以嘗試這樣的事情，我沒有測試過，所以這只是概念性的。

您可以生成一個隨機放置點的數組，每個點可以保存它自己的距離數組，使用基本的三角函數計算。

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. 

Answer 3

是的，隨着每個點的添加，它的幾何學變得更加複雜。

問題是，即使你知道三角形的所有三邊的長度，你仍然不知道方向。通過指定距離DAB和DBC（它給你DAC）

你定義ABC：爲了說明你的榜樣。但你實際上有兩個可能的三角形，ABC和ABC'。也就是說，如果通過指定第四個點D的距離來指定它與ABC上的其中一個點（例如dCD）的距離，則添加了第二個三角形，該三角形也可以具有兩個方向中的一個，從而總共四個點可能的解決方案。如您所見，定位對於確定同一三角形上兩點之間的距離無關緊要，但對於確定不同三角形上點之間的距離，方向確實無關緊要。