平行四边形内的随机点

问题描述

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

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.

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

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.

推荐答案

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

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

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

2. 如果你的平行四边形是由点 ABCD 定义的，这样 AB、BC、CD 和 DA 是边，那么把你的点当作是:

1. Take two random numbers between 0 and 1. We'll call then u and 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)

其中AB是从A到B的向量，AD是从A到D的向量.

Where AB is the vector from A to B and AD the vector from A to D.

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

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 P within the quad can be described by a 4-uple such that:

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

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

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.

C.您也可以按照其他地方的建议，将四边形分解为两个三角形并使用半平行四边形方法(即，作为平行四边形，但您添加条件 u+v=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.

这篇关于平行四边形内的随机点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！