algorithm - 平行四边形内的随机点

Question

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

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

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

score 44 · Accepted Answer

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

In order to accomplish this we:

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_triangulation for a starting point, or http://www.cgal.org/ if you just need a library.
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:
Then generate a random index i from the finite distribution over indexes given their weights. For the quadrilateral, this is a Bernoulli distribution:
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).
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.
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.

score 29 · Accepted Answer

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

取两个介于 0 和 1 之间的随机数。我们将调用 thenu和v。
如果你的平行四边形由 ABCD 点定义，AB、BC、CD 和 DA 是边，那么你的点是：
```
 p = A + (u * AB) + (v * AD)
```

哪里AB是从 A 到 BAD的向量和从 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）或三角形的重心坐标。但是，如果您想要均匀分布，则在其中一个三角形中有一个点的概率必须等于三角形的面积除以四边形的面积。

score 18 · Accepted Answer

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.

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

If A+p is outside the triangle, return 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).

score 4 · Accepted Answer

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

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

score 2 · Accepted Answer

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

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.

score 2 · Accepted Answer

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:

.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.

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.

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

}

score 2 · Accepted Answer

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.

Basic recipe:

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

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.

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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.

score 1 · Accepted Answer

The MATLAB function cprnd generates 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.

score 0 · Accepted Answer

For PostGIS, this is what I am using (you might want a ward for possible infinite loops). You might export the algorithm to your programming language:

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;

algorithm - 平行四边形内的随机点

11 回答 11

C 代码示例

Related

Reference