Il teorema di Pick e gli amori giovanili

Sono un marito fedele.
Ma ci sono degli amori passati che ogni tanto tornano a stimolarmi e a riempirmi la mente, facendomi rivivere le emozioni che provavo quando li frequentavo. E allora eccomi lì a centellinarne i piaceri che ancora una volta, con rinnovato vigore, mi si concedono, quasi nell'ingenuità di una cotta adolescenziale.
Uno di questi amori è la Matematica. ;-)

È grazie a Giovanna e al suo blog Matematicamedie che mi sono imbattuto in un aspetto di questa materia a me ancora sconosciuto. Non avevo mai sentito parlare prima, infatti, del teorema di Pick.
Come la prof. Giovanna spiega esaurientemente nel suo interessantissimo post, che parla di un magnifico lavoro in cui ha guidato la classe dei suoi allievi, il teorema di Pick calcola in modo semplice e conciso l'area di un poligono costruito in un modo particolare.

Per chiarire meglio la faccenda, comincio con qualche definizione.

Avendo una griglia regolare di punti (che possiamo immaginare come gli incroci delle linee di un foglio quadrettato), un "segmento di Pick" è un segmento che unisce due punti della griglia senza incontrarne alcun altro nel suo cammino. Se il segmento incontra qualche altro punto, viene considerato piuttosto come il concatenamento di due segmenti consecutivi allineati.
Un "poligono di Pick" è un concatenamento chiuso e non autointersecante di segmenti di Pick.
È proprio l'area del poligono di Pick che è valutata dal teorema di Pick.

Si noti che la condizione di non-autointersezione è necessaria per il calcolo dell'area.

figura 1

Non avrebbe infatti molto senso valutare l'area di un poligono autointersecante.
Inoltre la condizione per cui un segmento non deve contenere nessun punto della griglia oltre gli estremi, non riduce l'espressività della definizione. Se un poligono ha un lato tagliato da un punto della griglia, be', in quel punto si può considerare un vertice aggiuntivo che forma un angolo piatto. Ad esempio la figura 1 mostra un poligono di Pick costituito da quattro vertici e quattro lati, indicati da colori diversi, pur essendo perfettamente sovrapponibile ad un triangolo.
Come rivela Giovanna, il teorema di Pick afferma che l'area A di un poligono di Pick è data dalla formula

A = PI + PC/2 -1

dove PI è il numero di punti "interni" al poligono (cioè i punti della griglia regolare che cadono nella parte interna) e PC è il numero di punti "al contorno", cioè quelli che costituiscono i vertici dei segmenti di Pick lati del poligono, o, in altre parole, i punti che giacciono sul perimetro.
Evidentemente la formula è valida a meno di moltiplicare il valore ottenuto per l'area del quadretto che definisce la griglia regolare. Per semplicità su questo post si supporrà di considerare una griglia il cui quadretto ha area unitaria.
Riprendendo la figura 1, ad esempio, PI è il numero di punti colorati in azzurro (7), PC quelli in giallo (4), quindi l'area del poligono è
A = 7 + 4/2 - 1 = 8
Funziona. Provare per credere!

In un commento della discussione di seguito al blog citato, Giovanna mi suggerisce un paio di link dove c'è pure la dimostrazione "ufficiale" del teorema di Pick. Io però non ho ancora seguito quei link, ne' ho intenzione di farlo prima di aver inserito questo post, perché ciò che mi affascina della matematica non è tanto il risultato in sè, anche se in casi come questo la formula ha un'eleganza davvero attraente. Ne' tanto meno ho bisogno di una prova concreta per credere nella verità della formula: mi fido di Giovanna!
No, l'aspetto che trovo irresistibile è utilizzare la matematica per trovare una dimostrazione da me.
Questo compito è naturalmente semplificato dal fatto che so già in anticipo quale sia il risultato a cui devo giungere e, non solo, sono già anche convinto che quel risultato sia vero. Si tratta quindi soltanto di trovare la strada giusta per arrivarci (senza navigatore satellitare ;-)).

Mettendomi nei panni dell'eventuale lettore che non conoscesse il teorema di Pick, avverto qui che il seguito di questo post riporta la mia dimostrazione e quindi, se si è interessati a trovarne una potenzialmente diversa, questo è un buon momento per smettere di leggere.

Dunque...

Innanzitutto cerco il modo per contare i punti interni al poligono date le informazioni geometriche sui vertici.
Comincio con il definire un sistema di assi cartesiani centrato in un qualunque punto della griglia che stia più a sinistra e più in basso di tutto il poligono (suppongo che queste due ultime condizioni siano ininfluenti, ma, visto che posso scegliere, mi semplifico la vita!).

figura 2

Mi concentro ora nel trovare un modo semplice per esprimere il numero di punti che stanno "sotto" ad un segmento di Pick. Per "sotto" intendo che hanno ordinata maggiore o uguale a zero e inferiore al punto di intersezione della verticale con il segmento, e che inoltre abbiano ascissa compresa (estremi inclusi) tra le ascisse degli estremi del segmento. Nell'esempio riportato in figura 2 si tratta del numero di punti evidenziati in giallo.

figura 3

Per fare ciò considero la figura costituita da tutti i punti che stanno sotto al segmento più tutti quelli che ottengo ruotando la figura di 180° intorno al punto medio del segmento. Questi punti sono disposti come un rettangolo che chiamo R (un esempio è riportato in figura 3).
Il numero di punti appartenenti a questo rettangolo è chiaramente dato dal numero di punti alla base moltiplicato per il numero di punti in altezza.
Chiamando P1 e P2 gli estremi del segmento, e chiamando rispettivamente (x1, y1) e (x2, y2) le loro coordinate, il calcolo del numero di punti del rettangolo è dato da questa formula:
R = (x2 - x1 +1) * (y2 + y1 + 1)

Il numero R calcolato è un numero pari.

figura 4

Infatti, come mostra la figura 4 è possibile scomporre R in tre rettangoli, evidenziati dai colori rosso, verde e blu. Chiaramente il rettangolo rosso e quello blu sono uguali, e quindi contengono lo stesso numero di punti. La somma dei punti in questi rettangoli è dunque pari. Per dimostrare che R è un numero pari mi basta quindi mostrare che il numero di punti nel rettangolo verde è pure pari.
I numeri dx = x2 - x1 e dy = y2 - y1 sono numeri primi fra di loro. Infatti, se così non fosse, il segmento tra P1 e P2 incontrerebbe altri punti della griglia. Non sarebbe quindi un segmento di Pick, che per definizione non contiene altri punti della griglia oltre agli estremi. Poiché dx e dy sono primi tra loro, almeno uno di essi è dispari (se entrambi fossero pari avrebbero 2 come divisore comune). Di conseguenza, almeno un valore, tra dx+1 e dy+1 è pari. Ne consegue che il loro prodotto è necessariamente pari, e guarda a caso quel prodotto costituisce appunto il numero di punti del rettangolo verde. Perciò R è pari.
Il numero R è quindi divisibile per 2, e il risultato della divisione è dato dal numero di punti che stanno "sotto" al segmento più uno. Infatti per costruzione il numero dei punti appartenenti ad R che stanno sopra al segmento e quello dei punti che ne stanno sotto è uguale, ed è uguale alla metà di R meno i punti che stanno proprio sul segmento (2).

figura 5

Mi interessa ora trovare il numero di punti che stanno sotto il segmento tranne quelli dell'ultima colonna (come indicato, nella figura 5, dai punti colorati di verde). Questo numero, che chiamo Q, è evidentemente dato da
Q = (R-2)/2 - y2
poiché y2 è il numero di punti dell'ultima colonna, e cioè
Q = (x2 - x1 +1) * (y2 + y1 + 1) / 2 - 1 - y2

figura 6

È facile verificare che questa formula è valida anche se il punto P1 sta al di sopra del punto P2 o se hanno la stessa ordinata (cioè y1 = y2).
Nel caso in cui P1 stia a destra di P2 (cioè x1 > x2), la formula è ancora valida, salvo che il risultato è cambiato di segno e viene contato anche il punto estremo coinvolto. Questo risultato è mostrato dalla figura 6.
In questo caso, infatti, la base del rettangolo R è la proiezione del segmento a cui però si escludono gli estremi, invertita di segno. La formula per contarne i punti
R = (x2 - x1 +1) * (y2 + y1 + 1)
indica quindi l'inverso del numero di punti di quel rettangolo. Si noti che l'area vale 0 se x1 = x2 + 1. La prima parte della formula di Q, (x2 - x1 +1) * (y2 + y1 + 1) / 2, indica quindi il numero di punti che stanno sotto al segmento escludendo la prima e l'ultima colonna, come schematizzato dai punti colorati in verde nella figura 6.

figura 7

La seconda parte della formula Q, -1 -y2, invece, indica chiaramente la colonna a sinistra dei punti che stanno sotto il segmento, invertita di segno, contando, stavolta, anche il punto P2 stesso, come mostrato dai punti colorati in blu nella figura 6. La somma algebrica delle due parti, data dalla formula Q
Q = (x2 - x1 +1) * (y2 + y1 + 1) / 2 - 1 - y2
indica dunque il numero dei punti che stanno sotto al segmento, escludendo la colonna di destra e contando anche l'estremo di sinistra, il tutto invertito di segno.

La formula Q mi serve per calcolare, in un concatenamento di segmenti, il numero dei punti che stanno sotto a quelli che vanno da sinistra a destra, ma contemporaneamente sopra a quelli che vanno da destra a sinistra. La figura 7 mostra il concatenamento di due segmenti da sinistra a destra: al numero di punti sotto il segmento rosso si sommano i punti sotto il segmento blu.

figura 8-1 figura 8-2 figura 8-3

Nelle figure 8-1, 8-2, 8-3 viene mostrato il procedimento per sommare algebricamente i punti relativi a due segmenti consecutivi, uno verso destra e l'altro verso sinistra. In 8-1 sono mostrati in rosso i punti del segmento rosso, positivi, in 8-2 in blu i punti del segmento blu, negativi, in 8-3 la loro somma algebrica.

figura 9-1 figura 9-2 figura 9-3 figura 9-4 figura 9-5 figura 9-6

Nella sequenza delle figure da 9-1 a 9-6 si vede la procedura reiterata per i segmenti da P1-P2 a P6-P1 (chiudendo il giro).
Le figure 9-1 e 9-2 mostrano come si sommino due segmenti verso destra, la figura 9-3 mostra i punti che vengono sottratti dalla somma ottenuta al passo precedente. Sono indicati in blu i punti "negativi", cioè quelli che vengono sottratti in eccesso. Tali punti annullano alcuni di quelli positivi al passo 9-4. In 9-5 e 9-6 vengono poi sottratti i punti relativi agli ultimi due segmenti, entrambi verso sinistra.
Il valore che è stato ottenuto dall'iterazione rappresenta il numero di punti interni al poligono, salvo due punti che vengono sottratti in eccesso (gli estremi P1 e P4), e uno che viene sommato in eccesso (P3). Considerando il motivo per cui ciò avviene, si giunge alla conclusione che i punti sommati in eccesso sono quelli che appartengono ai vertici delle "concavità a sinistra" (cioè quelli che formano una concavità tra un segmento verso destra e il successivo verso sinistra), e, viceversa, i punti sottratti in eccesso sono quelli che appartengono ai vertici delle "convessità a sinistra" (cioè quelli che formano una convessità tra il segmento precedente verso sinistra e il successivo verso destra).
È facile dimostrare che, percorrendo un poligono in senso orario, il numero totale di vertici a concavità a sinistra è uguale al numero di vertici a convessità a sinistra meno uno, infatti, ad ogni "cambio di direzione", percorrendo il perimetro del poligono, deve prima o poi seguire un cambio di direzione nel verso opposto. Quindi per calcolare il numero esatto dei punti interni al poligono, se N e' il numero di convessita' a sinistra bisogna sommare N e sottrarre N-1, ovvero sommare 1.

Riprendendo la formula per Q, e generalizzandola sugli indici dei punti:
Qi = (xi+1 - xi +1) * (yi+1 + yi + 1) / 2 - 1 - yi+1
Questa vale per tutti gli n segmenti del poligono, facendo variare i sui valori 1, 2, ..., n. L'indice n+1 identifica il punto P1, in modo che l'ultimo segmento sia quello che congiunge Pn con P1.
Modifico un po' la formula, moltiplicando e raccogliendo:
Qi = (xi+1 - xi) * (yi+1 + yi) / 2 + (xi+1 - xi + yi+1 + yi + 1)/2 - 1 - yi+1
ottenendo, poi
Qi = (xi+1 - xi) * (yi+1 + yi) / 2 + (xi+1 - xi -yi+1 + yi - 1)/2
Posso spezzare in due questa formula, chiamando
Ai = (xi+1 - xi) * (yi+1 + yi) / 2
Bi = (xi+1 - xi -yi+1 + yi - 1)/2
e dunque
Qi = Ai + Bi

Il numero dei punti interni del poligono è quindi dato da
PI = (Σi = 1..nQi) +1 = [Σi = 1..n(Ai + Bi)] +1
ovvero:
PI = (Σi = 1..nAi) + (Σi = 1..nBi) +1

Detti
A = Σi = 1..nAi
B = Σi = 1..nBi
si conclude che
PI = A + B + 1

La parte B si può semplificare. Infatti
B = Σi = 1..nBi = Σi = 1..n[(xi+1 - xi -yi+1 + yi - 1)/2]
o, in altre parole
B = [(x2-x1-y2+y1-1) + (x3-x2-y3+y2-1) + ... + (xn-xn-1-yn+yn-1-1) + (x1-xn-y1+yn-1)]/2
Osservando la formula così scritta si nota che tutti i termini xi e yi si semplificano tra loro, e quel che rimane è -1 sommato n volte, dove n è il numero dei lati del poligono, che equivale evidentemente al numero dei punti che stanno sul contorno del poligono. Quindi
B = -PC/2
e, di conseguenza
PI = A - PC/2 + 1

Cerco ora di calcolare l'area del poligono di Pick.

figura 10

In modo simile a quanto fatto sopra, considero il poligono di Pick segmento per segmento. Ogni segmento, se percorso da sinsitra verso destra, dà un contributo positivo dato dall'area del trapezio formato dal segmento stesso e dalla sua proiezione sull'asse delle ascisse, come esemplificato nella figura 10. L'area del trapezio è data dalla somma delle basi (y1 + y2) per l'altezza (x2 - x1) diviso 2.
Generalizzando, dunque
Ai = (xi+1 - xi) * (yi+1 + yi) / 2

Questa formula vale anche per i segmenti percorsi da destra verso sinistra, salvo il fatto che l'area ottenuta è cambiata di segno, visto che l'altezza (xi+1 - xi) è negativa. La somma algebrica dei contributi di tutti i segmenti comunque vengano percorsi, genera l'area del poligono, come esemplificato dalla sequenza delle figure da 11-1 a 11-6.

figura 11-1 figura 11-2 figura 11-3 figura 11-4 figura 11-5 figura 11-6

Ad ogni passo della sequenza si somma algebricamente la porzione Ai relativa al segmento in questione. Nella figura 11-3 è evidenzata in blu la porzione che viene sottratta in eccesso, e che poi viene ricompensata dall'area positiva sommata al passo 11-4.
La sommatoria
Σi=1..n Ai
che quindi rappresenta l'area del poligono, è proprio uguale alla porzione A della formula ottenuta sopra
PI = A - PC/2 + 1

Elaborando la precedente si ottiene dunque

A = PI + PC/2 - 1

che rappresenta proprio il teorema di Pick.
Ai miei tempi, a questo punto, si concludeva l'esercizio, godendosi il momento di agoniata gloria, con l'acronimo

CVD