Algoritmo di forma con ottimizzazione

Question

Ho una forma definita da segmenti di retta.

Voglio semplificare la forma da costruire con linee rette ma solo con un insieme finito di pendenze.

Desidero ridurre al minimo la quantità di segmenti utilizzati e ridurre al minimo la differenza di area dalla forma prima e dopo.

Desidero ridurre al minimo queste due cose contemporaneamente con un peso definito dall'utente che enfatizza minimizzare uno più di un altro.

minimize { J = w1(number of segments/length) + w2(difference area/length) } 

Dove w1 e w2 sono entrambi i pesi e la lunghezza è la lunghezza del nuovo segmento. Voglio un algoritmo che faccia questo. Qualche idea?

Qui di seguito mostro alcune immagini di come potrei volere che funzioni. C'è qualcosa in letteratura che potrebbe aiutare a scrivere un algoritmo. Grazie!

Answer 1

Questo sembra un problema molto difficile! Avrei avvicinarlo definendo prima due routine:

1. diffArea(fig, target) calcola l'area differenza tra fig e target
2. decomp(fig, p1, p2, s1, s2) calcola le due figure che possono essere costruiti sostituendo tutti i segmenti tra p1 e p2 con un paio di segmenti di forme s1 e s2. Ad esempio, se ci sono stati quattro segmenti tra i punti p1 e p2 in fig, quindi decomp(fig, p1, p2, s1, s2) restituisce le due cifre generate sostituendo questi quattro segmenti con le versioni in scala appropriata di s1 e s2. C'è solo un modo per ridimensionare s1 e s2 per riempire lo spazio tra p1 e p2 (perché siamo nello spazio 2-d), e le due cifre provengono da entrambi ordinandoli s1 -> s2 o s2 -> s1.

Date queste due routine, penso che una procedura di ricerca locale iterata potrebbe funzionare bene. Si avrebbe le seguenti operazioni:

1. Impostare fig in larga delimitazione forma intorno target
2. Per ogni coppia di vertici (p1, p2) a fig (a partire da coppie con 1 segmento tra, quindi 2 segmento tra ...) E per ogni coppia (s1, s2) di forme:
   • Calcola fig1 e fig2 usando decomp(fig, p1, p2, s1, s2)
   • Let e_fig essere il numero di bordi in fig e e_new per il numero di bordi in fig1 e fig2
   • Se w1 * e_new + w2 * diffArea(fig1, target) < w1 * e_fig + w2 * diffArea(fig, target), sostituire fig con fig1
   • Se w1 * e_new + w2 * diffArea(fig2, target) < w1 * e_fig + w2 * diffArea(fig, target), sostituire fig con fig2

Ripetere questa procedura fino a quando hai provato ogni coppia di vertici e hanno trovato sostituti miglioramento. Ovviamente non ti daremo una soluzione ottimale, ma scommetto che funzionerà abbastanza bene.

Answer 2

Ebbene, in questo caso Pareto efficiency sembra essere un buon peso di una soluzione. A prima vista sembra che l'utilizzo di un'ottimizzazione discreta sarebbe appropriato. La scelta di un particolare algoritmo dipende dalla complessità delle figure da modellare. Per figure grandi e complesse suggerirei di usare un algoritmo genetico.