图形范围内均匀获取随机点的问题

心羽 · 发表于 2021-8-13 02:06:44

【游客模式】——注册会员，加入11RIA 闪客社区吧！一起见证Flash的再次辉煌……

您需要登录才可以下载或查看，没有帐号？立即注册

x

本帖最后由 TKCB 于 2021-8-16 15:42 编辑

图形范围内均匀获取随机点的问题是指，在某个规则的图形下随机获取图形内的一点；当多次随机获取后，使随机的点在图形内较为均匀分布。

在以往的项目经历中，主要用到的就是圆形和矩形。今天由于在某个技术群讨论到了三角形的实现，所以想在ASer自己的论坛内整理一下目前的一些心得，也算是抛砖引玉，希望能讨论出更丰富的内容来。

一、矩形
普通的矩形在随机获取点的问题中应该是最简单的一种了，矩形ABCD， AB//CD//x轴， AD//BC//y轴，
可以通过Math.random() * width + Math.random() * height + A来求得随机坐标点。

下面是矩形内10000次随机取点的结果和实验代码。

标准矩形

游客，如果您要查看本帖隐藏内容请回复

二、平行四边形
前面矩形的部分看起来非常简单，但却是建立在矩形摆放的很标准的基础上的。若矩形发生一点旋转，该怎么办呢？
可能会有精通矩阵运算的大神说，可以先通过宽高计算出水平摆放状态下的随机坐标点位置，然后再通过旋转矩阵得到正确的结果。
这的确也是一种O(1)的计算方法，但无法引申出平行四边形的解法。接下来我要介绍自己的做法。

平行四边形分解

过平行四边形内部任意一点P，做EF//AB，交AD于点E，交BC于点F。

接下来要使用向量计算，为了便于书写，所有向量采用粗体字表示，点坐标使用普通字体表示。
O表示原点，因为A点坐标的数值与向量OA的数值相等，所以接下来点A的坐标都以OA来表示

以A为基准点，则向量AP=AE+EP
所以P点的坐标公式为：OP = OA + AP = OA + AD * r1 + AB * r2
观察图像可知，无论r1取什么值，EF的长度都是一样；并且随着E点的变动，在EF上的点可以铺满整个图形。在这种情况下使用Math.random()随机r1和r2，取点的概率分布一定是均等的。

下面是依照这个计算方式随机10000次的结果和实验代码。

平行四边形

游客，如果您要查看本帖隐藏内容请回复

三、圆

圆内最简单直接的方式就是采用极坐标的方式了。
通俗点的理解方式就是，以圆心为起点，随机一个角度，然后朝这个角度移动不超过半径的距离，即可得到圆内任意一点的坐标。

[Actionscript3] 纯文本查看 复制代码

import flash.geom.Point;

var pA:Point = new Point(160, 60);
var pB:Point = new Point(390, 60);
var pC:Point = new Point(390, 340);
var pD:Point = new Point(160, 340);

function drawRect():void {
        this.graphics.lineStyle(1, 0, 1);
        this.graphics.moveTo(pA.x, pA.y);
        this.graphics.lineTo(pB.x, pB.y);
        this.graphics.lineTo(pC.x, pC.y);
        this.graphics.lineTo(pD.x, pD.y);
        this.graphics.lineTo(pA.x, pA.y);
}
function drawRandomPoint():void {
        var width:Number = pB.x - pA.x;
        var height:Number = pD.y - pA.y;
        var tx:Number = pA.x + Math.random() * width;
        var ty:Number = pA.y + Math.random() * height;
        this.graphics.drawCircle(tx, ty, 0.5);
}
this.drawRect();
this.graphics.lineStyle(1, 0xff0000, 0.6);
for(var i:int = 0; i < 10000; i++) {
        this.drawRandomPoint();
}

但是这样的计算却得到了一个不好的结果

圆的错误示范

可以明显看出随机点大量向圆心靠拢，四周区域显得稀疏。

思考一下就明白了，这段代码中随机的半径是(0~1)R内均匀分布的。但越靠近圆心，根据角度选择的圆的落点范围越小，反之靠近边缘处落点范围大，才造就了这样的结果。

那么怎么处理这个问题呢？

在R随机变化的过程中，通过极坐标计算出来的点的位置的选取范围实际上是随机出来的r对应的小圆上任意一点。
圆的讲解.png

在平行四边形的问题中，第一个变量发生变化，对第二个变量的取值范围没有产生影响，所以采用均匀的随机数就可以了。
但在圆的问题中，取值范围是小圆的圆周，长度为2πr，与r的随机结果产生了相关性。想消除这种相关性带来的影响，需要对r的随机数开平方运算，使随机点靠近圆心的概率小于远离圆心的概率。这个开平方运算并不是随便想的，只是我没有经过严谨的数学推导，无法呈现给大家。
下面是概率经过开平方修正后的10000次随机结果和代码：
圆的正确示范.png

游客，如果您要查看本帖隐藏内容请回复

四、三角形
三角形采用向量方式解决

三角形原理

过三角形内任意一点P，做DE//BC，交AB于D，交AC于E，
则有△ADE相似于△ABC，
可知|DE| : |AD| = |BC| : |AB|
设随机数r1、r2，使AD = AB * r1, DP = DE * r2
可以推导出 DP = BC * r1 * r2

那么以A为基准点，使用向量表达式求任意点P的坐标公式就变成了：
OP = OA + AP
   = OA + AD +DP
   = OA + AB * r1 + BC * r1 * r2

因为r1的变化会导致DE的长度变化，并且因三角形相似原理，DE长度推导出与r1相关。
为了避免随机点的分布向A点聚拢，需要将r1的随机数开平方。

先看下r1和r2直接使用Math.random()的错误示范：

三角形错误