Ich habe SVG-Abirtrary-Pfade, die ich innerhalb eines bestimmten Rechtecks ​​so effizient wie möglich packen muss (so wenig Platzverschwendung wie möglich). Nach einigen Recherchen habe ich die Bin-Packing-Algorithmen gefunden, bei denen es sich anscheinend um Kästchen und nicht um gekrümmte Zufallsformen handelt (meine SVG-Formen sind recht komplex und enthalten Beziers usw.).

AFAIK, es gibt keinen deterministischen Algorithmus zum tatsächlichen Packen abstrakter Formen.

Ich möchte hier als falsch erwiesen werden, was ideal wäre (mit einer mathematisch deterministischen Methode, um sie zu packen). Falls ich jedoch Recht habe und es nicht gibt, was wäre der beste Ansatz für dieses Problem

Der Betreff lautetFormverschachtelung, Verschachtelungsproblem oder Verschachtelungsprozess.

Bei der Formverschachtelung gibt es keinen einzigen / einheitlichen Algorithmus oder keine mathematische Methode, um Formen zu verschachteln und so wenig Platz wie möglich zu verschwenden.

Die erste Methode ist der Verpackungsalgorithmus (erstellt einen imaginären Begrenzungsrahmen für jede Form und verwendet einen rechteckigen 2D-Algorithmus zum Verpacken der Begrenzungsrahmen). Diese Methode ist schnell, aber in Bezug auf Platzmüll am wenigsten effizient.

Die zweite Methode ist eine Art inkrementelle Rotation. Der Algorithmus dreht die Form in inkrementellen Schritten und prüft, ob sie in den Raum passt. Dies ist in Bezug auf Weltraummüll besser als die Verpackungsmethode, aber es ist akribisch langsam.

Was sind andereBeispiele aus dem Klassenzimmer Um eine Lösung für dieses Problem zu finden?