Area di figure sovrapposte

[boiler]

Ciao a tutti

La domanda è: come determinare l'area comune a due figure. Ovvero l'area della regione in cui si sovrappongono.

Immaginiamo di avere un cerchio nell'origine delle coordinate.
E abbiamo anche un quadrato il cui centro è sull'asse X ad una certa distanza d dall'origine.
Se questa distanza è sufficientemente grande, la sovrapposizione è nulla:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

In questo caso (banale) invece, il quadrato ha lato 2, il cerchio è di raggio unitario e d = -1.
È subito ovvio che l'area sovrapposta è

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Ma come determinare l'area sovrapposta in condizioni meno "favorevoli", come per esempio qui:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Non mi interessa una formula universale bella e pronta
Mi interesserebbe piú che altro sapere come affrontereste un problema del genere.

A me (ma sono molto arrugginito su questo tipo di cose) viene in mente solo Monte Carlo come strada percorribile.

Boiler

[xyz]

Sul momento mi vengono in mente i seguenti metodi:

ꞏ geometrico calcolo l'area con operazioni algebriche sulle aree elementari
ꞏ integrale se possibile in forma chiusa o numerica calcolo l'area di un integrale doppio definito
ꞏ elementi finiti suddivido in elementi finiti le figure e calcolo il numero di elementi sovrapposti
ꞏ statistico metodo montecarlo
ꞏ intelligenza artificiale rete neuronale opportunamente addestrata

[Ianero]

Ciao Boiler, io sarei curioso di sapere da dove viene il problema. È solo una tua curiosità?

[Piercarlo]

Mi inserisco con un'altra domanda: esiste un testo di algoritmi grafici che tratti casi come il determinare se una figura su un foglio è storta e poi calcolare di quanto; o anche (questa simile a quanto chiesto da boiler) se esiste intersezione tra due aree e di quanto; o anche di che tipo di figura si tratta (cerchio, quadrato, ellisse, rettangolo ecc.). Riassumendo la domanda, mi servirebbe un libro di algoritmi che "vedono" un'mmagine in modo da passare i parametri risultanti a un programma successivo che avvii l'esecuzione di varie procedure (raddrizzare una figura, isolare una intersezione ecc.). Grazie fin da ora.

[PietroBaima]

In generale ragionerei sul fatto che l'area sovrapposta sia quella di un rettangolo più l'area di una sezione circolare delimitata da una corda.
L'area del rettangolo non presenta particolari problemi, ma solo tre casi, che si riducono a due.
L'area della corda la risolverei come ho fatto per trovare l'altezza dell'acqua nella cisterna.

[PietroBaima]

Riassumendo la domanda, mi servirebbe un libro di algoritmi che "vedono" un'mmagine in modo da passare i parametri risultanti a un programma successivo che avvii l'esecuzione di varie procedure (raddrizzare una figura, isolare una intersezione ecc.). Grazie fin da ora.

Problema del tutto non banale. Esistono varie tecniche di computer graphics adatte allo scopo, ma richiedono della matematica molto pesante.
Vedo se trovo qualcosa quando arrivo in ufficio.

[Piercarlo]

Immaginavo.... Volevo vedere se era possibile implementare qualcosa come macro ("azioni") di photoshop per velocizzare alcune acquisizioni di immagini allo scanner... O almeno capire i vari procedimenti con cui si ha a che fare.

[PietroBaima]

Ah, capisco cosa vorresti fare, allora.
Hem... se vuoi sapere onestamente cosa penso... lascia perdere, ti vai ad infilare in un ginepraio.
Scusami se mi permetto, ma so che non sei "veneziano" e non ti offendi

[Piercarlo]

Tranquillo! So già che il problema è tosto ma speravo che per altri lo fosse (forse) un po' meno. Pazienza, continuerò con il mio solito processore "bío"

[luxinterior]

Probabilmente mi verrà tolto ogni diritto di scrittura sul forum...
Io farei così:
Immagino di disegnare in un'area di memoria le figure (come se dovessi visualizzale sul display) Se sono figure geometriche note le disegno facilmente altrimenti per una figura arbitraria dovrei avere un bitmap.
Supponiamo di utilizzare un byte per pixel (ma posso usare un bit una word cambia solo il calcolo non la procedura)
Azzero tutti i bytes dell'area di memoria, traccio la prima figura mettendo a 0xFF i byte occupati dalla figura.
Taccio la seconda figura con l'avvertenza di scrivere bytes a 0x80 quando incontro un byte 0xFF cioè già occupato dalla prima figura. Alla fine conto i bytes a 0x80 della zona di memoria, è un rudimentale integrale, e ho ricavato l'area della zona sovrapposta.