Random point inside triangle inside Java

Question

I'm trying to get random point inside triangle in Java.

I have three points with x, y coordinates and trying to use this formula.

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

Where r1 and r2 are random double from 0 to 1. But, how to define A, B, C? Because now A have x and y coordinates.

Anyway make **A**,**B**,**C** points, then write some method like multiplePoint(double x, Point y); which multiplies points **y** coordinates by double **x** — Tafari, Oct 29 '13 at 09:36

score 16 · Accepted Answer · edited Apr 13 '17 at 12:19

16

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)

More information can be found here math.stackexchange and this papaer

edited Apr 13 '17 at 12:19

Community

1
1

answered Oct 29 '13 at 09:35

Vaibhav Raj

2,214
4
23
39

ghilesZ · Answer 2 · 2021-05-06T10:38:12.857

I would rather not use a formula wich involves square roots and thus, floating point errors + computation time. The following approach only uses multiplication and addition, wich makes it efficient, and more float-friendly. It is also quite easy to implement/understand :

Generating randomly uniformly a point in ABC : The idea is to generate a point in a parallelogram ABCD, and project the obtained point inside ABC.

pick a point p inside the parallelogram ABCD (D is the translation of A by vector AB + AC)
two cases :
1. p is inside ABC, keep it
2. p is outside ABC, pick p', its symetrical according to the middle of [BC]

Few additional details

Checking if a point is inside a triangle : How to determine if a point is in a 2D triangle? (in fact you only need to check on wich side of bc it is)
Random point p in parallelogram ABCD : let V1 (resp. V2) the vector from A to B (resp A to C). Point p is given by the translation of A by (r1 * V1 + r2 * V2) where r1 and r2 are two random double between 0 and 1.
Uniformity : The choosen point in the parallelogram is obviously uniformly choosen. Moreover every point in ABC can be obtained from two points in ABCD, except for the points lying on BC, which are twice less likely, however this does not harm unifromity as BC is of null area comparing to ABC.
This approach can easily be generalized to n-dimensional simplices

Simple and effective! Great! – Simone Lai Oct 21 '19 at 15:44 — Simone Lai, Oct 21 '19 at 15:44

score 2 · Answer 3 · answered Feb 12 '14 at 08:13

Here's another method to achieve this goal which is also introduced in 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

This method cannot be extended to a higher dimensional space. If that is the case, you need to use your formula which is essentially Barycentric coordinates.

score 0 · Answer 4 · answered May 14 '20 at 18:28

Since the question was for Java code and not pseudo code or mathematical notation, here's Vaibhav's solution in 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);
    }
}

Further optimization is possible, the code just becomes less readable.

Random point inside triangle inside Java

4 Answers4

Linked