Trova poligono di area massima inscritto nel poligono più grande

Question

Vorrei trovare la rotazione e la posizione di un poligono che massimizzi quanto grande possa essere ridimensionato entro i limiti di adattamento all'interno di un poligono più grande.

idea attuale è quella di utilizzare scipy optimization routines per ottimizzare i parametri di posizione e rotazione per massimizzare il parametro di scala, e shapely per aggiungere un vincolo che il poligono è contenuto. Sembra che sarà lento e non particolarmente elegante.

Altre idee?

Answer 1

Questo problema sembra essere NP-difficile. Data una soluzione candidata, non si può essere certi che sia la soluzione migliore. Sembra che tu abbia bisogno di provare a utilizzare una sorta di ricerca casuale incrementale.

Answer 2

Se il poligono interno viene scalato al massimo, ci sono almeno 4 coppie "vertice interno - bordo esterno" o "vertice esterno - bordo interno" in cui il vertice si trova sul bordo.

Prendiamo tutti i 4 di coppie vertice-bordo. Per ognuno otteniamo il sistema di equazioni lineari per le coordinate di due punti di riferimento. Se ha una soluzione, verifichiamo che non ci siano intersezioni e se OK ricordiamo le coordinate e la dimensione del poligono interno.

Questa è una soluzione esatta, ma è lenta. D'altra parte, le routine di ottimizzazione di scipy probabilmente troveranno un massimo locale che non è quello globale.