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

Question

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

"要在四边形中找到一个随机位置,这个点在任何位置都有相同的可能性."

看起来像这样:

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

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

编辑感谢您的回复.我将在周末看看这个,然后将奖励接受的答案.顺便说一下,我应该提到四边形可以是CONVEX OR CONCAVE.Sry'bout dat.

Answer 1

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

更新:

借用Akusete的这个伟大链接,在三角形中选择一个随机点.

主要人物http://mathworld.wolfram.com/images/eps-gif/TrianglePointPicking_700.gif

给定一个三角形,其原点有一个顶点,其他位置为v ₁ 和v ₂,选择 x http://mathworld.wolfram.com/images/equations/TrianglePointPicking/NumberedEquation2.gif其中A ₁ 和A ₂ 是均匀的变量在区间[0,1]中,它给出了均匀分布在四边形中的点(左图).然后可以丢弃不在三角形内部的点,或者将其转换为三角形内的对应点(右图).

Answer 2

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

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

  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

给出了很好的解释