Algoritmo di tratteggio rettangolo ottimale

Question

Sto cercando un algoritmo per tratteggiare un rettangolo con la lunghezza della linea complessiva più breve, in modo che un oggetto di una determinata area possa passare attraverso il tratteggio.

Ad esempio, dato un rettangolo di 5x3 cm e tratteggio usando linee parallele di 1 cm di diametro, l'oggetto più grande che posso passare attraverso il tratteggio è un quadrato di 1 cm di lato. Ho usato un totale di 22 cm (ovvero 4x3 + 2x5) di linee di tratteggio. Quindi per passare un'area di 1mq ho usato 22cm di linee di tratteggio.

L'algoritmo dovrebbe trovare un modello che minimizzi le linee di tratteggio complessive dagli attuali 22 cm senza consentire il passaggio di un'area con più di 1sqcm (l'oggetto non deve necessariamente avere la forma di un quadrato o addirittura di un rettangolo, è l'area complessiva che questioni).

Modifica: seguendo l'esempio di nlucaroni ho trovato la Congettura a nido d'ape che afferma che qualsiasi divisione del piano in regioni di uguale area ha perimetro almeno quello della normale griglia esagonale, che risponde parzialmente alla mia domanda.

Answer 1

Hai bisogno di forme che formino una tassellation . Hexagon è probabilmente la soluzione migliore. Tuttavia, cosa succede se la forma che stai attraversando non si adatta esattamente al modello di tassellatura?

Osserva le tassellature e scopri se il tuo modello / schermo / tratteggio deve essere regolare o meno, deve adattarsi all'oggetto da testare, eccetera.

se in effetti lo stai costruendo da infinite linee rette che formano aree = 1, allora il meglio che puoi fare è un quadrato (vai avanti, trova il massimo dell'area rispetto al rapporto dei lati, oppure trova perimetro rispetto al rapporto dei lati prendendo la derivata).

la tua domanda è piuttosto vaga / incompleta, s, questo è tutto ciò che ho per te.

Answer 2

Problema pulito. Ho il sospetto che l'algoritmo finirà per essere davvero semplice, però - ci devono essere alcuni "ottimali" set di angoli dello schermo da utilizzare che minimizza le dimensioni di apertura per una determinata lunghezza di filo.

In realtà, questo mi ricorda un po 'il problema del taglio della torta, in cui stai cercando di trovare il numero minimo di tagli dritti per fare x fette di torta. Quindi, la soluzione potrebbe essere sulla falsariga di, per ogni filo, cercare di ridurre al massimo le dimensioni dell'oggetto più grande che può passare. Ciò significherebbe tagliare i più grandi "buchi". a metà con ogni filo aggiunto, quando possibile.

modifica: quando ho effettivamente provato il mio algoritmo proposto, ho ottenuto risultati peggiori della versione ingenua. Devi assolutamente prendere in considerazione le dimensioni minime quando posizioni i fili.

Answer 3

Cosa significa tratteggiare un rettangolo?

Puoi riformulare la tua domanda?

Inoltre, durante la riformulazione, indica ciò che l'algoritmo dovrebbe ricevere come input e cosa dovrebbe produrre come output.