John D. Cook mostra alcuni metodi per generare punti casuali all’interno di un triangolo ABC dato. Possiamo immaginare di lavorare in coordinate cartesiane, per semplicità, e quindi avere A, B e C come coppie ordinate di valori.
Il metodo più semplice è quello di usare coordinate baricentriche: generate tre numeri casuali α, β e γ tra 0 e 1, normalizzateli per far sì che la loro somma sia 1, e date come risposta αA + βB + γC. Il metodo genera punti che stanno tutti all’interno del triangolo: ma non sono uniformi, come si vede dalla figura qui sotto presa dal blog di Cook. I punti centrali del triangolo sono più probabili di quelli vicino ai vertici.
Il secondo metodo è quello del rejection sampling. Costruite il rettangolo circoscritto al triangolo, generate due numeri casuali per la coordinata x e quella y, e controllate se il punto corrispondente sta all’interno del triangolo: se sì, bene, altrimenti lo buttate via. È evidente che in questo modo i punti generati e accettati sono distribuiti in modo casuale, perché tutti quelli nel rettangolo lo sono: il costo computazionale è di due insiemi di operazioni per numero scelto.
C’è poi un terzo metodo, quello del parallelogramma. Costruite un parallelogramma aggiungendo al triangolo una sua versione speculare, e generate punti a caso al suo interno, con la formula P = A + r₁·(B-A) + r₂·(C-A) dove r₁ e r₂ sono numeri casuali in [0,1]. Ora, se il punto generato si trova nel triangolo di partenza, e quindi r₁ + r₂ ≤ 1, bene; altrimenti prendete la sua immagine riflessa nel triangolo di partenza, usando (1-r₁, 1-r₂). Di nuovo, la casualità è assicurata. Il tutto è raccontato anche su Stack Overflow.
Quale conviene tra il secondo e il terzo metodo? Dipende. Se siete fanatici e sapete dove cercare – oppure siete molto intelligenti e l’avete trovato da soli – il parallelogramma è la scelta migliore. Ma se avete fretta di implementare una soluzione e dovete generare poche centinaia di punti il rejection sampling va più che bene: il costo è il doppio dell’altro metodo, e quindi sopportabile.
Due ultime note: nei commenti al post di Cook si fa notare come scegliere una distribuzione esponenziale anziché lineare dei numeri casuali fa funzionare anche il metodo delle coordinate baricentriche. Ma soprattutto ho provato a fare la domanda a Claude. Riporta i tre metodi (immagino perché addestrato su Stack Overflow) ma afferma che quello delle coordinate baricentiche è il metodo più elegante ed efficiente. Mai fidarsi degli LLM!
[Disclaimer: Ho ricevuto il libro grazie al programma Early Reviewer di LibraryThing] Certo, l’ambientazione è fantascientifica. Però il libro è fondamentalmente un hardboiled, il che non è poi così strano visto che French è stato un supervisore di scene del crimine. Da questo punto di vista il libro è una certezza: uno sa perfettamente come si dipanerà la storia, e quindi può concentrarsi sui particolari. In effetti il testo scorre piacevolmente, soprattutto nelle parti in cui il TrovaVerità terrestre e l’assistente alieno da lui nominato cominciano a trovare un loro modus operandi. Il libro probabilmente non vincerà il Pulitzer, ma è una lettura amena.
