@
kaiki @
chengfeng1992 @
XiaoxiaoPu @
JeffGe @
fbxshit 想了一下,找到了一个我认为正确的方法。
但基本原理很简单,就是类似前面提到的,在多边形内随机采样取点。
先看一下为什么发红包跟多边形取点会关联起来,举例来说,发红包的条件可以表示为:
x+y+z=11,(给 3 个人发 11 元红包)
x>=2, x<=8, y>=2, y<=8, z>=2, z<=8,
(给每个人发的红包在 2 和 8 之间)
用几何的观点来看,这几个条件表示的是,使用一个立方体(x,y, z 的范围都在 2 ~ 8 之间),去截取一个平面,平面的方程为 x+y+z=11 。平面被立方体截取的部分(在立方体内的),就是满足题目要求的解。然后求一个随机解就变成了在被截取的平面上随机采样采点。
如果把这个图形画出来,会发现平面被立方体所截得的图形是一个等边三角形。三个顶点分别是(2,2,7),(2,7,2),(7,2,2)
所以,现在的问题变成了:已知一个三角形(凸多边形),怎么才能做到均匀采样其内部的点?
这个就要感谢凸集的美好性质了:凸集内部的任何一点都可以唯一表示成凸集顶点的线性组合。
假设三角形的三个顶点分别是 P0, P1, P2,那么三角形内部的任一点,可以唯一表示为 a*P0+b*P1+c*P2,其中 a+b+c=1 。
所以要想随机采样三角形内部的点,只要随机取 a,b,c 这三个数,保证和为 1 即可。
上面是 3 维的简单情形,如果发红包给更多的人,就变成了更高维的,但原理是一样的。原来的平面变成了高维平面,原来的立方体变成了高维立方体。关键是求出立方体在平面上截得的顶点。找到所有的顶点后,对这些顶点线性组合就 ok 了。