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

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

“要在四边形中找到一个随机位置，这个点在任何位置都有相同的可能性。”

看起来像这样：

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://sofzh.miximages.com/c%23/TrianglePointPicking_700.gif

给定一个三角形，其原点有一个顶点，其他位置为v ₁和v ₂ ，选择x http://sofzh.miximages.com/c%23/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。

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

如果你想要一个终止的gaurentee，那么你可以创建一个算法只生成四边形内的点（简单），但你必须确保点的概率分布是偶然的四边形。

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

给出了非常好的探索

Answer 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”。 我意识到这不是世界上执行速度最快的东西，但我认为它会起作用。

Answer 4

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

四个边可以表示为y = mx + bforms的线。 检查点是在四条线的上方还是下方，并将它们放在一起，你可以弄清楚它是在里面还是外面。

Answer 5

您是否可以反复尝试限制四边形的矩形内的任何位置，直到您在四边形内获得某些内容？ 这可能比某些花哨的算法更快，以确保你在四边形中选择一些东西？

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

Answer 6

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

那么写一个函数很简单：

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

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

Answer 7

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

所以：

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

Answer 8

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

如果你想在你的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) 

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

Answer 9

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

这是算法：

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

编辑

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