平行四边形内的随机点

我有一个4边凸多边形由2D中的4个点定义,我希望能够在其中生成随机点.

如果它真的简化了问题,我可以将多边形限制为平行四边形,但更常见的答案是首选.

生成随机点直到其中一个在多边形内部将不起作用,因为它所花费的时间实际上是不可预测的.

OP的问题有点模棱两可,所以我要回答的问题是:如何从任意四边形内的均匀分布生成一个点,这实际上是如何从任意内的均匀分布生成一个点的概括(凸)多边形.答案是基于从三角形中的均匀分布生成样本的情况(参见http://mathworld.wolfram.com/TrianglePointPicking.html,其中有一个非常好的解释).

为了实现这个目标,我们:

对多边形进行三角测量(即生成覆盖多边形的非重叠三角形区域的集合).对于四边形的情况,在任意两个不相邻的顶点上创建边.对于其他多边形,请参阅http://en.wikipedia.org/wiki/Polygon_triangulation作为起点,如果您只需要一个库,请参见http://www.cgal.org/.



要随机选择一个三角形,让我们为每个三角形分配一个索引(即0,1,2,...).对于四边形,它们将是0,1.对于每个三角形,我们指定一个等于如下的权重:



然后根据给定权重的索引从有限分布中生成随机索引i.对于四边形,这是伯努利分布:



设v0,v1,v2为三角形的顶点(由它们的点位置表示,使得v0 =(x0,y0)等.然后我们生成两个随机数a0和a1,两者均从区间[0,1]中均匀绘制然后我们通过x = a0(v1-v0)+ a1(v2-v0)计算随机点x.



注意,在概率为0.5的情况下,x位于三角形外部,但是如果确实如此,则它位于由三角形与其图像的并集组成的平行四边形内部,在围绕(v1,v2)的中点旋转pi之后(虚线)在图像中).在那种情况下,我们可以生成新的点x'= v0 + R(pi)(x-v3),其中R(pi)是pi(180度)的旋转.点x'将在三角形内.

进一步注意,如果四边形已经是平行四边形,那么我们不必随机选择一个三角形,我们可以确定性地选择一个,然后选择点x而不测试它是否在它的源三角形内.

A.如果您可以将输入限制为平行四边形,这非常简单:

以0和1.我们将调用然后与两个随机数u和v.

如果您的平行四边形由ABCD点定义,使得AB,BC,CD和DA是边,那么请将您的观点视为:

 p = A + (u * AB) + (v * AD)

AB从A到B AD的向量和从A到D的向量在哪里

B.现在,如果你不能,你仍然可以使用重心坐标.重心坐标对应,对于一个四,至4的坐标(a,b,c,d),使得a+b+c+d=1.然后,P四边形内的任何点都可以用4-uple来描述,这样:

P = a A + b B + c C + d D

在你的情况下,你可以绘制4个随机数并对它们进行标准化,使它们加起来为1.这将给你一个观点.请注意,在这种情况下,点的分布将不一致.

C.您也可以像其他地方一样,将四边形分解为两个三角形,并使用半平行四边形方法(即平行四边形但添加条件u+v=1)或三角形的重心坐标.但是,如果要均匀分布,则在三角形中的一个点中具有点的概率必须等于三角形的面积除以四边形的面积.

假设您想要均匀分布:从多边形中形成两个三角形.根据面积比选择生成点的三角形.

调用三角形A,B,C的角,侧向量AB,BC,AC,并在[0,1]中生成两个随机数,称为u和v.令p = u*AB + v*AC.

如果A + p在三角形内,则返回A + p

如果A + p在三角形之外,则返回A + AB + AC - p

(这基本上是PierreBdR的公式,除了预处理和将点折回三角形的最后一步,因此它可以处理除平行四边形以外的其他形状).