平行四边形内的随机点
我有一个由4个点在2D中定义的4边凸多边形，我希望能够在里面生成随机点。
如果真的能够简化问题，我可以将多边形限制为平行四边形，但更一般的答案是首选。
生成随机点，直到一个在多边形内部将不起作用，因为它真的是不可预测的时间。
答：如果你可以限制你的input到平行四边形，这很简单：
- 取两个0到1之间的随机数。然后我们会打电话给
u和v。 -
如果你的平行四边形是由ABCD定义的，AB，BC，CD和DA是边，那么你的观点是：
p = A + (u * AB) + (v * AD)
AB是从A到B的vector， AD是从A到D的vector。
B.现在，如果你不能，你仍然可以使用重心坐标。 对于四边形，重心坐标对应于4个坐标(a,b,c,d) ，使得a+b+c+d=1 。 那么，四边形内的任何点P都可以用四元来描述：
P = a A + b B + c C + d D
在你的情况下，你可以绘制4个随机数，并将它们归一化，使它们加起来为1。这会给你一个点。 请注意，在这种情况下点的分布将不统一。
C.也可以像其他地方提出的那样，将四边形分解为两个三angular形，并使用半平行四边形方法（即作为平行四边形，但是添加条件u+v=1 ）或三angular形的重心坐标。 但是，如果要求均匀分布，则在三angular形中有一个点的概率必须等于三angular形的面积除以四边形的面积。
由OP提出的问题有点模棱两可，所以我会回答的问题是： 如何从一个任意四边形内的均匀分布生成一个点 ，这实际上是一个泛化如何从一个统一的分布点生成一个点凸）多边形 。 答案是基于从三angular形中均匀分布生成样本的情况（请参阅http://mathworld.wolfram.com/TrianglePointPicking.html ，这有一个非常好的解释）。
为了完成这个我们：
-
三angular形多边形（即生成覆盖多边形的非重叠三angular形区域的集合）。 对于四边形的情况，在任意两个不相邻的顶点之间创build一条边。 对于其他多边形，请参阅http://en.wikipedia.org/wiki/Polygon_triangulation作为起点，或者如果您只需要一个库，请访问http://www.cgal.org/ 。
-
要随机select一个三angular形，让我们为每个三angular形分配一个索引（即0,1,2，…）。 对于四边形，它们将是0,1。 对于每个三angular形，我们赋予相等的权重如下：
-
然后从给定权重的索引上的有限分布生成随机索引i。 对于四边形，这是一个伯努利分布：
-
令v0，v1，v2为三angular形的顶点（用它们的点位置表示，使得v0 =（x0，y0）等等）。然后我们产生两个随机数a0和a1，均从[0,1 ]，然后我们用x = a0（v1-v0）+ a1（v2-v0）来计算随机点x。
-
请注意，以0.5的概率，x位于三angular形之外，但是如果它位于平行四边形的内部，该平行四边形就是围绕（v1，v2）的中点旋转π后的三angular形与其图像的并集（虚线在图像中）。 在这种情况下，我们可以生成一个新的点x'= v0 + R（pi）（x – v3），其中R（pi）是pi（180度）的旋转。 点x'将在三angular形内。
-
还要注意的是，如果四边形已经是一个平行四边形，那么我们不必随意选取一个三angular形，我们可以select一个确定性的，然后select点x而不testing它是否在源三angular形内。
假设你想要一个均匀的分布：从你的多边形中形成两个三angular形。 根据它们的面积比select要生成点的三angular形。
调用三angular形A，B，C的边angular，侧向vectorAB，BC，AC，并在[0,1]中生成两个随机数u和v。令p = u * AB + v * AC。
如果A + p在三angular形内，则返回A + p
如果A + p在三angular形之外，则返回A + AB + AC – p
（这基本上是PierreBdR的公式，除了预处理以及将点折回到三angular形的最后一步，所以它可以处理除平行四边形以外的其他形状）。
你的多边形是两个三angular形，为什么不随机select其中的一个，然后在三angular形中find一个随机点。
可能不是最好的解决scheme，但它会工作。
一个不太“ 幼稚 ”的方法是使用多边形填充algorithm ，然后从填充线中随机select点。
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.
“一般”是指所有非平行四边形的多边形，或者是所有可能的多边形？
如何绘制连接四边的随机线如果你有这样的：
.BBBB. AC AC .DDDD.
然后在单位正方形上生成一个随机点，然后在X轴上的距离百分比上标记线B和D上的点。 A行和C行使用Y轴的值。
然后将线A上的点连接到线C，将线B连接到线D，然后将交点用作随机点。
这是不统一的，因为舍入错误将有助于某些点，但如果您正在使用浮点值，它应该是closures的。
由于您已经在使用多边形，所以实现应该也相当简单。 您应该已经拥有完成这些简单任务的代码。
这是一个快速的伪代码：
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，v in [-1,1]），该四边形由点p_i组成（对于i = 1,2,3,4 ）。 请注意，在提供的参考中，参数被称为\ eta和\ xi。
基本配方：
- select一个合适的随机数生成器，在一个正方形的二维域中生成分布良好的点
- 在范围[-1,1]中生成随机uv对
- （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空间中的均匀分布的点将不会在四边形中产生均匀分布的点（在欧几里德意义上）。 如果这一点很重要，可以在四边形的边界框内以二维方式直接进行处理，然后写入一个四分之一点（也可以通过将问题分解为三点中的两点）来testing外部的随机点。
点数是否需要均匀分配，还是分配好？
多边形可以凹入，还是保证凸出？
如果上述两个答案都是否定的，则选取任意两个顶点并在它们之间的线段上选取一个随机点。 这仅限于连接顶点的线段（即，非常不均匀）; 你可以通过选取第三个顶点，然后在第一个点和第一个点之间选取一个点来做更好的一点 – 仍然是非均匀的，但至less可以在多边形中的任意点
在两点之间的线上select一个随机点很容易，只需要A + p（BA），其中A和B是点，p是0.0到1.0之间的随机数
你想得到什么样的分布？ 如果你不在乎，上面的方法将正常工作。 如果你想要一个统一的分布，下面的过程将起作用：将多边形分成两个三angular形a和b。 让A（a）和A（b）是他们的区域。 在0和A（a）+ A（b）之间的间隔内从均匀分布中采样点p。 如果p <A（a），select三angular形a。 否则，select三angular形b。 select所选三angular形的顶点v，并设c和d为三angular形边对应的向量。 从单位平均的指数分布中抽样两个数字x和y。 然后点（xc + yd）/（x + y）是来自多边形上均匀分布的样本。
MATLAB函数cprnd通过一般凸多面体的均匀分布生成点。 对于您的问题，基于将四边形分解为三angular形的更专门的algorithm效率更高。
对于PostGIS，这是我正在使用的（你可能想要一个可能无限循环的病房）。 您可能会将algorithm导出到您的编程语言中：
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;
