10

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

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

视觉上是这样的：

替代文字

ABCD四边形的一个例子是：A:[21417.78 37105.97] B:[38197.32 24009.74] C:[1364.19 2455.54] D:[1227.77 37378.81]

提前感谢您提供的任何帮助。:-)

编辑感谢大家的回复。我会在周末看看这个，然后奖励接受的答案。顺便说一句，我应该提到四边形可以是凸的或凹的。Sry 'bout dat。

4

9 回答 9

9

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

更新：

从Akusete借用这个很棒的链接，在三角形中选择一个随机点。

主要人物
（来自 MathWorld - Wolfram 网络资源：wolfram.com）

给定一个三角形，其中一个顶点位于原点，其他顶点位于v 1 和v 2位置，选择 （来自 MathWorld - A Wolfram Web 资源：wolfram.com） 其中A 1 和A 2 是区间[0,1 ]，它给出了均匀分布在四边形中的点（左图）。然后可以丢弃不在三角形内部的点，或者将其转换为三角形内部的对应点（右图）。X

于 2010-06-17T01:03:42.323 回答
4

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

其他海报提到的第一个是找到包围矩形的最小边界框，然后在该框中生成点，直到找到位于矩形内的点。

  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。

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

如果您想要终止的 garentee，那么您可以创建一个算法以仅在四边形内生成点（简单），但您必须确保点的概率分布即使在四边形中也是如此。

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

给出了很好的解释

于 2010-06-17T01:09:03.887 回答
3

“蛮力”方法只是循环，直到你有一个有效的坐标。在伪代码中：

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”。我意识到这不是世界上执行速度最快的事情，但我认为它会奏效。

于 2010-06-17T00:43:56.037 回答
2

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

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

于 2010-06-17T01:02:50.673 回答
1

你是否允许在四边形边界的矩形内重复尝试任何地方，直到你在四边形内得到一些东西？这甚至可能比一些花哨的算法更快，以确保您在四边形中选择一些东西？

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

于 2010-06-17T00:47:45.017 回答
1

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

所以：

  1. 找到包含多边形所有点的框。
  2. 在先前找到的框的边界内创建一个随机点。使用随机函数生成 x 和 y 值。
  3. 检查该点是否在多边形内（参见此处或此处如何）
  4. 如果该点在多边形停靠点内，则完成，如果不是，请转到步骤 2
于 2010-06-17T01:06:44.180 回答
1

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

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

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

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

于 2010-06-17T01:07:46.863 回答
0

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

这是算法：

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

编辑

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

于 2010-06-17T00:45:52.387 回答
0

因此，这取决于您希望如何分配。

如果您希望在 2d 视图空间中随机采样点，那么 Jacob 的答案非常棒。如果您希望这些点有点像透视图（在您的示例图像中，右上角的密度高于左下角的密度），那么您可以使用双线性插值。

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

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

主要区别在于您是否希望您的分布在二维空间（雅各布方法）中是均匀的，还是在参数空间中是均匀的。

于 2010-06-17T05:29:59.390 回答