Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Random point inside triangle inside Java

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.

like image 777
Arunas Jaspelkis Avatar asked Oct 29 '13 09:10

Arunas Jaspelkis


2 Answers

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

like image 98
Vaibhav Raj Avatar answered Oct 17 '22 08:10

Vaibhav Raj


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

like image 40
ghilesZ Avatar answered Oct 17 '22 09:10

ghilesZ