如何高效生成矩形内距定点A满足距离范围的随机点B？

核心思路：缩小采样范围，减少无效尝试 #

你的朴素方法性能差的核心原因是采样范围太大，包含了大量矩形外的无效区域。下面是几种更高效的方案，按实现复杂度和性能排序：

方案1：环形完全在矩形内时直接采样 #

当A点的环形区域完全落在矩形内部（即 d_max ≤ min(A.x - x0, x1 - A.x, A.y - y0, y1 - A.y)），直接生成环形内的均匀随机点：

• 生成随机角度：θ = 2 * π * rand()（rand() 生成[0,1)区间的随机数）
• 生成随机半径：r = sqrt(d_min² + (d_max² - d_min²) * rand())（用平方根转换保证环形内的均匀分布）
• 计算B点坐标：B.x = A.x + r * cosθ，B.y = A.y + r * sinθ

方案2：裁剪采样范围后快速过滤 #

当环形有部分超出矩形时，先把采样范围限制在矩形与环形的交集外接矩形内，再过滤距离约束：

1. 计算B点的有效坐标范围：
   • x轴范围：x_low = max(x0, A.x - d_max)，x_high = min(x1, A.x + d_max)
   • y轴范围：y_low = max(y0, A.y - d_max)，y_high = min(y1, A.y + d_max)
2. 在这个小矩形内生成随机点 (x, y)
3. 计算距离平方（避免开根号，提升速度）：dist_sq = (x - A.x)² + (y - A.y)²
4. 如果 d_min² ≤ dist_sq ≤ d_max²，则保留该点；否则重新采样
   这种方法的采样范围比朴素方法小得多，无效尝试次数会大幅减少，实现也简单，适合大多数场景。

方案3：极坐标约束下的精准采样（零拒绝率） #

如果追求极致性能，不想有任何无效尝试，可以用极坐标结合矩形边界的约束：

1. 先计算A到矩形四条边的距离：left = A.x - x0，right = x1 - A.x，bottom = A.y - y0，top = y1 - A.y
2. 针对每个角度θ，计算该方向上的有效半径范围：
   • 若 cosθ ≠ 0，x方向允许的最大半径 r_x = (cosθ > 0 ? right : left) / abs(cosθ)
   • 若 sinθ ≠ 0，y方向允许的最大半径 r_y = (sinθ > 0 ? top : bottom) / abs(sinθ)
   • 该角度下的有效最大半径 r_max = min(d_max, r_x, r_y)
   • 有效最小半径 r_min = max(d_min, 0)
   • 只有当 r_max ≥ r_min 时，这个角度区间才是有效的
3. 随机选择一个有效角度区间，在 [r_min, r_max] 内生成半径r，再计算B点坐标
   这种方法实现稍复杂，但完全没有拒绝采样，性能最优。

额外优化建议 #

• 全程用距离平方代替欧氏距离，避免开根号的计算开销
• 若只需近似均匀分布，方案2完全足够，平衡了实现复杂度和性能

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