一尘不染

平行四边形内的随机点

algorithm

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

如果确实简化了问题,我可以将多边形限制为平行四边形,但是更通用的答案是首选。

生成随机点直到多边形中的某个点不起作用,因为这确实花费了很多时间。


阅读 287

收藏
2020-07-28

共1个答案

一尘不染

答:如果可以将输入限制为平行四边形,这确实很简单:

  1. 取两个介于0和1之间的随机数。我们将其称为uv
  2. 如果您的平行四边形由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可以用四边形描述四边形内的任何点,使得:

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

在您的情况下,您可以绘制4个随机数并将其规格化,以使它们的总和为1。这将为您提供一个分数。请注意,在这种情况下,点的分布将不均匀。

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

2020-07-28