平行四边形内的随机点

StackOverflow https://stackoverflow.com/questions/240778

题

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

如果它确实简化了问题，我可以将多边形限制为平行四边形，但更喜欢更常见的答案。

生成随机点直到其中一个在多边形内部将无法工作，因为它实际上无法预测所需的时间。

有帮助吗？

解决方案

一个。如果您可以将输入限制为平行四边形，这非常简单：

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

  2. 如果您的平行四边形由ABCD点定义，使AB，BC，CD和DA成为边，那么请将您的观点视为：

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

    3. 其中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.这将给你一个观点。请注意，在这种情况下，点的分布将不一致。

    ℃。您也可以像其他地方一样，将四边形分解为两个三角形，并使用半平行四边形方法（即，作为平行四边形但添加条件u+v=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 = a0（v1-v0）+ a1（v2-v0）计算随机点x。

  5. 请注意，概率为0.5，x位于三角形外部，但如果确实存在，则位于三角形的并集内部的平行四边形内部，并且在围绕中点旋转pi后将其与图像进行对比（v1 ，v2）（图中的虚线）。在那种情况下，我们可以生成新的点x'= v0 + R（pi）（x-v3），其中R（pi）是pi（180度）的旋转。点x'将在三角形内。

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

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

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

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

可能不是最好的解决方案，但它确实有效。

少一点<！> na <！>＃239; ve < ！/一> <> QUOT;方法是使用多边形填充算法，然后从填充线中随机选择点。

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.

通过<！> quot; general <！> quot;是指一般的所有非平行四边形4边多边形还是所有可能的多边形？

如何绘制连接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);

}

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

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

基本食谱：

  1. 选择合适的随机数生成器以在方形2D域中生成分布均匀的点
  2. 生成[-1,1]
    3. 范围内的随机u-v对
  3. 对于每个uv对，quad中相应的随机点= 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）

    4. 唯一的问题是u-v空间中均匀分布的点不会在四边形中产生均匀分布的点（在欧几里德意义上）。如果这很重要，你可以在四边形的边界框内直接在2D中工作并写入四边形（可能通过将问题分成三点中的两个点）测试来剔除外部的随机点。

这些点是否需要均匀分布，还是任何分布都可以？

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

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

在两点之间的线上拾取随机点很容易，只有A + p（B-A），其中A和B是点，p是0.0到1.0之间的随机数

您希望这些积分具有什么样的分布？如果您不在乎，上述方法将正常工作。如果您想要均匀分布，则以下过程将起作用：将多边形划分为两个三角形a和b。设A（a）和A（b）为他们的区域。在0和A（a）+ A（b）之间的间隔上从均匀分布中采样点p。如果p <！> lt; A（a），选择三角形a。否则，选择三角形b。选择所选三角形的顶点v，让c和d为与三角形边相对应的矢量。从指数分布中采样两个数字x和y，单位平均值。然后点（xc + yd）/（x + y）是多边形上均匀分布的样本。

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

对于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;
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top