刚刚写了一个小程序，计算2维外凸多面体的外围周长和面积。

下面的图线是所算出的周围长度和内部面积随着beta 参数的变化。

这里给出不同beta参数下所算出的周长和面积，只是为了显示所算的精度，实际计算中，只需要计算两次就可以，既可以给出目标值，还可以给出误差。

蒙特卡洛算法一般也叫Randmization method.
蒙特卡洛算法的每一次选择样本点都要验算所有的不等式限制条件，Complexity 是m*n,

假设所选的长方形面积是A,所要计算的多面体的面积是B, 如果所要求的精度是p，所要求的样本数至少是N > A/(B*p). 通常A/B至少上千。于是，达到10位数的精度，总的Complexity 大致是N=10^13 *m*n

我这里给出的算法应该是1000*m*n. 1000 是对圆周积分时对2×pi 角度细分的数目。

对于任何由一系列连续的非线性函数所给出的外凸区域，都可以用这种方法来求出表面面积和体积。那将是另外的一个课题。

另外，蒙特卡洛方法在很多情况下并不适用。比如对下面的问题：

x+y <= 0.00001
-x-y <= 0.00001
x-y <= 10^8
-x+y <= 10^8

这是一个细长方体。你要选择的长方形A的面积至少要10^17, 而B～10^3,即便是N=10^14 计算精度也只能是0.1.




下面的图形是以（1，0）为选定的极坐标点画出的曲线。

锟斤拷锟洁辑时锟斤拷: 2023-04-10 17:18:34