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.
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
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 :
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With