Suche nach freien, sich nicht überschneidenden rechteckigen Bereichen zwischen Rechtecken in C#

Ich habe ein folgendes Problem. Ein großes Rechteck enthält kleinere, sich nicht überschneidende Rechtecke (die schwarzen Rechtecke im Bild unten) und ich muss einen Algorithmus finden, um die verbleibende freie Fläche mit sich nicht überschneidenden Rechtecken zu füllen (rote im unteren Bild). Geschwindigkeit ist kein Problem für den Algorithmus. Auch wenn jemand einen Beispiel-Quellcode des Algorithmus hätte, würde ich das wirklich schätzen.Suche nach freien, sich nicht überschneidenden rechteckigen Bereichen zwischen Rechtecken in C#

Bearbeiten. Kleine Klärung Ich brauche die Koordinaten der roten Rechtecke, um sie nicht zu zeichnen. Ich arbeite auch mit Punktdaten und nicht mit Bildern.

http://koti.mbnet.fi/niempi2/Squares.gif

Quelle

2010-08-04 Jargo

Beginnen Sie mit Punktdaten oder einem Bild? –

Punktdaten, dh Koordinaten der schwarzen Rechtecke im Bild. Ich muss auch die Koordinaten der roten Rechtecke erhalten und sie nicht einfach zeichnen. – Jargo

Es gibt mehr als eine Möglichkeit, einen Satz roter Rechtecke für eine bestimmte Menge schwarzer Rechtecke zu definieren. Kümmert es dich, welches Set zurückgegeben wird? –

Wie die meisten bin-packing-Probleme sieht mir das wie ein NP-schweres Problem. Mit 2 Rechtecken gibt es 8! (= 40320) mögliche Vereinbarungen, die Sie berücksichtigen müssen. Drei Rechtecke ergeben 12! Möglichkeiten, eine coole 480 Millionen.

Sie benötigen eine Heuristik, um dies berechenbar zu machen. Jenseits der Bevorzugung der äußeren Ränder der Rechtecke, die dem begrenzenden Rechteck am nächsten sind, sehe ich keinen guten. Sie würden strengere Anforderungen an die resultierenden Rechtecke, die Sie akzeptieren, benötigen, die Anzahl von ihnen wird nicht helfen. Froh, das ist nicht mein Problem :)

Quelle

2010-08-04 15:36:16

Wie schon gesagt, das Layout der Rechtecke spielt keine Rolle und tatsächlich kann ich die Anforderung, eine möglichst kleine Anzahl von Füllrechtecken zu haben, fallen lassen. Ich muss also nicht jede mögliche Lösung durchgehen, weil ich einfach die erste auswählen kann, die den ganzen leeren Raum ausfüllt. Die Lösung, die ich dachte, war, zuerst die 4 äußersten Füllrechtecke zu berechnen, was eine einfache Aufgabe ist, und danach die mittleren Rechtecke separat zu berechnen, in diesem Fall hätten Sie nur 4! mögliche Anordnungen mit 2 Rechtecken. – Jargo

Sie scheinen bereits zu wissen, wie man das macht. Warum hast du gefragt? –

@Nobugz: Kannst du mir bitte sagen, wie du berechnet hast 2 Rechteck würde 8 erfordern! und 3 würde 12 erfordern !? –

Blick auf die Region Klasse.

Quelle

2010-08-04 13:46:17 leppie

Bitte hören Sie auf, Namen von Personen ohne Grund oder Provokation anzurufen, wenn Sie ihre Fragen neu einreichen. Vor allem, wenn das Miss-Tagging auf einen [Bug] reduziert ist (http://meta.stackexchange.com/questions/59556/tags-with-uppercase-characters-get-cut) –

Obwohl es mehrere mögliche Lösungen gibt, denke ich, dass Sie ziemlich leicht zu einem kommen können.

Ich würde in steigenden Werten entlang einer Achse arbeiten. Durch das Scannen aller Rechtecke und das Ordnen der Kanten entlang dieser Achse können Sie durch sie hindurchgehen und Rechtecke erstellen, während Sie fortfahren. Jedes Mal, wenn Sie ein neues Paar Ecken treffen, können Sie mit den Rechtecken, die Sie gerade geöffnet haben, vergleichen und bestimmen, was zu tun ist (schließen Sie sie, beginnen Sie neu, teilen Sie usw.).

Diese Aussage ist keine vollständige Lösung, aber ich denke, es bringt Sie von einer komplexen Lösung zu einer einfachen Lösung. In Bezug auf die Leistung scheint es auch nicht NP-vollständig zu sein. Sie könnten sogar O (n) perf bekommen.

Ein interessantes Problem. Lass uns wissen, wie es dir geht.

Quelle

2010-08-05 14:48:09

Suche nach freien, sich nicht überschneidenden rechteckigen Bereichen zwischen Rechtecken in C#

Antwort

Verwandte Themen