平行四边形内的随机点 [英] Random points inside a parallelogram

问题描述

我有一个由4D点在2D中定义的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，这样:

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.

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