JavaScript实现矩形内随机点生成及分区概率分析面试题求解

核心思路 #

针对问题需求，我们分两种常见场景处理：轴对齐矩形（边平行于坐标轴）和旋转矩形（任意角度）。核心逻辑是：

1. 生成均匀分布的随机点；
2. 将矩形等分为4个面积相等的区域；
3. 统计各区域的点数量，计算落入概率。

一、轴对齐矩形实现 #

1. 步骤解析 #

• 获取矩形边界：从4个顶点中提取最小/最大x、y值，确定矩形范围；
• 生成随机点：在x和y的范围内生成均匀随机数，得到矩形内的点；
• 划分区域：通过x和y的中点将矩形分为4个象限区域；
• 统计概率：计数各区域的点数量，除以总点数得到概率。

2. 代码实现 #

// 获取矩形的边界范围
function getRectangleBounds(vertices) {
  const xs = vertices.map(v => v.x);
  const ys = vertices.map(v => v.y);
  return {
    minX: Math.min(...xs),
    maxX: Math.max(...xs),
    minY: Math.min(...ys),
    maxY: Math.max(...ys)
  };
}

// 生成N个矩形内的随机点
function generateRandomPoints(vertices, n) {
  const { minX, maxX, minY, maxY } = getRectangleBounds(vertices);
  const points = [];
  for (let i = 0; i < n; i++) {
    const x = minX + Math.random() * (maxX - minX);
    const y = minY + Math.random() * (maxY - minY);
    points.push({ x, y });
  }
  return points;
}

// 分析随机点在各区域的分布概率
function analyzePointRegions(points, vertices) {
  const { minX, maxX, minY, maxY } = getRectangleBounds(vertices);
  const midX = (minX + maxX) / 2;
  const midY = (minY + maxY) / 2;
  
  const counts = { p1: 0, p2: 0, p3: 0, p4: 0 };
  
  points.forEach(point => {
    if (point.x <= midX && point.y <= midY) counts.p1++;
    else if (point.x > midX && point.y <= midY) counts.p2++;
    else if (point.x <= midX && point.y > midY) counts.p3++;
    else counts.p4++;
  });
  
  const total = points.length;
  return {
    counts,
    probabilities: {
      p1: counts.p1 / total,
      p2: counts.p2 / total,
      p3: counts.p3 / total,
      p4: counts.p4 / total
    }
  };
}

// 示例使用
const axisAlignedVertices = [
  { x: 0, y: 0 }, // A
  { x: 4, y: 0 }, // B
  { x: 4, y: 2 }, // C
  { x: 0, y: 2 }  // D
];
const N = 10000;

const randomPoints = generateRandomPoints(axisAlignedVertices, N);
const result = analyzePointRegions(randomPoints, axisAlignedVertices);

console.log("各区域点数量：", result.counts);
console.log("各区域落入概率：", result.probabilities);

二、旋转矩形实现 #

1. 步骤解析 #

• 计算矩形中心：取4个顶点坐标的平均值；
• 生成随机点：通过仿射变换，将旋转矩形映射为单位正方形，生成随机点后再变换回原矩形；
• 划分区域：通过矩形中心绘制两条平行于矩形边的中线，将矩形分为4个全等区域；
• 统计概率：利用向量点积判断点位于中线的哪一侧，计数后计算概率。

2. 代码实现 #

// 生成旋转矩形内的随机点
function generateRotatedRectanglePoints(vertices, n) {
  // 计算矩形中心
  const center = {
    x: vertices.reduce((sum, v) => sum + v.x, 0) / 4,
    y: vertices.reduce((sum, v) => sum + v.y, 0) / 4
  };
  
  // 获取相邻顶点的边向量
  const A = vertices[0];
  const B = vertices[1];
  const D = vertices[3];
  const vecAB = { x: B.x - A.x, y: B.y - A.y };
  const vecAD = { x: D.x - A.x, y: D.y - A.y };
  
  // 计算边的半长和单位向量
  const halfLengthAB = Math.hypot(vecAB.x, vecAB.y) / 2;
  const halfLengthAD = Math.hypot(vecAD.x, vecAD.y) / 2;
  const normAB = { x: vecAB.x / (2 * halfLengthAB), y: vecAB.y / (2 * halfLengthAB) };
  const normAD = { x: vecAD.x / (2 * halfLengthAD), y: vecAD.y / (2 * halfLengthAD) };
  
  const points = [];
  for (let i = 0; i < n; i++) {
    // 生成[-1,1]范围内的随机系数
    const u = Math.random() * 2 - 1;
    const v = Math.random() * 2 - 1;
    // 计算点坐标
    const x = center.x + u * halfLengthAB * normAB.x + v * halfLengthAD * normAD.x;
    const y = center.y + u * halfLengthAB * normAB.y + v * halfLengthAD * normAD.y;
    points.push({ x, y });
  }
  return points;
}

// 分析旋转矩形内各区域的点分布概率
function analyzeRotatedRectangleRegions(points, vertices) {
  const center = {
    x: vertices.reduce((sum, v) => sum + v.x, 0) / 4,
    y: vertices.reduce((sum, v) => sum + v.y, 0) / 4
  };
  
  const A = vertices[0];
  const B = vertices[1];
  const D = vertices[3];
  const vecAB = { x: B.x - A.x, y: B.y - A.y };
  const vecAD = { x: D.x - A.x, y: D.y - A.y };
  
  // 边的法向量，用于判断点的位置
  const normalAB = { x: -vecAB.y, y: vecAB.x };
  const normalAD = { x: -vecAD.y, y: vecAD.x };
  
  const counts = { p1: 0, p2: 0, p3: 0, p4: 0 };
  
  points.forEach(point => {
    const delta = { x: point.x - center.x, y: point.y - center.y };
    const dotAB = delta.x * normalAB.x + delta.y * normalAB.y;
    const dotAD = delta.x * normalAD.x + delta.y * normalAD.y;
    
    if (dotAB <= 0 && dotAD <= 0) counts.p1++;
    else if (dotAB > 0 && dotAD <= 0) counts.p2++;
    else if (dotAB <= 0 && dotAD > 0) counts.p3++;
    else counts.p4++;
  });
  
  const total = points.length;
  return {
    counts,
    probabilities: {
      p1: counts.p1 / total,
      p2: counts.p2 / total,
      p3: counts.p3 / total,
      p4: counts.p4 / total
    }
  };
}

// 示例使用
const rotatedVertices = [
  { x: 1, y: 0 }, // A
  { x: 3, y: 2 }, // B
  { x: 1, y: 4 }, // C
  { x: -1, y: 2 } // D
];
const rotatedPoints = generateRotatedRectanglePoints(rotatedVertices, N);
const rotatedResult = analyzeRotatedRectangleRegions(rotatedPoints, rotatedVertices);

console.log("旋转矩形各区域点数量：", rotatedResult.counts);
console.log("旋转矩形各区域落入概率：", rotatedResult.probabilities);

关键说明 #

• 当N足够大时，各区域的落入概率会趋近于0.25，因为每个区域面积相等且点是均匀分布的；
• 轴对齐矩形的实现更简单高效，适合大多数常见场景；旋转矩形的实现通过向量运算保证了点严格在矩形内部。

内容的提问来源于stack exchange，提问作者Thomas_Ruby