六角形/形狀中的隨機點

Question

我有一個簡單的六角形網格，我選擇一組六邊形，然後填充一些隨機點。

讓我解釋一下生成點的具體程序：

• 使用十六進制的座標列表，我選擇六邊形。
• 將六邊形組合成區域。
• 爲每個區域單獨存儲所有邊緣點。
• 遍歷領域：
  • 計算區域邊界（對於definig用於隨機點發生器的範圍內所需的）
  • 繪圖區域（邊界）的正方形。 （查看計算是否正確）
  • 根據邊界平方min，max值生成隨機點
  • 測試點是否在區域形狀內。 （形狀由區域邊緣點定義）
  • 如果點通過上述測試，則​​它被推入數組中。
• 遍歷點陣列並在屏幕上繪製它們。

現在我嘗試了這兩種方法來確定點是否位於特定形狀內。

cn_PnPoly: function(P, V, n){ ///// Point , array of vertices , array size //// 
     var cn = 0, vt = 0.0; 
     for (var i=0; i< (n-1); i++) { // edge from V[i] to V[i+1] 
      if (((V[i].y <= P.y) && (V[i+1].y > P.y))  // an upward crossing 
      || ((V[i].y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing 
       // compute the actual edge-ray intersect x-coordinate 
       vt = (P.y - V[i].y)/(V[i+1].y - V[i].y); 
       if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect 
        ++cn; // a valid crossing of y=P.y right of P.x 
      } 
     } 
     return (cn&1); // 0 if even (out), and 1 if odd (in) 
    }, 

結果：

isInHexBounary: function(p, points, l){ ///// Point , array of vertices , array size //// 
     var result = false; 
      for (i = 0, j = l - 1; i < l; j = i++) { 
      if ((points[i].y > p.y) != (points[j].y > p.y) && (p.x < (points[j].x - points[i].x) * (p.y - points[i].y)/(points[j].y-points[i].y) + points[i].x)) { 
       result = !result; 
      } 
      } 
      return result; 
    }, 

結果：

我認爲第一種方法需要知道所有的點按特定的順序，這就是爲什麼它工作不正常。 但第二個似乎工作幾乎正確，除了一些部分。任何想法我做錯了什麼？

更新：

它的轉向指出，對於MOS TOF它需要有個特定的順序algorhytms，每個相對平均中心點點，所以我計算的角度。然後按角度對所有點進行排序。兩種算法現在都返回相似的結果雖然有一些點通過區域形狀泄漏。

findCenter: function(points){ 
     var x = 0, y = 0, i, len = points.length; 
     for (i = 0; i < len; i++) { 
      x += points[i].x; 
      y += points[i].y; 
     } 
     return {x: x/len, y: y/len}; 
    }, 

    findAngles: function(c, points){ 
     var i, len = points.length, p, dx, dy; 
     for (i = 0; i < len; i++) { 
      p = points[i]; 
      dx = p.x - c.x; 
      dy = p.y - c.y; 
      p.angle = Math.atan2(dy, dx); 
     } 
    }, 

    sortByAngle: function(points){ 
     points.sort(function(a, b) { 
      if (a.angle > b.angle) return 1; 
      else if (a.angle < b.angle) return -1; 
      return 0; 
     }); 
    }, 

結果：

Answer 1

坦率地說，我會讓它更簡單。

1. 在一個單一的六邊形中進行採樣。只需製作尺寸爲（2s，​​2scos（30）），樣本（x，y）的邊界框，如果它位於六邊形之外，則將其拒絕。效率應該是3/4（檢查hexagon area）。位置在本次抽查六邊形（0,0），使得取樣是很容易的，而且，保持六邊形中心，說的陣列什麼是更重要的，非常可驗證

2. 對於每一個區，大小爲N

3. 樣品分兩步進行。首先，抽取整數1 ... N並選擇該區域內將要選擇的六邊形。其次，從步驟＃1的 （x，y）開始，從（0,0）處的單個六邊形開始採樣。最後， 移採樣的（X，Y）由隨機選擇的六邊形中心

UPDATE

實際上，相信有一種方法來樣點（X，Y）在一個具有100％效率的單六角形，沒有任何拒絕/接受。看看上面的圖片。紅色是整個六邊形，矩形藍色區域是您採樣點的位置。如果採樣點位於紅色區域內，則將其取下並繼續。如果它不在紅色和內部藍色A三角形中，則將其映射爲黑色A'三角形。如果點不在紅色但是在藍色B三角形中，則將其重新映射爲黑色B'三角形

重新映射是相當簡單的線性變換。

最後，你有（用於採樣隨機點一個用來選擇 目的地六邊形，二）三個隨機數作爲輸入採樣，這將保證所需區域的某處返回隨機點

UPDATE II

正如Denis Sheremet所指出的，更好的映射將是A->B'和B->A'。假設（0,0）處的六邊形中心，總體上只有兩個反射 - 一個在中心，另一個在三角形的中間。