Comment un travail d'algorithme couvrait-il une zone arbitraire avec des cercles de rayon égal?
Le rayon du cercle et la taille et la forme de la zone sont administrés arbitrairement. La zone doit être couverte avec peu de cercles que possible. Les cercles peuvent se chevaucher.
Y a-t-il un algorithme qui va gérer cela?
3 Réponses :
Sans en savoir plus sur vos contraintes, je suggérerais de prendre une couverture régulière de l'avion, avec des disques correspondant aux hexagones réguliers d'un carrelage hexagonal. Ensuite, gardez tous les disques intersectant la forme.
J'espère avoir compris votre question à droite ...
On peut prouver que l'emballage de fermeture hexagonale (HCP) de sphères couvre le volume maximum, à l'aide de sphères. Par conséquent, je suppose que faire du HCP avec des cercles couvrira également la zone maximale à l'aide de cercles. Tessellez votre zone avec des triangles et placez un cercle avec le centre à chaque sommet du triangle, avec le rayon la moitié de la longueur du côté du triangle. Voir Ce pour une image de l'algorithme dont je parle.
Remarque: Ceci est similaire au Fermer l'emballage d'atomes dans une cellule unitaire .
Comme vous le savez probablement, il n'y a que 3 tessellations d'espace 2D avec des polygones réguliers - en utilisant des carrés, des triangles ou des hexagones. La stratégie consiste à tesseller à l'aide d'un de ces polygones, puis de circonscrire un cercle à chaque polygone. Un hexagone perdrait la zone minimale en utilisant cette méthode.
Par conséquent, du rayon du cercle donné, calculez la taille des hexagones nécessaires, tessellez la zone à l'aide des hexagones, puis circonscrivez un cercle sur chaque hexagone.
- flaviu cipcigan
Cette technique ne fonctionne pas, car elle ne couvre pas toute la zone.
Je sais que la question peut être un peu dépassée, mais j'ai récemment eu un problème similaire avec une zone géographique avec des cercles égaux en utilisant une grille hexagonale et c'est comme ça que je résolvai-je:
Comme dans une image donnée, bien sûr, vous pouvez augmenter la précision en diminuant le rayon de cercle
Je sais que ce n'est pas la meilleure option mais ça marche assez bien pour moi.
J'espère que c'est assez compréhensible et aidera tout le monde.
Bonjour, je cherche à résoudre le même problème si je ne suis pas totalement à la suite de votre code sudo. Seriez-vous capable de me fournir votre implémentation? Merci!
Les cercles ne tassellent pas, vous ne pouvez donc pas le faire parfaitement sans chevauchement. Pouvez-vous clarifier votre problème?
Édité ma réponse pour inclure une méthode qui couvre toute la zone. :-)
Quelle est l'importance de "couvert de quelques cercles que possible"? S'il n'est pas essentiel d'utiliser le nombre minimum absolu de cercles, les techniques telles que Eric Bainville peuvent donner de bons résultats pour de nombreux cas.
Les cercles doivent-ils avoir la même taille? Que les cercles chevauchent le bord de la forme?
Les cercles doivent avoir la même taille. Ils peuvent chevaucher le bord de la forme.
Je pense que l'approche hexagonale est une bonne approximation pour résoudre le problème du cercle égal du problème. Cependant, il est parfois le cas qu'il ne résoudra pas parfaitement le problème. Vous voudrez peut-être vérifier: arxiv.org/abs/2003.04839 qui utilise des algorithmes génétiques et une optimisation BFGS à résoudre ce problème. Le code source est également contenu dans le papier.