9

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.

1
  • 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, 2013 at 9:36

4 Answers 4

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

3

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. enter image description here

  • 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

1
  • Simple and effective! Great!
    – Simone Lai
    Oct 21, 2019 at 15:44
2

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.