Algorithme de hachurage rectangle optimal

Question

Je recherche un algorithme pour hachurer un rectangle dont la longueur totale est la plus courte possible, de sorte qu'un objet d'une surface donnée puisse être passé entre les hachures.

Par exemple, avec un rectangle de 5x3 cm et des hachures parallèles de 1 cm, le plus gros objet que je puisse passer à travers la trappe est un carré de 1 cm de côté. J'ai utilisé 22 cm (4x3 + 2x5) de hachures. Donc, pour passer une zone de 1 m², j'ai utilisé 22 cm de hachures.

L’algorithme devrait trouver un motif qui minimise les lignes de hachure globales de 22 cm actuelles tout en ne permettant pas le passage d’une zone supérieure à 1 cm² (l’objet n’a pas besoin d’être sous la forme d’un carré ou même d’un rectangle, questions).

Modifier: Suivant l'exemple de nlucaroni, j'ai trouvé le Conjecture de la colonie de nid d'abeilles qui indique que toute partition du plan en régions de même surface a au moins le périmètre de la grille hexagonale régulière, ce qui répond partiellement à ma question.

Answer 1

Vous avez besoin de formes qui constituent une tessellation . Hexagone est probablement votre meilleur pari. Mais que se passe-t-il si la forme que vous traversez ne correspond pas exactement au motif de tessellation?

Examinez les mosaïques et déterminez si votre modèle / écran / hachure doit être régulier ou non, s’adapter à l’objet testé, etc.

si en fait vous construisez cela à partir de lignes droites infinies qui forment des zones = 1, le mieux que vous puissiez faire est un carré (allez-y, recherchez le maximum de la surface en ce qui concerne le rapport des côtés, ou trouvez périmètre par rapport au rapport des côtés en prenant le dérivé).

votre question est assez vague / incomplète, s, c’est tout ce que j’ai pour vous.

Answer 2

Problème intéressant. Je soupçonne que l’algorithme finira par être vraiment simple, cependant - il doit exister des paramètres "optimaux". ensemble d'angles d'écran à utiliser minimisant la taille de l'ouverture pour une longueur de fil donnée.

En fait, cela me rappelle un peu le problème de la coupe du gâteau, où vous essayez de trouver le nombre minimal de coupes droites pour faire x tranches de gâteau. Ainsi, la solution peut être le suivant: pour chaque fil, essayez de réduire le plus possible la taille du plus gros objet pouvant passer. Cela signifierait couper les plus grands "trous". en deux avec chaque fil ajouté, lorsque cela est possible.

edit: Lorsque j’ai réellement essayé l’algorithme proposé, j’ai eu des résultats pires que la version naïve. Vous devez absolument tenir compte de la taille minimale lors du placement des fils.

Answer 3

Que signifie hachurer un rectangle?

Pouvez-vous reformuler votre question?

De même, lors de la reformulation, indiquez ce que l'algorithme doit recevoir en entrée et ce qu'il doit produire en sortie.