Bedecken einer beliebigen Fläche mit Kreisen gleichen Radius

Question

Wie würde ein Algorithmus arbeiten, der eine beliebige Fläche mit Kreisen mit gleichem Radius abdeckt?

Der Radius des Kreises und die Größe und Form des Bereichs sind willkürlich angegeben. Das Gebiet sollte mit möglichst wenigen Kreisen abgedeckt werden. Die Kreise können sich überlappen.

Gibt es einen Algorithmus, der damit umgehen kann?

Answer 1

Ohne mehr über Ihre Beschränkungen zu wissen, würde ich vorschlagen, eine regelmäßige Abdeckung des Flugzeugs zu nehmen, mit Scheiben, die den regelmäßigen Sechsecken eines hexagonalen Tilings entsprechen. Halten Sie dann alle Scheiben, die die Form schneiden.

Answer 2

Hoffnung Ich habe Ihre Frage richtig verstanden ...

nachgewiesen werden kann, dass Hexagonal Close (HCP) Verpackung von Kugeln umfasst das maximale Volumen, mit Kugeln. Daher gehe ich davon aus, dass HCP mit Kreisen auch die maximale Fläche mit Kreisen abdecken wird. Tesselliere deine Fläche mit Dreiecken und platziere einen Kreis mit der Mitte an jedem Eckpunkt des Dreiecks, mit dem Radius die Hälfte der Länge der Seite des Dreiecks. Siehe this für ein Bild des Algorithmus, über den ich spreche.

Hinweis: Dies ist vergleichbar mit der close packing of atoms in a unit cell.

EDIT: Meine vorherige Methode deckt so viel von der Fläche wie möglich ab, ohne sich zu überlappen. Wenn Überschneidungen erlaubt sind, würde (so glaube ich) das folgende Verfahren das gesamte Gebiet mit minimalen Überlappungen abdecken.

Wie Sie wahrscheinlich wissen, gibt es nur 3 Tesselationen von 2D-Raum mit regelmäßigen Polygonen - mit Quadraten, Dreiecken oder Sechsecken. Die Strategie besteht darin, mit einem dieser Polygone zu tessellieren und dann einen Kreis zu jedem Polygon zu umschreiben. Ein Sechseck würde die minimale Fläche mit dieser Methode verschwenden.

Berechnen Sie daher aus dem Radius des gegebenen Kreises die Größe der benötigten Sechsecke, tessellieren Sie die Fläche mit den Sechsecken und umschreiben Sie dann einen Kreis auf jedes Sechseck.

Anmerkung:Eric Bainville schlug eine ähnliche Methode vor.

-- Flaviu Cipcigan

Answer 3

Ich weiß, dass diese Frage ein bisschen veraltet sein kann, aber vor kurzem habe ich ein ähnliches Problem mit Abdeckung geografischen Gebiet mit gleichen Kreisen hexagonalen Gitter verwenden und das ist, wie ich es gelöst:

1. mein Eingabedaten waren Radius des Kreises in Metern und Koordinaten der Grenzen des Gebietes
2. zuerst fand ich das Begrenzungsrechteck, das den gegebenen Bereich
3. dann beginnend von der linken Unterseite bedeckte ich bewege mich Punkt für Abstand gleich doppelt so hoch wie das Dreieck, das zum Aufbau des Sechsecks verwendet wurde (und die Seite ist gleich dem Radius meines Kreises) und Peilung von 0 Grad mit den Formeln
4. für jeden Punkt, den ich gefunden habe, überprüfe ich, ob es sich schneidet meine Eingangsbereich, wenn tut ich es, andere Art und Weise spare ich es
5. überspringen, wenn ich an den Rand habe ich eine weitere Überprüfung zu tun, um sicherzustellen, dass ich alle Punkte innerhalb der
6. sind ich den Punkt bewegen durch das Lager von 60 Grad, überprüfen Sie es, dann um 120 Grad, überprüfen Sie erneut
7. zurück zum 3. Schritt, aber jetzt verschiebe ich die Punkte von 180 Grad
8. und die Kante noch einmal überprüfen und dann wie in Schritt 6.en aber zuerst um 120 Grad dann 60 Grad
9. weiter bis zur oberen Kante des Rechtecks ​​erhalten

wie in gegebenen Bild, natürlich kann die Genauigkeit erhöhen, indem abnehmenden Radius von Kreis

Ich weiß, dass dies nicht die beste Option ist, aber es funktioniert ziemlich gut für mich.

Ich hoffe, es ist ziemlich verständlich und wird jedem helfen.