matlab 平行四边形内的随机点

Random points inside a parallelogram

提问by Andres

I have a 4 side convex Polygon defined by 4 points in 2D, and I want to be able to generate random points inside it.

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

If it really simplifies the problem, I can limit the polygon to a parallelogram, but a more general answer is preferred.

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

Generating random points until one is inside the polygon wouldn't work because it's really unpredictable the time it takes.

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

采纳答案by PierreBdR

A. If you can restrict your input to parallelogram, this is really simple:

A. 如果您可以将输入限制为平行四边形，这真的很简单：

1. Take two random numbers between 0 and 1. We'll call then uand v.

2. If your parallelogram is defined by the points ABCD such that AB, BC, CD and DA are the sides, then take your point as being:

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

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

2. 如果您的平行四边形由点 ABCD 定义，使得 AB、BC、CD 和 DA 是边，则将您的点视为：

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

Where ABis the vector from A to B and ADthe vector from A to D.

AB从 A 到 BAD的向量和从 A 到 D 的向量在哪里？

B. Now, if you cannot, you can still use the barycentric coordinates. The barycentric coordinates correspond, for a quad, to 4 coordinates (a,b,c,d)such that a+b+c+d=1. Then, any point Pwithin the quad can be described by a 4-uple such that:

B. 现在，如果你不能，你仍然可以使用重心坐标。对于四边形，重心坐标对应于 4 个坐标(a,b,c,d)，使得a+b+c+d=1。然后，P四边形内的任何点都可以用 4-uple 来描述，使得：

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

In your case, you can draw 4 random numbers and normalize them so that they add up to 1. That will give you a point. Note that the distribution of points will NOT be uniform in that case.

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

C. You can also, as proposed elsewhere, decompose the quad into two triangles and use the half-parallelogram method (i.e., as the parallelogram but you add the condition u+v=1) or the barycentric coordinates for triangles. However, if you want uniform distribution, the probability of having a point in one of the triangle must be equal to the area of the triangle divided by the area of the quad.

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

回答by cheshirekow

The question by the OP is a bit ambiguous so the question I will answer is: How to generate a point from a uniform distribution within an arbitrary quadrilateral, which is actually a generalization of How to generate a point from a uniform distribution within an arbitrary (convex) polygon. The answer is based on the case of generating a sample from a uniform distribution in a triangle (see http://mathworld.wolfram.com/TrianglePointPicking.html, which has a very nice explanation).

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

In order to accomplish this we:

为了实现这一点，我们：

1. Triangulate the polygon (i.e. generate a collection of non-overlapping triangular regions which cover the polygon). For the case of a quadrilateral, create an edge across any two non-adjacent vertices. For other polygons, see http://en.wikipedia.org/wiki/Polygon_triangulationfor a starting point, or http://www.cgal.org/if you just need a library.

   

2. To pick one of the triangles randomly, let us assign an index to each triangle (i.e. 0,1,2,...). For the quadrilateral, they will be 0,1. For each triangle we assign a weight equal as follows:

   

3. Then generate a random index i from the finite distribution over indexes given their weights. For the quadrilateral, this is a Bernoulli distribution:

   

4. Let v0, v1, v2 be vertices of the triangle (represented by their point locations, so that v0 = (x0,y0), etc. Then we generate two random numbers a0 and a1, both drawn uniformly from the interval [0,1]. Then we calculate the random point x by x = a0 (v1-v0) + a1 (v2-v0).

   

5. Note that with probability 0.5, x lies outside outside the triangle, however if it does, it lies inside the parallelogram composed of the union of the triangle with it's image after a rotation of pi around the midpoint of (v1,v2) (dashed lines in the image). In that case, we can generate a new point x' = v0 + R(pi)(x - v3), where R(pi) is a rotation by pi (180 deg). The point x' will be inside the triangle.

6. Further note that, if the quadrilateral was already a parallelogram, then we do not have to pick a triangle at random, we can pick either one deterministically, and then choose the point x without testing that it is inside it's source triangle.

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 而不测试它是否在其源三角形内。

回答by jakber

Assuming you want a uniform distribution: Form two triangles from your polygon. Pick which triangle to generate the point in according to their area ratio.

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

Call the corners of the triangle A, B, C, the side vectors AB, BC, AC and generate two random numbers in [0,1] called u and v. Let p = u * AB + v * AC.

调用三角形 A, B, C 的角，边向量 AB, BC, AC 并在 [0,1] 中生成两个随机数，称为 u 和 v。让 p = u * AB + v * AC。

If A+p is inside the triangle, return A+p

如果 A+p 在三角形内，则返回 A+p

If A+p is outside the triangle, return A + AB + AC - p

如果 A+p 在三角形之外，则返回 A + AB + AC - p

(This is basically PierreBdR's formula except for the preprocessing and the last step that folds the point back into a triangle, so it can handle other shapes than parallelograms).

（这基本上是 PierreBdR 的公式，除了预处理和将点折叠回三角形的最后一步，因此它可以处理平行四边形以外的其他形状）。

回答by jonnii

Your polygon is two triangles, so why not randomly select one of those, then find a random point in the triangle.

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

Probably not the best solution, but it'd work.

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

回答by wprl

A somewhat less "na?ve" approach would be to use a polygon fill algorithm, and then select points from the fill lines randomly.

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

C Code Sample

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.

回答by Not Sure

This works for general, convex quadrilaterals:

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

You can borrow some concepts from the Finite Element Method, specifically for quadrilateral (4-sided) elements (refer to section 16.5 here). Basically, there is a bilinear parameterization that maps a square in u-v space (for u, v \in [-1, 1] in this case) to your quadrilateral that consists of points p_i (for i = 1,2,3,4). Note that In the provided reference, the parameters are called \eta and \xi.

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

Basic recipe:

基本配方：

1. Choose a suitable random number generator to generate well-distributed points in a square 2D domain
2. Generate random u-v pairs in the range [-1, 1]
3. For each u-v pair, the corresponding random point in your 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)

1. 选择合适的随机数生成器在方形二维域中生成分布良好的点
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)

The only problem is that uniformly distributed points in the u-v space won't produce uniformly distributed points in your quad (in the Euclidean sense). If that is important, you can work directly in 2D within the bounding box of the quad and write a point-in-quad (maybe by splitting the problem into two point in tris) test to cull random points that are outside.

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

回答by chakrit

By "general" do you mean all non-parallelogram 4-side polygons in general or all possible polygons?

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

How about drawing a random line connecting the 4 sides e.g. If you have this:

如何绘制一条连接 4 个边的随机线，例如如果你有这个：

.BBBB.
A    C
A    C
.DDDD.

Then generate a random point on a unit square, then mark the point on the line B and D at the percentage of distance on the X axis. Do the same on line A and C using value from the Y axis.

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

Then connect the point on line A to line C and line B to line D, the intersection point is then used as the random point.

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

It's not uniform because rounding errors will aid certain points but it should be close if you are working with floating points values.

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

Implementation should be rather easy, too, since you are already working with polygons. You should already have code that does those simple tasks.

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

Here's a quick pseudocode:

这是一个快速的伪代码：

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);

}

回答by Tim Benham

The MATLAB function cprndgenerates points from the uniform distribution on a general convex polytope. For your question a more specialized algorithm based on decomposing the quadrilateral into triangles is more efficient.

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

回答by Chris Dodd

Do the points need to be uniformly distributed, or is any distribution ok?

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

Can the polygon be concave, or is it guarenteed to be convex?

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

If the answer to both the above is no, then pick any two of the vertexes and pick a random point on the line segment between them. This is limited to the line segements connecting the vertexes (ie, VERY non-uniform); you can do a bit better by picking a third vertex and then picking a point between that and the first point -- still non-uniform, but at least any point in the polygon is possible

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

Picking a random point on a line between two points is easy, just A + p(B-A), where A and B are the points and p is a random number between 0.0 and 1.0

在两点之间的线上随机选取一个点很容易，只需 A + p(BA)，其中 A 和 B 是点，p 是 0.0 和 1.0 之间的随机数

回答by Alex Coventry

What kind of distribution do you want the points to have? If you don't care, the above methods will work fine. If you want a uniform distribution, the following procedure will work: Divide the polygon into two triangles, a and b. Let A(a) and A(b) be their areas. Sample a point p from the uniform distribution on the interval between 0 and A(a)+A(b). If p < A(a), choose triangle a. Otherwise, choose triangle b. Choose a vertex v of the chosen triangle, and let c and d be the vectors corresponding to the sides of the triangle. Sample two numbers x and y from the exponential distribution with unit average. Then the point (xc+yd)/(x+y) is a sample from the uniform distribution on the polygon.

您希望积分有什么样的分布？如果你不在乎，上面的方法都可以。如果您想要均匀分布，可以使用以下步骤： 将多边形分成两个三角形 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) 是多边形上均匀分布的一个样本。