Introdução
Neste vídeo eu mostrarei dois algoritmos para gerar pontos aleatórios em um triângulo.
Problema
Dado um triângulo com pontos A, B e C, onde esses pontos são um par (x,y), crie uma função que retorne um ponto aleatório no triângulo.
Apresentarei dois métodos, descritos abaixo.
Método 1
Primeiro defina duas variáves s e t, onde cada uma contém um número aleatório entre [0,1]. Em JavaScript o Math.random() retorna um número aleatório entre [0,1] e pode ser usada. A função random() (sem parâmetros) do P5 também pode ser usada.
As expressões abaixo calculam um ponto Q no triângulo com vértices A, B e C.
O t nas equações acima servem para determinar uma linha aleatória dentro do triângulo e o s serve para determinar um ponto aleatório dentro desta linha. A raiz quadrada serve para espalhar a probabilidade dentro do triângulo, para evitar que os pontos fiquem concentrados próximos dos vértices.
A explicação e prova matemática dessas equações fogem do escopo deste documento.
Abaixo está o código em JavaScript que retorna o ponto aleatório.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function method1() {
let t = random();
let s = random();
let a = 1 - sqrt(t);
let b = (1-s) * sqrt(t);
let c = s * sqrt(t);
/* Calculate the Point Q*/
let qx = a*x1 + b*x2 + c*x3;
let qy = a*y1 + b*y2 + c*y3;
/* Return the Q point */
return [qx,qy];
}
Método 2
Esse segundo método seque o esquema do método anterior. Temos duas variáves s e t, onde cada uma contém um número aleatório entre [0,1].
O pseudo-código abaixo descreve o algoritmo.
1
2
3
4
5
6
7
8
9
10
if s+t > 1 then
s = 1-s
t = 1-t
endif
a = 1-s-t
b=s
c=t
Q = aA + bB + cC
O if no código acima serve para que o ponto gerado fique no triângulo, pois caso contrário ficará no paralelogramo gerado por dois triângulos juntos.
Este algoritmo é muito melhor que o anterior pois não precisa da raiz quadrada, que é uma operação custosa.
O código abaixo mostra o código em JavaScript.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function method2() {
let t = random();
let s = random();
if (s+t > 1) {
s = 1-s;
t = 1-t;
}
a = 1-s-t;
b = s;
c = t;
/* Calculate the Point Q*/
let qx = a*x1 + b*x2 + c*x3;
let qy = a*y1 + b*y2 + c*y3;
/* Return the Q point */
return [qx,qy];
}