均匀的生成圆和三角形内的随机点 - tenos - 博客园
一、均匀生成圆内的随机点

我们知道生成矩形内的随机点比较容易，只要分别随机生成相应的横坐标和纵坐标，比如随机生成范围[-10,10]内横坐标x，随机生成范围[-20,20]内的纵坐标y，那么(x,y)就是生成的随机点。由此，我们很容易的想到了算法1
算法1（正确的）：
每个圆对应一个外切矩形，我们随机生成矩形内的点，如果该点在圆内，就返回改点，否则重新生成直到生成的点在圆内。
该方法的缺点是有可能连续几次都生成不了符合要求的点。（可以求得：每次生成点时，该点有

的概率在圆内）

算法3（错误的）：

还可以根据极坐标，圆内的点可以如下描述

x = r*sin(theta)

y = r*cos(theta)

其中0 <= r <= R, 0 <= theta < 360

先随机生成[0, 360)内的theta，然后随机生成[0, R]内的r。

theta固定后，当r越靠近R，即点越靠近圆的边缘，因此如果r是[0，R]等概率生成的，那么圆的边缘的点会比靠近圆心处要稀疏。

算法4（正确的）：

和算法3一样还是根据极坐标

x = r*sin(theta)

y = r*cos(theta)

其中0 <= r <= R, 0 <= theta < 360

先随机生成[0, 360)内的theta，然后随机生成[0, 1]内的k, 且r = sqrt(k)*R。

根据根号函数的性质，这样使得r的分布在k靠近1（靠近边缘）的地方点变得较密，具体证明可参考here, 也可以参考论文“矩形和椭圆内均匀分布随机点定理及应用”，圆是椭圆的特例

def GeneratePointInCycle1(point_num, radius):

    for i in range(1, point_num+1):

        while True:

            x = random.uniform(-radius, radius)

            y = random.uniform(-radius, radius)

            if (x**2) + (y**2) < (radius**2):

                break

        plt.plot(x, y, '*', color = "black")

#博客算法3

def GeneratePointInCycle3(point_num, radius):

    for i in range(1, point_num+1):

        theta = random.random()*2*pi;

        r = random.uniform(0, radius)

        x = r*math.sin(theta)

        y = r*math.cos(theta)

        plt.plot(x, y, '*', color = "black")

#博客算法4

def GeneratePointInCycle4(point_num, radius):

    for i in range(1, point_num+1):

        theta = random.random()*2*pi;

        r = random.uniform(0, radius)

        x = math.sin(theta)* (r**0.5)

        y = math.cos(theta)* (r**0.5)

        plt.plot(x, y, '*', color = "black")   

一、均匀生成三角形内的随机点

算法6（正确的）

如图所示，三角形ABC有与之对应的矩形ABNM，且矩形面积是三角形的两倍，三角形ADC和CMA全等，CDB和BNC全等。

我们可以先生成矩形ABNM内的随机点P，如果P刚好在三角形ABC中，那么符合要求；如果P不在三角形ABC中，P要么在AMC中，要么在BNC中，如图P在BNC中，我们求P关于BC中点的的中心对称点，该点一定在三角形中。P在AMC中同理。这样可以保重三角形外的点都可以均匀的一一对应到三角形内部。

http://hustsxh.is-programmer.com/posts/40762.html

将三角形扩充成一个矩形
将矩形的两条边分别线性映射成一个随机生成器，这两个随机生成器相互独立
如果生成的D点在三角形外，将D以靠近的边为对称轴映射到三角形内的D'上。

显然随机生成的点在矩形内的分布是等概率的，第3部的映射也是一一对应的，因此在三角形内生成的点也是均匀分布的。

#判断点P是否在三角形ABC内,参考 http://www.cnblogs.com/TenosDoIt/p/4024413.html

def IsPointInTriangle(pointA, pointB, pointC, pointP):

    area_abc = ComputeTriangleArea(pointA, pointB, pointC)

    area_pab = ComputeTriangleArea(pointA, pointB, pointP)

    area_pbc = ComputeTriangleArea(pointP, pointB, pointC)

    area_pac = ComputeTriangleArea(pointP, pointA, pointC)

    return math.fabs(area_pab + area_pac + area_pbc - area_abc) < 0.000001

#计算一个点关于某一点的中心对称点

def ComputeCentralSymmetryPoint(point_src, point_center):

    return np.array([point_center[0]*2-point_src[0], point_center[1]*2-point_src[1]])

#对应博客算法6

def GeneratePointInTriangle2(point_num, pointA, pointB, pointC):

    for i in range(1, point_num+1):

        pointP = np.array([random.uniform(pointA[0], pointB[0]), random.uniform(pointA[1], pointC[1])])

        if not IsPointInTriangle(pointA, pointB, pointC, pointP):

            if pointP[0] > pointC[0]:

                pointP = ComputeCentralSymmetryPoint(pointP, np.array([(pointC[0] + pointB[0])/2, (pointC[1] + pointB[1])/2]))

            else:

                pointP = ComputeCentralSymmetryPoint(pointP, np.array([(pointC[0] + pointA[0])/2, (pointC[1] + pointA[1])/2]))

http://hustsxh.is-programmer.com/posts/40762.html

多边形内随机生成一个点

多边形可以先分割成多个三角形。根据面积的比率，使用一次随机生成器确定点落在哪个三角形内。然后在使用上面的方法在三角形内随机生成一个点。

Read full article from 均匀的生成圆和三角形内的随机点 - tenos - 博客园

均匀的生成圆和三角形内的随机点 - tenos - 博客园

多边形内随机生成一个点

Labels

Popular Posts