javascript - 六边形/形状中的随机点

Question

我有一个简单的六边形网格，我在其中选择一组六边形，然后用一些随机点填充这些六边形。

让我解释一下生成点的具体过程:

• 我使用六 Angular 坐标列表选择六边形。
• 将六边形分组为区域。
• 分别为每个区域存储所有边缘点。
• 遍历区域:
  • 计算区域边界(定义随机点生成器的范围所必需的)
  • 绘制区域(边界)正方形。 (看计算是否正确)
  • 根据边界平方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 算法，需要按特定顺序排列点，因此我计算了每个点相对于平均中心点的 Angular 。然后按 Angular 对所有点进行排序。这两种算法现在返回相似的结果。虽然有一些点通过区域形状泄漏。

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,2s cos(30))、样本 (x,y) 的边界框，如果它在六边形之外则拒绝它。效率应该是 3/4(检查 hexagon area )。将此采样六边形定位在 (0,0) 处，这样采样非常容易，而且，更重要的是，非常可测试

2. 为每个区域维护六边形中心数组，例如，大小为 N

3. 分两步采样。首先，采样整数 1...N 并选择什么区域中的六边形即将被选中。第二，从你的样本(x,y) 来自步骤 #1，来自位于 (0,0) 的单个六边形。最后的，通过随机选择的六边形中心对 (x,y) 进行移位采样

更新

实际上，我相信有一种方法可以在单个六边形中以 100% 的效率对点 (x,y) 进行采样，而不会出现任何拒绝/接受。看上面的图片。红色是整个六边形，矩形蓝色区域是您采样点的地方。如果采样点在红色区域内，则将其拿走并继续前进。如果它不在红色和蓝色 A 三 Angular 形内部，则将其映射到黑色 A' 三 Angular 形。如果点不在红色中而是在蓝色 B 三 Angular 形中，则将其重新映射到黑色 B' 三 Angular 形

重映射是非常简单的线性变换。

最后，您使用三个随机数作为输入进行采样(一个用于选择目标六边形，两个用于采样随机点)并且它会保证在所需区域的某处返回随机点

更新二

正如 Denis Sheremet 所指出的，更好的映射是 A->B' 和 B->A'。假设六边形中心在 (0,0)，总体上只有两个反射 - 一个在中心上方，另一个在三 Angular 形中间上方