Partizione casualmente un rettangolo in n rettangoli più piccoli

Question

Sto cercando un algoritmo in grado di suddividere un rettangolo in n rettangoli più piccoli, a caso. N sarà piccolo (nell'ordine di 5-10 nella maggior parte dei casi). Non deve essere uniformemente in modo uniforme, ma per lo meno, vorrei evitare algoritmi che escludono completamente le classi di partizioni interessanti.

Un algoritmo che mi sono imbattuto alcune volte (incluso un domanda in matematica sul numero di modi per fare n partizioni) è di dividere casualmente il rettangolo in due disegnando una linea orizzontale o verticale su di esso, quindi fare la stessa cosa in modo ricorsivo ai rettangoli più piccoli risultanti fino a ottenere ciò che desideri .

Il trucco qui è che anche se puoi ottenere diverse partizioni usando questo schema:

Ci sono alcuni modi per dividere un rettangolo in rettangoli più piccoli che questo metodo non produrrà mai:

Puoi facilmente vedere che il partizionamento di divisione e conquista non genererà mai quanto sopra, perché non esiste una linea che potrebbe essere il primo taglio, poiché nessuna linea retta singola divide l'intero quadrato in due rettangoli più piccoli.

Quindi fondamentalmente sto cercando un algoritmo per dividere casualmente un rettangolo in n rettangoli più piccoli, in cui i risultati soddisfano i seguenti criteri:

• Partizionato in esattamente n rettangoli più piccoli
• Tutto deve effettivamente essere un rettangolo (senza forme L, ecc.
• Nessun spazio vuoto rimasto

L'algoritmo nel suo insieme dovrebbe soddisfare i seguenti criteri:

• Non vi è alcuna parizione valida che l'algoritmo non sia in grado di produrre
• Può essere distorto verso determinati tipi di configurazioni, sebbene meno pregiudizi è meglio.
• Preferibilmente funziona con gli indici interi.
• Non opera generando tutte le partizioni possibili e quindi sceglierne una a caso.

Non mi interessa molto della complessità asintotica, perché lavorerò con piccoli numeri.