在已知边界的图形中查找随机的x，y坐标

Question

目标是在形状未知的图形中找到坐标。已知的是该图形边界的坐标列表，例如：

boundary = [(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(3,3),(2,3),(2,2),(1,2),(1,3),(0,3),(0,2),(0,1]

看起来像这样：

带山墙的正方形

这是一个非常基本的例子，我想用非常大的不同种类的数字列表来做。

问题是如何在不硬编码图形形状的情况下获得图形内的随机坐标，因为这在一开始是未知的？有没有办法确定，或者做出估计是最好的选择？我该如何实现这样的估算？

Answer 1

以下是初步答案。您分两步对数字进行采样。

之前，先做准备工作——把你的身材分成简单的基本物体。在你的例子中，你把它分成矩形，通常人们会把它分成三角形。

因此，简单对象的数量为N，每个对象的面积为A_i，总面积A=Sum(A_i(。

第一个采样步骤-选择从哪个矩形中拾取点。在某些伪码中

r = randomU01(); // random value in [0...1) range
for(i in N) {
r = r - A_i/A;
if (r <= 0) {
k = i;
break;
}
}

所以你选取了一个索引为k的矩形，然后在这个矩形中均匀地采样点

x = A_k.dim.x * randomU01();
y = A_k.dim.y * randomU01();
return (x + A_k.lower_left_corner.x, y + A_k.lower_left_corner.y);

就是这样。非常类似于三角形图形的技术。

矩形选择可以通过二进制搜索或更复杂的别名方法进行优化

更新

如果你的边界是通用的，那么唯一好的方法就是使用任何好的库(例如三角形(对你的多边形进行三角测量，然后根据面积选择其中一个三角形(步骤1(，然后使用两个随机的U01数字r1和r2对三角形中的点进行均匀采样，

P = (1 - sqrt(r1)) * A + (sqrt(r1)*(1 - r2)) * B + (r2*sqrt(r1)) * C

即在伪码中

r1 = randomU01();
s1 = sqrt(r1);
r2 = randomU01();
x = (1.0-s1)*A.x + s1*(1.0-r2)*B.x + r2*s1*C.x;
y = (1.0-s1)*A.y + s1*(1.0-r2)*B.y + r2*s1*C.y;
return (x,y);