平行四边形内的随机点

Question

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

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

生成随机点直到一个点位于多边形内部是行不通的，因为它所花费的时间确实是不可预测的。

Answer 1

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

为了实现这一点，我们：

1. 对多边形进行三角测量（即生成覆盖多边形的非重叠三角形区域的集合）。 对于四边形的情况，创建一条边
   任意两个不相邻的顶点。 对于其他多边形，请参阅 http://en.wikipedia.org/wiki/Polygon_triangulation 了解起始信息点，或者http://www.cgal.org/（如果您只需要一个库）。

   

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

   

3. 然后从有限分布生成一个随机索引 i超过给定权重的指数。 对于四边形，这是伯努利分布：

   

4. 设 v0、v1、v2 为三角形（用它们的点位置表示，使得 v0 = (x0,y0) 等。然后我们生成两个随机数 a0 和 a1，都是从区间 [0,1] 均匀抽取的。然后我们计算随机点 x由 x = a0 (v1-v0) + a1 (v2-v0)

   

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

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

Answer 2

答：如果您可以将输入限制为平行四边形，那么这非常简单：

1. 取 0 到 1 之间的两个随机数。我们将调用 u 和 v。

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 都可以用 4-uple 来描述，这样：

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

在您的情况下，您可以绘制 4 个随机数并将它们归一化，以便它们加起来为 1。这将给出你一点。 请注意，在这种情况下，点的分布将不均匀。

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

Answer 3

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

将三角形的角称为 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 的公式，除了预处理和最后一步将点折叠回三角形，因此它可以处理平行四边形以外的其他形状）。

Answer 4

你的多边形是两个三角形，所以为什么不随机选择其中一个，然后在三角形中找到一个随机点。

可能不是最好的解决方案，但它会起作用。

Answer 5

一种不太“天真”的方法是使用 多边形填充算法，然后从填充线上随机选择点。

C 代码示例

//  public-domain code by Darel Rex Finley, 2007

int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;

//  Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
      *(polyX[j]-polyX[i])); }
    j=i; }

  //  Sort the nodes, via a simple “Bubble” sort.
  i=0;
  while (i<nodes-1) {
    if (nodeX[i]>nodeX[i+1]) {
      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
    else {
      i++; }}

  //  Fill the pixels between node pairs.
  //  Code modified by SoloBold 27 Oct 2008
  //  The flagPixel method below will flag a pixel as a possible choice.
  for (i=0; i<nodes; i+=2) {
    if   (nodeX[i  ]>=IMAGE_RIGHT) break;
    if   (nodeX[i+1]> IMAGE_LEFT ) {
      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;
      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
      for (j=nodeX[i]; j<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}

   // TODO pick a flagged pixel randomly and fill it, then remove it from the list.
   // Repeat until no flagged pixels remain.

Answer 6

“一般”是指一般的所有非平行四边形四边多边形还是所有可能的多边形？

画一条连接 4 条边的随机线怎么样，例如如果你有这样的：

.BBBB.
A    C
A    C
.DDDD.

然后在单位正方形上生成一个随机点，然后以 X 轴上距离的百分比标记直线 B 和 D 上的点。 使用 Y 轴的值对线 A 和 C 执行相同的操作。

然后将A线上的点连接到C线，将B线上的点连接到D线，交点作为随机点。

它并不统一，因为舍入误差会帮助某些点，但如果您使用浮点值，它应该很接近。

实现也应该相当容易，因为您已经在使用多边形了。 您应该已经拥有执行这些简单任务的代码。

这是一个快速伪代码：

void GetRandomPoint(Polygon p, ref float x, ref float y) {

    float xrand = random();
    float yrand = random();

    float h0 = p.Vertices[0] + xrand * p.Vertices[1];
    float h1 = p.Vertices[2] + yrand * p.Vertices[3];

    float v0 = p.Vertices[0] + xrand * p.Vertices[2];
    float v1 = p.Vertices[1] + yrand * p.Vertices[3];

    GetLineIntersection(h0, h1, v0, v1, x, y);

}

Answer 7

这适用于一般的凸四边形：

您可以借用有限元法中的一些概念，特别是四边形（4 边）元素（请参阅此处第 16.5 节）。 基本上，有一个双线性参数化将 uv 空间中的正方形（在本例中为 u, v \in [-1, 1]）映射到由点 p_i 组成的四边形（对于 i = 1,2,3,4 ）。 请注意，在提供的参考中，参数称为 \eta 和 \xi。

基本配方：

1. 选择合适的随机数生成器，在方形 2D 域中生成均匀分布的点
2. 生成 [-1, 1] 范围内的随机 uv
3. 对 对于每个 uv 对，四边形中相应的随机点 = 1/4 * ((1-u)(1-v) * p_1 + (1+u)(1-v) * p_2 + (1+u)(1+v) * p_3 + (1-u)(1+v) * p_4)

唯一的问题是 uv 空间中的均匀分布点不会在四边形中产生均匀分布的点（在欧几里德意义上）。 如果这很重要，您可以直接在四边形的边界框中进行二维工作，并编写一个四边形中的点（可能通过将问题分成三元组中的两个点）测试来剔除外部的随机点。

Answer 8

积分需要均匀分布吗，还是任意分布都可以？

多边形可以是凹的，还是保证是凸的？

如果以上两个问题的答案都是“否”，则选取任意两个顶点并在它们之间的线段上选取一个随机点。 这仅限于连接顶点的线段（即非常不均匀）； 你可以通过选择第三个顶点然后在该点和第一个点之间选择一个点来做得更好——仍然不均匀，但至少多边形中的任何点都是可能的

在两点之间的线上选择一个随机点是简单，只需 A + p(BA)，其中 A 和 B 是点，p 是 0.0 到 1.0 之间的随机数

Answer 9

您希望积分有什么样的分布？ 如果你不介意的话，上面的方法就可以了。 如果您想要均匀分布，则可以执行以下过程：将多边形分为两个三角形：a 和 b。 设 A(a) 和 A(b) 为它们的面积。 从 0 和 A(a)+A(b) 之间的间隔上的均匀分布中采样点 p。 如果p< A(a)，选择三角形a。 否则，选择三角形b。 选择所选三角形的顶点 v，并令 c 和 d 为对应于三角形边的向量。 从具有单位平均值的指数分布中采样两个数字 x 和 y。 那么点 (xc+yd)/(x+y) 就是多边形上均匀分布的样本。

Answer 10

MATLAB 函数 cprnd 从一般凸多面体上的均匀分布生成点。 对于您的问题，基于将四边形分解为三角形的更专业的算法更有效。

Answer 11

对于 PostGIS，这就是我正在使用的（您可能需要一个用于可能的无限循环的病房）。 您可以将算法导出到您的编程语言：

CREATE or replace FUNCTION random_point(geometry)
RETURNS geometry
AS $
DECLARE 
    env geometry;
    corner1 geometry;
    corner2 geometry;
    minx real;
    miny real;
    maxx real;
    maxy real;
    x real;
    y real;
    ret geometry;
begin

select ST_Envelope($1) into env;
select ST_PointN(ST_ExteriorRing(env),1) into corner1;
select ST_PointN(ST_ExteriorRing(env),3) into corner2;
select st_x(corner1) into minx;
select st_x(corner2) into maxx;
select st_y(corner1) into miny;
select st_y(corner2) into maxy;
loop
    select minx+random()*(maxx-minx) into x;
    select miny+random()*(maxy-miny) into y;
    select ST_SetSRID(st_point(x,y), st_srid($1)) into ret;
    if ST_Contains($1,ret) then
        return ret ;
    end if;
end loop;
end;
$
LANGUAGE plpgsql
volatile
RETURNS NULL ON NULL INPUT;