如何找到四边形中的任意点？

Question

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

“在四边形中找到一个随机位置，其中该点在任何位置的概率相等。”

视觉上就像这样：

​

例如，example四边形是: A:21417.78 37105.97 B:38197.32 24009.74 C:1364.19 2455.54 D:1227.77 37378.81

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

编辑感谢您的回复。我将在周末看一看这个问题，届时将奖励被接受的答案。顺便说一句，我应该提到四边形可以是凸的也可以是凹的。Sry 'bout dat.

Answer 1

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

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

  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 2

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

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 3

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

这四条边可以表示为y = mx + b形式的线条。检查这个点是在这四条线的上方还是下方，放在一起你就可以知道它是在里面还是外面。