Genera aree di dimensioni uguali in poligono

Non risolvibile. Ho provato un certo numero di metodi fino a quando ho realizzato che non si poteva fare.

Assumi una forma con area 4, che dovrebbe essere divisa in 2 parti con area 2 ciascuna:

Il triangolo e il quadrato più a sinistra devono essere parte della forma 1, ma ha bisogno di un altro triangolo. L'unico posto che può essere preso è il quadrato a destra, ma il resto è diviso in due regioni.

Come ho detto nel mio commento alla risposta di Doc Browns (altrimenti eccellente), vi è una questione di scelta della divisione del triangolo quadrata e gt; che rende leggermente più difficile il device di un algoritmo. Inoltre, non devi renderlo in serie, ma puoi farlo in parallelo, come mostrano alcuni dei miei suggerimenti.

Ho fatto diversi approcci euristici all'inizio.

Voronoi: Scegli N punti (coordinate non intero) nella forma, crea una mappa voronei. Lascia che i punti si attraggano e si respingano l'un l'altro rispetto alla loro area (attrazione troppo grande, repellenze troppo piccole).

Utile per A / N di grandi dimensioni, facile da inserire nei massimi locali.

Metodo Circle: L'obiettivo è rimuovere le aree problematiche e quindi continuare a utilizzare un altro metodo.

Scegli un punto (non intero) all'interno e un raggio r. L'interno meno il cerchio creerà k sottoregioni sconnesse. Se una delle sottoregioni è di dimensione A / n, rimuoverla. Inoltre, se c'è 2 * A / n, dovrebbe essere facile dividerlo e rimuoverlo anche. Abbassa leggermente il raggio e continua (probabilmente usa qualche ricerca binaria).

Crescita di punti problematici: Inizia usando il metodo menzionato da Doc Brown, ma poiché ci sono due scelte al massimo bordi, salta il grafico e fai crescere ogni regione sul bordo in un modo per creare il minor numero possibile di punti problematici possibili (punti problematici = triangoli che condividono solo un bordo con il resto della forma). Per esempio. quando si scelgono nuovi vicini da includere, aggiungili in ordine di convessità (concavo = convessità negativa)

Crescita del nastro: Per aree quasi convesse o convesse. Scegliere un punto sul bordo esterno, fare in modo che un nastro di larghezza unitaria segua il bordo esterno finché non raggiunge la lunghezza giusta, assicurandosi di non creare mai un nuovo punto disconnesso. Se necessario, salta gli ultimi triangoli e fallo crescere leggermente in larghezza. Lascia che il prossimo nastro segua dove si è conclusa l'ultima fino a quando l'area finale è della giusta dimensione.

Simile al gioco o organico: Crea N "paesi". Mettili in punti casuali. Lasciali crescere organicamente. Quando si incontrano, quello con la più piccola area corrente è il più strong e vince il triangolo. Probabilmente incline ai massimi locali?

La strategia generale dovrebbe essere quella di rimuovere il primo pezzo di area A / n dal poligono P0 (dove A è l'area totale), lasciando un nuovo poligono P1 dell'area A-A / n. Quindi ripeti questo producendo un poligono P2, poi P3, e dopo n ripetizioni, hai la tua soluzione. Nota che è possibile ad ogni passo che non riesci a trovare un pezzo così nuovo in cui le parti rimanenti formino ancora un poligono connesso, nel quale devi tornare indietro di un passo e provare a trovare un altro pezzo, o interrompere l'algoritmo senza un risultato .

Per costruire questo pezzo di dimensione A / n, inizia dividendo il poligono in "pezzi di griglia". Qualsiasi quadrato di griglia all'interno del poligono forma un tale pezzo, così come qualsiasi semitono triangolare in cui il bordo del poligono divide il quadrato in due metà. Puoi utilizzare un test point-in-polygon per questo, iterare su tutti i mezzi quadrati all'interno del riquadro di delimitazione del poligono e prova se il loro punto medio si trova all'interno del poligono dato (se entrambe le metà di un quadrato sono contenute, si può usare invece il quadrato completo). Successivamente, crei un grafico planare, in cui ciascuno dei pezzi definisce un vertice (con una "area" o "peso" di 1 o 1/2). I bordi di quel grafico sono dati dai pezzi vicini. Questo riduce il tuo problema geometrico a un problema grafico, dove stai cercando un sotto-grafico collegato con vertici di peso totale A / n, e il grafico rimanente è ancora collegato.

L'ultimo problema potrebbe essere risolto con un approccio backtracking . Inizia con un vertice che può essere rimosso dal grafico senza renderlo scollegato. Puoi scegliere la vertice in modo casuale, se lo desideri, o mischiare casualmente la lista di tutti i vertici una volta, per riutilizzarla nei seguenti passaggi. Ora prova a trovare un secondo vertice che è collegato al primo, che può essere rimosso dal grafico rimanente senza distruggere anche la sua connessione. Se ci sono più possibilità, sceglierne una a caso. Per i vertici che rappresentano un quadrato, puoi anche consentire un'operazione di grafico in cui dividi il quadrato in due triangoli (questo crea nuovi vertici di peso 1/2) dall'uno o dall'altro modo possibile. Questo è solo un po 'più complicato del semplice spostamento di un vertice dal grafico originale al grafico secondario, ma non dovrebbe essere affatto difficile.

Ripeti finché il tuo sottografo non raggiunge un peso totale A / n, oppure non trovi un altro vertice. In questo caso, "backtrack" di un livello e prova prima un altro vertice.

Ci sono diversi modi per ottimizzare questo, per esempio, devi scegliere un test di connettività veloce per i grafici. Immagino che troverai molti algoritmi per questo sottotema, usa Google o inizia qui . Può valere la pena cercare un algoritmo che possa verificare rapidamente se un grafo connesso è ancora connesso quando viene rimosso un vertice.

Spero che questo aiuti.