Come si può calcolare la sovrapposizione percentuale di due rettangoli?

Question

Ho scritto una funzione di disegno che disegna vari sprite sullo schermo. Questi sprite possono solo sovrapporsi fino a un certo punto. Se devono sovrapporsi, diventano troppo oscuri. Di conseguenza ho bisogno di rilevare quando questi sprites sono troppo sovrapposti. Fortunatamente, il problema è semplificato dal fatto che gli sprite possono essere trattati come rettangoli ortogonali. Mi piacerebbe sapere di quanto questi rettangoli si sovrappongano. In questo momento, ho solo la forza bruta testando ogni pixel in un rettangolo per vedere se l'altro lo contiene. Conta questi e calcola la sovrapposizione percentuale. Penso che ci sia probabilmente un approccio migliore, meno brutale. Quale algoritmo posso usare per determinare questo?

Sto usando wxwidgets.

Answer 1

I risultati dipendono da come si definisce la percentuale di sovrapposizione, per tenerlo simmetrica, vorrei codice in questo modo:

double CalculatePercentOverlap(const wxRect& rect1, const wxRect& rect2) 
{ 
    wxRect inter = rect1.Intersect(rect2); 
    if (inter.IsEmpty()) 
    return 0; 
    return (double)(inter.GetWidth()*inter.GetHeight()) * 2.0/
    (double)(rect1.GetWidth()*rect1.GetHeight() + 
      rect2.GetWidth()*rect2.GetHeight()); 
}