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.

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)

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

Answer 2

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