Packen ein unregelmäßiges Polygon mit verschiedenen Größen

Question

Dies ist mein erster Beitrag, also lass es mich wissen, wenn ich irgendwelche Regeln der Anstand brechen.

Ich versuche, ein Programm in Python mit formschönen zu schreiben, die Formdateien (gerade Kongressbezirke) aufnimmt und sie mit Kreisen "verpackt". Das Endziel ist es, die Mittelpunkte und Radien der Kreise zu haben. Ich möchte die maximale Fläche mit der geringsten Anzahl von Kreisen abdecken.

Alle Ressourcen, die ich über Google bisher gefunden habe, sind über Kreispackung innerhalb von geometrischen Standardobjekten wie Quadrate/Kreise/Dreiecke etc ... Also mein Instinkt ist es zu versuchen, diese Formen in Dreiecke oder etwas und dann zu verwandeln Wenden Sie einen vorhandenen Algorithmus auf die einfacheren Formen an.

Scheint dies der richtige Weg zur Problemlösung, wenn die Formen viele kleine konkave Kanten haben? Oder gibt es einen Algorithmus, den ich nicht über Google finden konnte? Total Computational Geometrie noob aber bereit zu lernen.

Answer 1

Sie könnten mit dieser wegweisenden Arbeit beginnen und dann rückwärts & vorwärts in der Zeit mit Google Scholar bewegen:

Bern, Marshall und David Eppstein. "Quadrilaterales Ineinandergreifen durch Kreisverpackung." International Journal of Algorithmische Geometrie & Anwendungen 10.04 (2000): 347-360.

---

         
          ^{Teil von Fig.1}

---

Insbesondere ein großer Teil der Arbeit ist auf Polygone mit Kreisen zu erreichen spezifische Eigenschaften, zB

---

         

---