我有一个由2D平面上4个点定义的4边凸多边形，想要能够在其中生成随机点。
如果将问题简化为一个平行四边形，那么问题会变得更简单，但更通用的答案更好。
生成随机点直到其位于多边形内并不可行，因为需要的时间真的很难预测。
11个回答
44
由于提问者的问题有些含糊，因此我将回答以下问题：如何在任意四边形内从均匀分布生成一个点，实际上是如何在任意（凸）多边形内从均匀分布生成一个点的概括。答案基于从三角形中生成服从均匀分布的样本（请参见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。
注意，x 有一半的概率落在三角形外面，但如果是这种情况，它将位于由三角形和以（v1，v2）中点为圆心旋转 π 后的映像形成的平行四边形内部（图中虚线所示）。在这种情况下，我们可以生成新的点 x' = v0 + R(pi)(x - v3)，其中 R(pi) 是一个π弧度（180度）的旋转。点 x' 将在三角形内部。
进一步注意，如果四边形已经是一个平行四边形，则我们不必随机选择一个三角形，我们可以确定性地选择任意一个，然后选择点 x 而无需测试它是否在其源三角形内。
- cheshirekow
5
1很棒的答案。美丽的图片。 - Thomas Ahle
1我正在尝试实现这个，我认为它应该是
x' = v0 + (v3 - x)。我完全错了吗？再仔细看一下，我不确定自己是否正确，但我的测试用例 v0 = [0,0] 将 x' 放在三角形外面。 - Gabriel Littman@gabriel_littman。我相信你是正确的。方程的图像中缺少了一个R(pi)，而文本中存在...即旋转180度。我认为旋转矩阵是[-1,0;0,-1]，也就是说我们将其操作数取反。 - cheshirekow
这是问题的实际答案！ - Gustavo Maciel
我尝试在Python中实现这个，但我认为有些东西出了问题。请参见https://gist.github.com/astromme/599de466236adc534bc6e33cf2af8e7b。对于一个三角形，其点为[0,1]，[1,0]，[1,0]，v3是[2，-1]，这似乎没有意义。此外，我得到的点在四边形之外。有什么想法吗？ - Andrew Stromme
29
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都可以由一个四元组描述，如下所示：
P = a A + b B + c C + d D
在您的情况下，您可以生成4个随机数并将它们归一化，使它们加起来等于1。这会给您一个点。请注意，在这种情况下，点的分布将不是均匀的。
C. 您还可以像其他地方提出的那样，将四边形分解为两个三角形，并使用半平行四边形方法（即作为平行四边形，但添加条件u+v=1）或三角形的重心坐标。然而，如果您想要均匀分布，一个三角形内有点的概率必须等于该三角形面积除以四边形面积的比例。
- PierreBdR
2
重心法是否适用于具有孔洞的多边形情况？ - Pranav
@Pranav 不会的...重心坐标需要连续域，我猜可能是凸的（需要检查）。 - PierreBdR
18
假设您想要一个均匀分布：从多边形中形成两个三角形。根据它们的面积比率选择要在哪个三角形内生成点。
将三角形的角落称为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的公式，除了预处理和最后一步将点折叠回三角形以处理除平行四边形外的其他形状）。
将三角形的角落称为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的公式，除了预处理和最后一步将点折叠回三角形以处理除平行四边形外的其他形状）。
- jakber
1
对于其他人寻找的话，以下是如何确定一个点是否在三角形内的方法：https://dev59.com/7XI-5IYBdhLWcg3wBjjk - Niyaz
4
您的多边形由两个三角形组成，那么为什么不随机选择其中一个三角形，然后在三角形中找到一个随机点呢？这可能不是最好的解决方案，但它可以工作。
- jonnii
1
3如果您需要随机点的均匀分布，请确保考虑到两个三角形的面积并进行适当加权。 - Robert Gamble
2
一种稍微不太“天真”的方法是使用多边形填充算法，然后随机选择填充线上的点。
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.
- SoloBold
1
1我怀疑这不是Turambar所需要的，但它可以工作。有些行比其他行长，因此为了获得均匀分布，请不要选择一行，然后选择一个像素。计算像素，然后随机选择一个，并从列表中找到其位置... - dmckee --- ex-moderator kitten
2
您所说的“一般”是指所有非平行四边形的四边形，还是所有可能的四边形？
如果你有这个图形，可以画一条连接四条边的随机线，例如：
.BBBB.
A C
A C
.DDDD.
首先在单位正方形上生成一个随机点，然后在线段B和D上标记该点在X轴上的距离百分比。使用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);
}
- chakrit
2
以下内容适用于普通的凸四边形：
您可以从有限元方法中借鉴一些概念，特别是针对四边形（4边形）元素（请参考此处的第16.5节）。基本上，有一个双线性参数化，将u-v空间中的正方形（在这种情况下，u，v \ in [-1,1]）映射到由点p_i（i = 1,2,3,4）组成的四边形。请注意，在提供的参考文献中，参数称为\eta和\xi。
基本步骤：
- 选择合适的随机数生成器来在二维正方形域内生成分布良好的点
- 在范围[-1,1]内生成随机u-v对
- 对于每个u-v对，相应的随机点在您的四边形中= 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)
唯一的问题是u-v空间中均匀分布的点不会在欧几里德意义下产生在您的四边形中均匀分布的点。如果这很重要，您可以直接在四边形的边界框内以2D方式工作，并编写一个点在四边形内（可能通过将问题分成两个点在三角形内）的测试来剔除在外部的随机点。
- Not Sure
1
这些点需要均匀分布吗？还是任何分布都可以？
这个多边形可以是凹的吗？还是保证是凸的？
如果上述两个问题的答案都是否定的，那么就选择任意两个顶点，并在它们之间的线段上选择一个随机点。这仅限于连接顶点的线段（即非常不均匀）；您可以通过选择第三个顶点，然后在该点和第一个点之间选择一个点来做得更好——仍然不均匀，但至少可以选择多边形中的任何点。
在两个点之间选择一个随机点很容易，只需使用公式 A + p(B-A)，其中A和B是两个点，p是0.0到1.0之间的随机数。
- Chris Dodd
1
你想要点的分布是什么样子的？如果你不介意，上述方法就能正常工作。如果你想要均匀分布，可以使用以下过程：将多边形分成两个三角形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）是多边形均匀分布的样本。
- Alex Coventry
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接