java - Java内部三角形内的随机点

Question

我正在尝试在 Java 中获取三角形内的随机点。

我有 x、y 坐标的三个点并尝试使用这个公式。

P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C

其中 r1 和 r2 是从 0 到 1 的随机双精度数。但是，如何定义 A、B、C？因为现在 A 有 x 和 y 坐标。

Answer 1

P(x) = (1 - sqrt(r1)) * A(x) + (sqrt(r1) * (1 - r2)) * B(x) + (sqrt(r1) * r2) * C(x)
P(y) = (1 - sqrt(r1)) * A(y) + (sqrt(r1) * (1 - r2)) * B(y) + (sqrt(r1) * r2) * C(y)

更多信息可以在这里找到math.stackexchange和这篇论文

Answer 2

我宁愿不使用涉及平方根的公式，因此，浮点错误+计算时间。以下方法仅使用乘法和加法，这使其高效且对浮点数更友好。它也很容易实现/理解：

在 ABC 中随机均匀地 生成一个点：想法是在平行四边形 ABCD 中生成一个点，并将获得的点投影到 ABC 内。

• 在平行四边形 ABCD 内选择一个点 p（D 是向量 AB + AC 对 A 的平移）

• 两种情况：

  1. p 在 ABC 里面，保留它
  2. p在ABC外，取p'，根据[BC]的中间对称

一些额外的细节

• 检查一个点是否在三角形内：如何确定一个点是否在二维三角形内？ （实际上你只需要检查 bc 的哪一边）

• 平行四边形 ABCD 中的随机点 p：设 V1（分别为 V2）是从 A 到 B（分别是 A 到 C）的向量。点 p 由 (r1 * V1 + r2 * V2) 对 A 的平移给出，其中 r1 和 r2 是 0 和 1 之间的两个随机双精度数。

• 均匀性：平行四边形中的选择点显然是均匀选择的。此外，ABC 中的每个点都可以从 ABCD 中的两个点获得，除了位于 BC 上的点，它们的可能性小两倍，但这不会损害均匀性，因为 BC 与 ABC 相比是零区域。

• 这种方法可以很容易地推广到 n 维单纯形

Answer 3

这是实现此目标的另一种方法，该方法也在 Graphics Gems (Turk) 中介绍。

if (r1 + r2 > 1) {
    r1 = 1 - r1;
    r2 = 1 - r2;
}

a = 1 - r1 - r2;
b = r1; 
c = r2;

Q = a*A + b*B + c*C

这种方法不能扩展到更高维空间。如果是这种情况，您需要使用本质上是重心坐标的公式。

Answer 4

由于问题是针对 Java 代码而不是伪代码或数学符号，因此这是 Vaibhav 在 Java 中的解决方案：

public class Point{
    public double x;
    public double y;

    public Point(double x, double y){
        this.x = x;
        this.y = y;
    }
}

public class Triangle {
    Point A;
    Point B;
    Point C;

    public Point getRandomPoint(){
        double r1 = Math.random();
        double r2 = Math.random();

        double sqrtR1 = Math.sqrt(r1);

        double x = (1 - sqrtR1) * A.x + (sqrtR1 * (1 - r2)) * B.x + (sqrtR1 * r2) * C.x;
        double y = (1 - sqrtR1) * A.y + (sqrtR1 * (1 - r2)) * B.y + (sqrtR1 * r2) * C.y;

        return new Point(x, y);
    }
}

进一步优化是可能的，只是代码变得不那么可读了。