三角形内随机生成一个点

在三角形内生成一个点

已有一个能生成0到1之间的数，并且这些数是均匀分布的随机生成器，给定一个任意的三角形，如何能在三角形内随机的生成一个点？

如上面这个三角形，点D就是三角形内部随机的一个点。一种简单的方法是通过如下公式生成D点：

或者

其中，a和b是两个独立随机生成器

要求等概率的情况

以上的两个公式很好的解决了在三角形内随机生成一个点的问题。然而三角形内每一个点被取到的概率一样吗？

拿

来说。a和b从0开始，每隔1/n取一个点。但n＝3时，a和b的取值为{0, 1/3, 2/3, 1}，将取到的D点在三角形种标出，如下图

很明显，靠近C点的地方D取值的概率更大。但n趋近于正无穷的时候，上面的图就是D取值的概率密度函数。很显然，三角形内每一个点被取到的概率并不相等。

为了克服这个问题，一名睿智的同学提出了如下的方法：

1. 将三角形扩充成一个矩形

2. 将矩形的两条边分别线性映射成一个随机生成器，这两个随机生成器相互独立

3. 如果生成的D点在三角形外，将D以靠近的边为对称轴映射到三角形内的D'上。

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

多边形内随机生成一个点

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

圆内随机生成一个点

给定一个半径为R的圆，如何在圆内等概率随机生成一个点？

圆用笛卡尔坐标系很不好处理，自然想到使用极坐标系。a表示OD与极轴的夹角，r表示D到坐标原点的距离。a从0度到360度，r从0到R。

如果将a和r直接线性映射到两个独立的随机生成器上。很明显圆内的概率密度函数并不相等。

当r为一个定值，D的轨迹为一个圆，圆的周长＝2 πr。如果我们能使D点落在任意一个圆的周长的单位长度上的概率相等，即可使圆内概率相等。简单的说，如果有一个随机生成器取r的概率和r线性相关，就可以搞定这个问题。

构造如下的方法解决这个问题：

如图，构造一个边长为R的等腰直角三角形。使用等概率在三角形内生成一个点的方法生成D点。将R减D点的x坐标设置为r。

此时，r取值概率与r的大小线性相关，满足上面条件。因此，用此方法生成的点在圆内等概率分布。

今天接触到两个很好用的东西，一个是markdown，一个是pandoc。在此mark下。

markdown

markdown是一种非常简介的文本标记语言，网上也有很多教程，这里就不多说了。尝尝鲜，篇博文就是用markdown写的。

pandoc

什么是pandoc呢？官网上是这么是的“如果你要把文件从一种文本标记语言转到另一种文本标记语言，pandoc就是你的瑞士'军刀'”

下面是张来自于官网的一张关于pandoc转换能力的图片，果断亮瞎双眼

转换

从md文件转化成latex文件格式执行如下代码 pandoc file.md -o file.tex

从md文件直接转化成pdf文件格式执行如下代码 pandoc file.md -o file.pdf

pandoc对中文支持不是很好，md转化成tex没有问题，转化成pdf中文出不来。这个有待进一步折腾折折腾

干什么用

• 我准备用markdown来写日常的一些小文档，可以html格式发布。如果能解决pdf中文问题，也可以直接转成pdf；如果不行，那就先转成latex然后在转pdf。

• 由于markdown较tex简洁很多，可以先用markdown搭框架，然后转tex再添细节。虽然这有点多此一举，tex的标签确实复杂了点

• 之前用latex排的东西可以直接转成html格式发布

之前也接触过遗传算法，只是没有实践，正巧这次模式识别的课程上老师提到，并布置了一个小练习题，便拿来做做吧。

题目本来要求是求Rosenbrock函数f(x, y) = (x-1)² + 100(y-x²)²在[-2,-2,2,2]之间的最大值，稍加分析，或者看下面的图就会发现，其实当(x, y) = (-2, -2)时，f(x,y)即可取到最大值。

觉得这样没什么意思，于是自己稍微把题目改了下，把x，y都变成sin x，sin y，函数就变成f(x, y) = (sin x-1)² + 100(sin y-sin²x)²

这是一个很漂亮的双峰函数。下面我们来讨论如何用遗传算法来求这个函数的极大值。

编码方式

由于x,y的范围都是[-2,2]，那么可以考虑使用11个二进制的定点小数来编码0.000到2.047这2048个定点小数。在加上1个二进制位符号为，即可表示[-2.047, 2.047]，刚好可以覆盖[-2,2]并且精度为0.001。x和y都采用相同的方法编码，然后拼接在一起，形成一个24位的二进制整数。实现过程中可以使用整数保存，位运算做遗传和变异。

原始个体生成方式

根据编码方式，每一个个体可以用24个二进制位表示，于是可以很简单的随机生成一个[0,1<<24)的整数表示一个个体。生成30个祖先个体

确定遗传、变异方式

遗传方式：任取两个个体(A,B)进行交配，生成两个子个体(C,D)。C基因序列的低k个二进制位来自于A，高24-k个二进制位来自于另一个父本B，其中0<k<24。D基因序列和C的情况真好相反，其低k个二进制位来自于B，高24-k个二进制位来自于A。用python语言表示为

k = randint(1, 23)
mask = (1<<k) - 1
C = A & mask | B & ~mask
D = B & mask | A & ~mask

变异方式：随机选取24个二进制位中的某一个，如果该位0变成则变成1，否则变成0

from random import randint
from numpy import sin

def decode(g):
    return [((g&0xfff) - 2048) * 0.001, ((g>>12) - 2048) * 0.001]

def function_g(g):
    x = decode(g)
    return function(x[0], x[1])
    
def function(x, y):
    return 100 * (sin(x) ** 2 - sin(y)) ** 2 + (1 - sin(x)) ** 2

def cmp(g1, g2):
    key = function_g(g1) - function_g(g2)
    if key > 0: return 1
    elif key < 0: return -1 
    else: return 0

def GA(num = 30, round = 10):
    gene = [randint(0, (1<<24) - 1) for i in range(num)]
    rnd = 0
    while rnd < round:
        rnd += 1
        gene_c = [g ^ (1<<randint(0, 23))  for g in gene]
        gene_h = []
        for g1 in gene:
            for g2 in gene:
                mask = (1<<randint(1, 23)) - 1
                gene_h.append(g2 & ~mask | g1 & mask)
                gene_h.append(g1 & ~mask | g2 & mask)
        gene_tot = gene + gene_h + gene_c
        gene_tot.sort(cmp = cmp, reverse = True)
        gene = gene_tot[:num]
        print "round", rnd, ":", decode(gene[0]), function_g(gene[0]) 
    return decode(gene[0]) + [function_g(gene[0])]
    
if __name__ == '__main__':
    print GA(30, 10), 

round 1 : [1.571, -1.464] 397.724305554
round 2 : [1.571, -1.539] 399.797824716
round 3 : [-1.605, -1.548] 403.426161017
round 4 : [-1.605, -1.556] 403.486264841
round 5 : [-1.541, -1.591] 403.561685598
round 6 : [-1.541, -1.575] 403.639747518
round 7 : [-1.573, -1.579] 403.984587994
round 8 : [-1.573, -1.571] 403.998039526
round 9 : [-1.569, -1.571] 403.998694536
round 10 : [-1.569, -1.571] 403.998694536

可以看到，结果收敛得非常快，并且经过10次迭代，结果基本稳定。