如何在四边形中找到随机点？

Question

我必须能够为飞行模拟的航路点设置随机位置。数学挑战很简单：

“在四边形内找到一个随机位置，其中该点位于任何位置的机会均等。”

视觉效果如下：

ABCD 四边形示例如下： 答：[21417.78 37105.97] 乙：[38197.32 24009.74] C：[1364.19 2455.54] D：[1227.77 37378.81]

预先感谢您提供的任何帮助。 ：-）

编辑 感谢大家的回复。我将在周末查看此问题，然后授予已接受的答案。顺便说一句，我应该提到四边形可以是凸的或凹的。抱歉。

Answer 1

您是否可以重复尝试包围四边形的矩形内的任何位置，直到在四边形内得到某些东西？这可能比某些奇特的算法更快，以确保您在四边形中选择某些内容吗？

顺便说一句，在该问题陈述中，我认为“查找”一词的使用令人困惑。您无法真正找到满足条件的随机值；随机发生器只是将其提供给您。您要做的就是在随机发生器上设置参数，以便为您提供符合特定条件的值。

Answer 2

我会将您的四边形分成多个图形，其中每个图形都是一个正多边形，其一侧（或两侧）平行于其中一个轴。例如，对于上图，我首先找到适合四边形内的最大矩形，该矩形必须平行于 X/Y 轴。然后在剩余的区域中，我将安装三角形，这样的三角形将与矩形的每条边相邻。

那么写一个函数就很简单了：

1）随机得到一个数字。
2）在图中随机找到一个点。

如果#1中选择的图形是一个矩形，那么在其中找到一个随机点应该很容易。棘手的部分是编写一个可以在三角形内找到随机点的例程

Answer 3

您可以在边界框中随机创建点，只有在找到位于多边形内部的点后才停止。

所以：

1. 找到包含多边形所有点的框。
2. 在先前找到的框的边界内创建一个随机点。使用随机函数生成 x 和 y 值。
3. 检查该点是否在多边形内部（参见此处 或此处）
4. 如果该点位于多边形内部停止，你就完成了，如果没有，请转到步骤 2

Answer 4

因此，这取决于您想要如何分配。

如果您希望在二维视图空间中随机采样点，那么雅各布的答案很好。如果您希望这些点有点像透视图（在示例图像中，右上角比左下角密度更大），那么您可以使用双线性插值。

双线性插值非常简单。生成 [0..1] 范围内的两个随机数 s 和 t。那么，如果您的输入点是 p0,p1,p2,p3，则双线性插值是：

bilerp(s,t) = t*(s*p3+(1-s)*p2) + (1-t)*(s*p1+(1-s)*p0)

主要区别在于您希望分布在 2d 空间中均匀（雅各布方法）还是在参数空间中均匀。

Answer 5

这是一个有趣的问题，可能也有非常有趣的答案，但如果您只是想让它起作用，让我为您提供一些简单的东西。

算法如下：

1. 在包围四边形的矩形内选择一个随机点。
2. 如果它不在四边形（或任何形状）内，请重复。
3. 利润！

编辑

根据 Bart K. 的建议，我更新了第一步以提及边界框。

Answer 6

将您的四边形分成两个三角形，然后使用这个优秀的答案来快速找到其中一个随机点。

更新：

从 链接 /3058150/how-to-find-a-random-point-in-a-quadrangle/3058274#3058274">Akusete 在三角形中选取随机点。

_{（来自 MathWorld - Wolfram 网络资源：wolfram.com ）}

给定一个三角形，其一个顶点位于
原点和其他位置 v₁
和v₂，选择

_{（来自 MathWorld - Wolfram 网络资源：wolfram.com )}
其中A₁
和 A₂ 是统一的
在区间 [0,1] 中变化，给出
点均匀分布在
四边形（左图）。这
不在三角形内部的点
然后可以被丢弃，或者
转化为对应的
三角形内的点（右
图）。

Answer 7

我相信有两种合适的方法可以解决这个问题。

其他发帖者首先提到的是找到包围矩形的最小边界框，然后在该框中生成点，直到找到位于矩形内部的点。

  Find Bounding box (x,y,width, height)
  Pick Random Point x1,y1 with ranges [x to x+width] and [y to y+height]
  while (x1 or y1 is no inside the quadrangle){
       Select new x1,y1
  }

假设您的四边形面积为 Q，边界框为 A，则您需要生成 N 对点的概率为 1-(Q/A)^N，以指数方式接近 0。

我会推荐上述方法，特别是在二维方面。生成点和测试非常快。

如果您想要终止的保证，那么您可以创建一个算法来仅生成四边形内的点（简单），但您必须确保点的概率分布均匀在四边形之外。

http://mathworld.wolfram.com/TrianglePointPicking.html

给出了很好的解释

Answer 8

“蛮力”方法只是循环遍历，直到获得有效的坐标。在伪代码中：

left   = min(pa.x, pb.x, pc.x, pd.x)
right  = max(pa.x, pb.x, pc.x, pd.x)
bottom = min(pa.y, pb.y, pc.y, pd.y)
top    = max(pa.y, pb.y, pc.y, pd.y)
do {
    x = left   + fmod(rand, right-left)
    y = bottom + fmod(rand, top-bottom)
} while (!isin(x, y, pa, pb, pc, pd));

您可以使用从网络中提取的股票函数作为“isin”。我意识到这不是世界上执行速度最快的东西，但我认为它会起作用。

Answer 9

所以，这次我们要解决的是如何确定一个点是否在四边形内：

四个边可以用 y = mx + b 形式的线表示。检查该点是在四条线的上方还是下方，综合起来就可以判断它是在里面还是在外面。