如何在四边形中找到一个随机点？ [英] How to find a random point in a quadrangle?

问题描述

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

在一个四边形内找到一个随机位置，这个位置在任何位置都有相同的机会。

这样看起来像：

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

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

编辑
感谢您的回复。我会在周末看看这个，然后会授予接受的答案。顺便提一下，我应该提到四边形可以是凸面或凹面。 Sry'bout dat。

解决方案

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

更新：

借用这个伟大的链接从 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] 区间中的变量，它给出
点均匀分布在
四边形中（左图）。不在三角形内部
的
点可以被丢弃，或
转换成三角形内对应的
点（右
图）。

I have to be able to set a random location for a waypoint for a flight sim. The maths challenge is straightforward:

"To find a single random location within a quadrangle, where there's an equal chance of the point being at any location."

Visually like this:

An example ABCD quadrangle is: A:[21417.78 37105.97] B:[38197.32 24009.74] C:[1364.19 2455.54] D:[1227.77 37378.81]

Thanks in advance for any help you can provide. :-)

EDIT Thanks all for your replies. I'll be taking a look at this at the weekend and will award the accepted answer then. BTW I should have mentioned that the quadrangle can be CONVEX OR CONCAVE. Sry 'bout dat.

解决方案

Split your quadrangle into two triangles and then use this excellent SO answer to quickly find a random point in one of them.

Update:

Borrowing this great link from Akusete on picking a random point in a triangle.

main figure http://mathworld.wolfram.com/images/eps-gif/TrianglePointPicking_700.gif

Given a triangle with one vertex at the origin and the others at positions v₁ and v₂, pick x http://mathworld.wolfram.com/images/equations/TrianglePointPicking/NumberedEquation2.gif where A₁ and A₂ are uniform variates in the interval [0,1] , which gives points uniformly distributed in a quadrilateral (left figure). The points not in the triangle interior can then either be discarded, or transformed into the corresponding point inside the triangle (right figure).

这篇关于如何在四边形中找到一个随机点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！