Approssimare funzioni seno e coseno

In un precedente articolo (si veda [7]) si è cercato di fare luce su una delle funzioni più famose e discusse nell'ambito della programmazione di videogiochi. Sarebbe interessante vedere se esistono implementazioni, altrettanto veloci, per approssimare le funzioni seno e coseno dato che queste sono le funzioni che in assoluto, insieme alla radice quadrata, vengono usate più spesso. Un esempio di implementazione efficiente è quello della libreria DirectXMath di Microsoft che fornisce supporto ad applicazioni DirectX:

inline void XMScalarSinCos(float* pSin, float* pCos, float  Value)
{
 assert(pSin);
 assert(pCos);
 
 // Map Value to y in [-pi,pi], x = 2*pi*quotient + remainder.
 float quotient = XM_1DIV2PI * Value;
 
 if (Value >= 0.0f)
 {
  quotient = static_cast<float>(static_cast<int>(quotient + 0.5f));
 }
 else
 {
  quotient = static_cast<float>(static_cast<int>(quotient - 0.5f));
 }
 
 float y = Value - XM_2PI * quotient;
 
 
 // Map y to [-pi/2,pi/2] with sin(y) = sin(Value).
 float sign;
 
 if (y > XM_PIDIV2)
 {
  y = XM_PI - y;
  sign = -1.0f;
 }
 else if (y < -XM_PIDIV2)
 {
  y = -XM_PI - y;
  sign = -1.0f;
 }
 else
 {
  sign = +1.0f;
 }
 
 float y2 = y * y;
 
 // 11-degree minimax approximation
 *pSin = (((((-2.3889859e-08f * y2 + 2.7525562e-06f) * 
    y2 - 0.00019840874f) * y2 + 0.0083333310f) * 
    y2 - 0.16666667f) * y2 + 1.0f) * y;
 
 // 10-degree minimax approximation 
 float p = ((((-2.6051615e-07f * y2 + 2.4760495e-05f) * 
    y2 - 0.0013888378f) * y2 + 0.041666638f) * y2 - 0.5f) * y2 + 1.0f;

 *pCos = sign * p;
}

Pathfinding: A*

Problema: Dato un grafo $G = (V, E)$ (di $|V|$ vertici ed $|E|$ archi) pesato (con pesi non negativi) ed orientato e dati due dei suoi vertici $v$ e $t$ ($v$ detto vertice sorgente e $t$ destinazione o target), trovare ilcammino minimo che parte da $v$ ed arriva a $t$.

Soluzione: Algoritmo A*
Complessità: Dipende dall'implementazione della coda di minima priorità (si veda [4]). In questo caso, per non complicare inutilmente il codice, si aggira completamente il problema usando semplicemente un array che porta ad un tempo totale $O(V^2)$

Il problema è praticamente lo stesso di quello che si risolve con l'algoritmo di Dijkstra (si veda [2]) solo che qui si cerca un cammino preciso invece che tutti i cammini minimi dalla sorgente.
Di fatto basterebbe una piccola modifica al codice dell'algoritmo di Dijkstra (3 righe al massimo) per ottenere la soluzione al problema del cammino minimo da sorgente a destinazione. Nella figura sotto, a sinistra, si vede che l'algoritmo di Dijkstra impiega 5 iterazioni per raggiungere il vertice $6$ a partite da $1$.

Grafi: Algoritmo di Dijkstra

Problema: Dato un grafo $G = (V, E)$ (di $|V|$ vertici e $|E|$ archi) pesato (con pesi non negativi) ed orientato e dato uno dei suoi vertici $v$ (detto vertice sorgente), trovare tutti cammini minimi che partono da $v$ ed arrivano ad ognuno dei vertici raggiungibili da $v$.

Soluzione: Algoritmo di Dijkstra
Complessità: Dipende dall'implementazione della coda di minima priorità (si veda [4]). In questo caso, per non complicare inutilmente il codice, si aggira completamente il problema usando semplicemente un array che porta ad un tempo totale $O(V^2)$

Grafi: Ricerca in Profondità (Depth-First Search)

Problema: Dato un grafo $G = (V, E)$ (con $|V|$ vertici ed $|E|$ archi) pesato, aciclico ed orientato, ordinare topologicamente tutti i vertici di $G$.

Soluzione: Ricerca in Profondità (Depth-First Search)
Complessità: $\Theta(V + E)$


Si prenda come esempio il grafo nell'immagine sotto a sinistra, con la sua rappresentazione in memoria illustrata sulla destra (si veda [2] per ulteriori info sulla rappresentazione dei grafi).

Grafi: Ricerca in Ampiezza (Breadth-First Search)

Problema: Dato un grafo $G = (V, E)$ (con $|V|$ vertici ed $|E|$ archi) non pesato e non orientato e dato uno dei suoi vertici $v$ (detto vertice sorgente), trovare tutti cammini minimi che partono da $v$ ed arrivano ad ognuno dei vertici raggiungibili da $v$.

Soluzione: Ricerca in Ampiezza (Breadth-First Search)
Complessità: $O(V + E)$


Si prenda come esempio il grafo nell'immagine sotto a sinistra, con la sua rappresentazione in memoria illustrata sulla destra (si veda [2] per ulteriori info sulla rappresentazione dei grafi).

Radice quadrata inversa veloce

Oltre che per la sua indiscussa utilità, il calcolo del reciproco della radice quadrata è diventata famosa anche per aver innescato per anni accesi dibattiti in rete sulla paternità, sulle origini e sul funzionamento di una sua particolare implementazione (si veda [1] per una breve ricostruzione storica). L'implementazione del metodo in questione è utilizzata prevalentemente in ambiti (come quello grafico) dove non è richiesta una accuratezza elevata ma solo una buona approssimazione. La particolarità che l'ha resa nota, però, è stata quella di essere tanto efficiente quanto criptica.

1  float FastInvSqrt(float x)
2  {
3     float xhalf = 0.5f*x;          // xhalf = x/2
4     int i = *(int*)&x;             // converte x nella sua rappresentazione intera
5     i = 0x5f3759df - (i >> 1);     // prima approssimazione di 1/sqrt(x) (nella sua rappresentazione intera)
6     x = *(float*)&i;               // ritorna alla rappresentazione floating-point
7     x = x * (1.5f - xhalf * x*x);  // singolo passo di Newton-Raphson per ottenere una approssim. di 1/sqrt(x) migliore
8     return x;                      // ritorna tale valore
9  }

Coordinate baricentriche definite da un triangolo in 2D e 3D

Dati tre punti non collineari $A, B$ e $C$ nel piano, le coordinate di un punto $P$ qualsiasi nello stesso piano possono essere calcolate attraverso la combinazione lineare dei due vettori ($B - A$) e ($C - A$)

\begin{equation}\label{eq:1}P - A = v(B - A) + w(C - A)\end{equation}\begin{equation}\label{eq:2}P = A + v(B - A) + w(C - A) = (1 - v - w)A + vB + wC = uA + vB + wC\end{equation}
Con $u = 1 - v - w$ (e quindi $u + v + w = 1$). Se, oltre a ciò, si aggiunge anche il vincolo $0\le v, w \le 1$, allora $P$ risiede all'interno di $\triangle ABC$.

Verificare posizione di un punto rispetto a circumcerchio e circumsfera

L'idea alla base dell'algoritmo per il calcolo della triangolazione di Delaunay (vista in [1]) può essere sfruttata per verificare (in 2D) se un punto $D$ è interno, esterno o appartiene al cerchio circoscritto al triangolo individuato da tre punti $A$, $B$ e $C$.

Triangolazione di Delaunay in 2D

Problema: Dato un insieme $\mathbf{P}$ di $n$ punti nel piano, trovare la triangolazione di Delaunay $\mathbf{D}(\mathbf{P})$ di $\mathbf{P}$. Trovare cioè quella triangolazione tale che nessun punto di $\mathbf{P}$ sia interno al cerchio circoscritto di ogni triangolo di $\mathbf{D}(\mathbf{P})$.

Soluzione: Convex Hull in 3D
Complessità: $O(n^2)$

Convex Hull in 3D

Problema: Dato un insieme di $n$ punti nello spazio, trovare il più piccolo involucro convesso che contiene gli $n$ punti. Trovare cioè i punti, tra gli $n$ dell'insieme dato, che si trovano sui bordi del più piccolo poliedro convesso che contiene tutti gli altri.

Soluzione: Incrementale
Complessità: $O(n^2)$

Convex Hull in 2D

Problema: Dato un insieme di $n$ punti nel piano, trovare il più piccolo involucro (o inviluppo) convesso che contiene gli $n$ punti. Trovare cioè i punti, tra gli $n$ dell'insieme dato, che si trovano sui lati del più piccolo poligono convesso che contiene tutti gli altri.

Soluzione: Graham Scan
Complessità: $O(n\log n)$

Collinearità e Complanarità in 3D

Collinearità di tre punti in 3D

Verificare se tre punti $A, B, C$ in 3D giacciono sulla stessa retta a livello teorico è del tutto equivalente a quanto accade in 2D (si veda [1]). Si tratta cioè di calcolare l'area del parallelogramma individuato dai due vettori $\,\, \mathbf{n_1} = B - A \,\,$ e $\,\, \mathbf{n_2} = C - A \,$. Se l'area è nulla i tre punti sono collineari.

Collinearità di tre punti in 2D

Verificare se tre punti $A, B, C$ nel piano giacciono sulla stessa retta risulta abbastanza semplice se si riduce il problema al calcolo dell'area del parallelogramma individuato dai due vettori $\quad \mathbf{n_1} = B - A \,\,$ e $\,\, \mathbf{n_2} = C - A$.
Se l'area è nulla, infatti, i tre punti sono collineari.

Triangolare un poligono con ear clipping

Problema: Dato un poligono $P$ descritto da $n$ punti nel piano trovare una triangolazione di $P$ in modo che le diagonali del poligono siano segmenti non intersecanti ed interni al poligono e che ogni regione interna sia un triangolo.

Soluzione: Ear clipping
Complessità: $O(n^2)$

Per triangolare un poligono la soluzione più semplice, ma anche più costosa, è quella di prendere tutti i segmenti che uniscono due vertici del poligono (ci sono $O(n^2)$ possibili candidati) e, per ogni segmento, controllare che sia interno al poligono e che non ci siano intersezioni con i lati del poligono (costo $O(n)$). Queste operazioni hanno quindi costo $O(n^3)$ e devono essere ripetute sino a quando non si trovano tutte le diagonali (che sono $n-3$). Il costo totale dunque arriva a $O(n^4)$. L'algoritmo è molto semplice ma con un piccolo sforzo in più si può ridurre il costo computazionale a $O(n^2)$ (in realtà si potrebbe arrivare fino a $O(n)$ ma il livello di complessità inizierebbe a farsi piuttosto elevato; per metodi più "semplici" con costo $O(n\log n)$ si vedano invece [2] e [3]).

Verificare l'intersezione di due segmenti in 2D

Verificare se due segmenti nel piano si intersecano risulta relativamente semplice se si considera che, preso uno qualsiasi dei due segmenti (ad esempio il segmento $AB$ della figura sotto), un vertice dell'altro segmento ($CD$) si troverà a sinistra del primo segmento ($D$ in questo caso) e l'altro a destra ($C$).

Area di un poligono

Per calcolare l'area di un poligono la soluzione più logica e semplice sarebbe quella di triangolare il poligono e sommare le aree dei triangoli che compongono il poligono.

Questa soluzione risulta abbastanza intuitiva per poligoni convessi, meno per quelli concavi. Utilizzando però il giusto metodo si può sfruttare questa stessa soluzione a prescindere dal tipo di poligono.
Il classico calcolo dell'area di un triangolo $A=(b \times h)/2$, però, si rivela insufficiente in questo caso. Invece, dall'algebra lineare sappiamo che dati tre vertici $a, b, c$, sia il modulo del prodotto vettoriale ($(b - a)\times (c - a)$) che il determinante della matrice composta dalle coordinate (omogenee) dei tre vertici

Problema dello zaino 0-1

Problema: Dato un insieme di $n$ elementi $A=\{a_0\dots a_n\}$, i cui valori e pesi sono rispettivamente $v=[v_0\dots v_n]$ e $w=[w_0\dots w_n]$, trovare $V[n, W]$, il valore totale maggiore che si può ottenere scegliendo tra gli $n$ elementi di $A$ e che possono essere contenuti in uno zaino che sopporta un peso massimo pari a $W$.

Soluzione: Programmazione dinamica
Complessità: $O(Wn)$

Una soluzione efficiente per risolvere il problema è quella che sfrutta la programmazione dinamica attraverso la formula

$V[i, 0]:= 0 \quad\text{ for $1 \le i \le n$.}$

$V[0, j]:= 0 \quad\text{ for $1\le j \le W$.}$

$V[i, j]:= \begin{cases}V[i-1, j], & \text{if $wi[i] > j$.} \\ MAX(V[i-1, j], V[i-1, j - wi[i]] + v[i]) , & \text{if $wi[i] \le j$.} \end{cases}$

Distanza di edit

Tra le tante definizioni di distanza di edit (o Edit distance) quella fornita da Vladimir Levenshtein (denominata anche Levenshtein distance) è tra le più semplici nonché tra le più usate per via della sua utilità a livello pratico.
Questa particolare definizione di distanza di edit usa solo tre operazioni: copia, inserimento ed eliminazione (quattro se si include l'operazione "nessuna operazione", che non ha costo) attraverso le quali si calcola il costo necessario per trasformare una sequenza di caratteri in un altra. Tanto più piccolo è il costo tanto maggiore è la somiglianza delle due sequenze. Al contrario, tanto maggiore è il costo tanto minore è la somiglianza delle sequenze.

Ad esempio, per trasformare la sequenza di caratteri Mantello in Minerva è necessario un certo numero di copie, inserimenti o eliminazione che, sommate tutte insieme danno il costo necessario per la trasformazione (si faccia riferimento all'immagine sotto). Per semplificare le cose il costo sarà uguale per tutte le operazioni ma, volendo generalizzare, può avere un valore diverso che dipende dall'operazione e dall'architettura sulla quale viene eseguito l'algoritmo.

Ordinamento: Heap Sort

Problema: Data una sequanza di $n$ numeri $A= [a_0,\, \dots\,, a_{n-1}]$, ordinarla in modo crescente.
Soluzione: Ricorsiva (Heap sort)
Complessità: $O(n \log n)$

L'idea alla base di Heap sort (o Heapsort) è quella di rappresentare una sequenza di $n$ numeri come fosse un albero binario con $n$ nodi con la proprietà che il valore di un nodo genitore è sempre $\ge$ al valore dei suoi due nodi figli.
Data, ad esempio, la sequenza nell'immagine sotto

Cifrario di Hill

Come è noto dall'algebra lineare, dato un vettore $\mathbf{v}$ di $n$ componenti e una matrice $\mathbf{A}$ di dimesione $n\times n$, si può ottenere un nuovo vettore $\mathbf{b}$ (sempre di $n$ componenti) attraverso la moltiplicazione (trasformazione)
\begin{equation}\label{eq:1}\mathbf{Av} = \mathbf{b}\end{equation}
Se $\mathbf{A}$ è invertibile, per ottenere nuovamente $\mathbf{v}$, bisogna calcolare l'inversa di $\mathbf{A}$ e moltiplicare $\mathbf{b}$ per questa matrice
\begin{equation}\label{eq:2}\mathbf{A^{-1}b} = \mathbf{v}\end{equation}
Se le componenti di $\mathbf{v}$ rappresentassero caratteri alfanumerici si potrebbe sfruttare questo fatto per implementare un cifrario relativamente robusto (almeno in ambiti casalinghi) in maniera abbastanza semplice.