在已知边界的图形中查找随机 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]

看起来像这样：

Square with a gab

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

问题是如何在不对图形形状进行任何硬编码的情况下获得图形内的随机坐标，因为这在开始时是未知的？有没有办法确定或估计最佳选择？我将如何实施这样的估算？

Answer 1

这里是暂定答案。您分两步对数字进行抽样。

在此之前，做好准备工作——将你的图形拆分成简单的基本对象。在你的情况下，你将它分割成矩形，通常人们会三角化并将它分割成三角形。

所以你有 N 个简单对象，每个对象的面积为 A_i，总面积为 A = Sum(A_i).

第一个采样步骤 - select 您从哪个矩形中选取点。在一些伪代码中

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);

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

矩形 selection 可以通过二进制搜索或更复杂的方式进行优化 alias method

更新

如果您的边界是通用的，那么唯一好的方法是使用任何好的库 (f.e。Triangle) 对您的多边形进行三角测量，然后 select基于面积的三角形（步骤 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);

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

Finding random x,y coordinates in a figure where you know the boundary

random

boundary

figure

coordinates