Das kleinste, mögliche Rechteck, welche n definierte kleinere Rechtecke enthält

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Das kleinste, mögliche Rechteck, welche n definierte kleinere Rechtecke enthält

    Guten Morgen zusammen,

    privat beschäftige ich mich viel mit dem Thema Holz und Holzbearbeitung und suche aktuell noch eine Lösung dafür 'mal eben schnell' zumindest grob zu überschlagen, welche Maße die nächste Plattenware für das geplante Projekt haben muss.

    Ich habe also n bekannte Maße von Teilstücken des Projektes und würde gerne die kleinsten möglichen Gesamtmaße der Platte ermitteln, in die alle diese Teilstücke rein passen. Zusätzlich wäre es vielleicht interessant, dass der Nutzer ein maximal Maß für seine Platte angeben können sollte und dann, wenn diese erreicht ist, alle übrigen Teilstücke auf weitere Platten verteilt werden.

    Ich würde mich freuen, wenn mir hier jemand einen groben Denkanstoß für die Mathematik hinter der Idee geben könnte, da ich im Moment ziemlich auf dem Schlauch stehe. Mir ist weder klar, wie sich das Problem mathematisch lösen ließen, aber vor allem nicht wie sich die mir bisher verborgene Lösung dann im Code realisieren lässt.

    Ich bin gespannt auf eure Rückmeldungen!

    Grüße,
    Daniel
    Man kann alles schaffen. Man muss es nur wollen ;)
    www.regetskcob.github.io
  • Hi Daniel,
    da hast du dir aber eine Aufgabe gesucht. Das führt ja im Endeffekt auf ein NP-Problem hinaus - das Packungsproblem.

    Also gibt es dafür keinen exakten Algorithmus aber Annäherungen. Ich hab mal schnell gegoogelt und hab diese Arbeit von der UNI Stuttgart gefunden. Gleich am Anfang gehen die auch darauf ein. Hier halt statt mit Holz mit Blech:
    UNI Stuttgart Packungsproblem

    Vlt. bekommst du daraus ja ein paar Ideen. Mit Rechtecken dürfte es vom Prinzip her ein Stück einfacher werden aber es gibt halt immer eine große Anzahl möglicher Anordnungen.

    Viele Grüße
    Nils
  • AppleDeveloper schrieb:

    Hi Daniel,
    da hast du dir aber eine Aufgabe gesucht. Das führt ja im Endeffekt auf ein NP-Problem hinaus - das Packungsproblem.

    Also gibt es dafür keinen exakten Algorithmus aber Annäherungen. Ich hab mal schnell gegoogelt und hab diese Arbeit von der UNI Stuttgart gefunden. Gleich am Anfang gehen die auch darauf ein. Hier halt statt mit Holz mit Blech:
    UNI Stuttgart Packungsproblem

    Vlt. bekommst du daraus ja ein paar Ideen. Mit Rechtecken dürfte es vom Prinzip her ein Stück einfacher werden aber es gibt halt immer eine große Anzahl möglicher Anordnungen.

    Viele Grüße
    Nils
    Morgen Nils,

    danke für die schnelle Antwort, dein Google-fu und den Hinweis auf den Oberbegriff "Packungsproblem" :)

    Ich hab mir die Arbeit mal ausgedruckt uns sehe sie mir am Nachmittag/Abend mal näher an, wenn ich von garten- und Holzarbeit zurück bin.

    Schöne Grüße,
    Daniel
    Man kann alles schaffen. Man muss es nur wollen ;)
    www.regetskcob.github.io
  • Danke Euch beiden für diesen Thread: Er ergab ein nettes Gespräch mit meinem Sohn beim Frühstück und ich habe eben (nur kurz) interessiert in die verlinkte Arbeit geschaut und an NP-vollständige Probleme gedacht...

    Schön, wenn hier ab und zu allgemeine Fragen zu Algorithmen aufkommen :D

    Sonnigen Samstag, Mattes
    Diese Seite bleibt aus technischen Gründen unbedruckt.
  • MyMattes schrieb:

    Danke Euch beiden für diesen Thread: Er ergab ein nettes Gespräch mit meinem Sohn beim Frühstück und ich habe eben (nur kurz) interessiert in die verlinkte Arbeit geschaut und an NP-vollständige Probleme gedacht...

    Schön, wenn hier ab und zu allgemeine Fragen zu Algorithmen aufkommen :D

    Sonnigen Samstag, Mattes
    Hi Mattes,

    schön, wenn ich dir (und deinem Sohn) mit meinem problem den Tag etwas verschönern konnte :) Geh ruhig näher auf eure Gedanken ein?

    Ich bin vor all der Gartenarbeit leider noch nicht wirklich zum lesen gekommen, ich hoffe morgen Zeit zu finden, bevor der eigentliche Beruf wieder ruft.

    Grüße,
    Daniel
    Man kann alles schaffen. Man muss es nur wollen ;)
    www.regetskcob.github.io
  • gritsch schrieb:

    Da es sich um Holz handelt, sind die Platten wohl nicht sehr groß und die Rechtecke die daraus geschnitten werden nicht sehr klein. Warum also nicht einfach alle berechnen und die optimalste lösung verwenden? ;)
    Ansonsten hilft dir vielleicht auch das Stichwort "Verschnittoptimierung".
    Je nach dem, was jetzt sehr groß bedeutet :D Normales Holz-Platten Maß ist eigentlich 3,50 m x 2,00 m, Für einen Menschen schon recht unhandlich, theoretisch natürlich nicht gerade riesig. :)

    Verschnittoptimierung ist quasi genau das, was ich vor habe. Stimmt, der Begriff war irgendwie nicht präsent in dem Moment.
    Man kann alles schaffen. Man muss es nur wollen ;)
    www.regetskcob.github.io
  • Wenn du wenig Bretter aus der Platte schneiden willst, kannst unter Umständen schon ein Brute-Force-Verfahren nehmen. Ansonsten gibt's da bestimmt auch Verfahren mit Dynamischer Programmierun oder Backtracking. Da Kreissägen in der Regel eine Schnittbreite größer 0mm haben, sollte das der Algorithmus ggf. auch noch berücksichtigen können.
    „Meine Komplikation hatte eine Komplikation.“
  • macmoonshine schrieb:

    Wenn du wenig Bretter aus der Platte schneiden willst, kannst unter Umständen schon ein Brute-Force-Verfahren nehmen. Ansonsten gibt's da bestimmt auch Verfahren mit Dynamischer Programmierun oder Backtracking. Da Kreissägen in der Regel eine Schnittbreite größer 0mm haben, sollte das der Algorithmus ggf. auch noch berücksichtigen können.
    Morgen Mondschein,

    die Schnittbreite, sowie auch eine Besäumkante (rund um das Brett, weil rechtwinkligkeit nicht 100% sicher) sind bereits im Kopf vorgesehen :)

    Grüße,
    Daniel
    Man kann alles schaffen. Man muss es nur wollen ;)
    www.regetskcob.github.io
  • gritsch schrieb:

    Die Frage ist ja auch mit welcher Technik "geschnitten" wird.
    Wird gestanzt, kann man anordnen wie man will, wird jedoch mit einer Kreissäge geschnitten muss man die Rechtecke so anordnen dass man diese auch auschneiden kann.
    Es geht tatsächlich um das Schnieden von Holz-Plattenware in mehrere kleinere Bestandteile, bspw. für ein Regal. Daher wäre ein 'Durchschneiden' kaum zu umgehen :)
    Man kann alles schaffen. Man muss es nur wollen ;)
    www.regetskcob.github.io