Cercasi algoritmo che divida una forma 2D concava in serie di rettagoli

[alexca82]

Ciao a tutti.
OK...già il titolo è un casino, ma non sapevo come sintetizzare in poche parole la cosa.
Per un progettino in Matlab, devo appunto suddividere un "semplice" spazio bidimensionale caratterizzato da un susseguirsi di stanze rettangolari in rettangoli semplici.
Mi spiego. Io parto da questo:

Lo spazio viene definito come una matrice di n righe e 2 colonne: le righe sono i punti ordinati in senso antiorario, le colonne sono le coordinate di tali punti. L'algoritmo che devo scrivere dovrebbe riconoscere le concavità dell'immagine e produrre un output del genere, con i rettangoli elementari separati.


A me comunque non interessa che mi venga prodotto il disegno.

Ciò che chiedo è dunque: dato che non vorrei mai scoprire l'acqua calda, qualcuno è a conoscenza di un algoritmo (Matlab, C, Java,...) che faccia questo?

Grazie
Ciao

[wisher]

io provereri a fare scorerere la matrice, non appena tra tre punti mi si crea un angolo retto mi fermo e mi segno il vertice.
una volta fatto tutto ciò, prendo il primo vertice, cerco i punti con la stessa ascissa e ordinata e il vertice opposto
p.s.
ci potrebbero essere infiniti raffinamenti(mi sa che molte cose potrebbero mandare in crisi l'algoritmo così come è), però prendilo come un inizio