Optimale Flächenaufteilung (2D)

[Tyvan]

Hi alle,

habe hier ein recht kompliziertes Problem.
Ich habe mich schon nach evtl. vorhandenen freien Java Klassen umgesehen, doch fand ich nichts.

Ich brauche ein Algorithmus dem ich in Pixeln eine Fläche (breite, höhe) angebe und noch eine Zahl die angibt in wie viele Flächen ich diesen Bereich aufteilen möchte.

Also z.B. Fläche 600x500 (in Pixel). Und ich gebe die Zahl 10 an. Dann sollte die Fläche optimal, also möglichst alle Subflächen gleichgross aufgeteilt werden.
So dass ich diese Aufteilung nutzen und später einfache Abfragen machen wo z.B. ein bestimmter Punkt liegt.

Dadurch würde ich z.B. diese aufgeteilten Flächen benennen, z.B. von F_1 bis F_n. Wenn ich dann prüfen will in welcher Fläche ein Punkt liegt würde ich z.B. den Flächennamen oder nummer zurückgeliefert bekommen.

Ich weiss gar nicht wie man sowas genau nennt. Ist das ein Area-Splitting? Finde absolut nix darüber.

Hoffe einer kann helfen.


Grüße

 

[madboy]

Wie sollen die "Subflächen" aussehen? Wenn die große Fläche rechteckig und die Form der "Subflächen" beliebig ist, könntest du sie in z "Streifen" aufteilen, also Rechtecke mit Höhe y/z und Breite x

 

[Tyvan]

Das ist eigentlich egal. Da die Subflächen ja optimal also möglichst gleichgross sein sollten, kämen hier also Polygonflächen in Frage.

Aber ich glaube das ist viel zu komplex. Das geht doch schon in die Richtung "NP-vollständig".

Ich könnte das Problem aber etwas vereinfachen.

Bleiben wir nicht bei Polygonflächen, sondern immer bei rechteckigen bzw. quadratischen.

ABER die Zahl welche die Anzahl der subflächen angibt, sollte beim Algorithmus insoweit (möglichst gering) verändert werden dass man immer eine einfache Rechteck aufteilung oder quadratische Aufteilung der Flächen erhält.

Beispiel: Wieder die 600x500. Nun gibt mir aber jemand die Zahl 3. Diese Fläche in 3 Subflächen aufzuteilen ist nur im Polygonzug möglich und recht komplex (exponentiell?). Eine optimale Aufteilung wäre aber 4. also erhöhe ich den Wert auf 4 und kann eine optimale Vierteilung machen, also Strich waagerecht und senkrecht durch die Mitte.

So gesehen müsste ich ungerade Zahlen nicht mehr erlauben, weil bei ungeraden Zahl schwierige Aufteilungen kommen. Ich glaube das wäre wesentlich einfacher.

Ausser irgendjemand hat immer noch eine möglichst effektive Methode mit der Polygonvariante, wäre natürlich super.

 

[musiKk]

Ich kann aus der Frage nichts ablesen, was gegen den Vorschlag von madboy spricht. Wieso kann man eine Fläche von 600x500 nicht in drei Flächen zu je 200x500 aufteilen? Was heißt "nur im Polygonzug möglich"? Ein Rechteck ist auch ein Polygon.

 

[Marco13]

Beispiel: Wieder die 600x500. Nun gibt mir aber jemand die Zahl 3. Diese Fläche in 3 Subflächen aufzuteilen ist nur im Polygonzug möglich und recht komplex (exponentiell?).

Hab das gerade mal meinen Roadrunner-Petaflops-Rechner durchrechnen lassen. Eine grobe Approximation der optimalen Lösung wäre in diesem Fall:
1. Fläche mit 199.45646 Breite und 499.452345 Höhe
2. Fläche mit 201.034223 Breite und 501.34234 Höhe
3. Fläche mit 201.417657 Breite und 499.0021234 Höhe

( :joke: )

Worum geht's denn eigentlich?

 

[Tyvan]

Bei 3 wäre das noch ok.

aber nach madboy würde ich ja immer nur Streifen kriegen. Also alle Flächen nur nebeneinander oder übereinander.
Wie sieht es mit einer gleichmäßigen Verteilung aus?

Die Streifen nutzen ja immer einen großen Bereich der Ursprungsfläche aus, also z.B. der Länge nach oder der Höhe nach.

Bei z=10 kämen also nicht 10 mal 600x50 Flächen oder 60x500 Flächen in Frage sondern 5 Flächen in erster Reihe und 5 Flächen in zweiter Reihe. Ich hätte wohl noch das gleichmäßige Verteilung erwähnen müssen.

Aber die Streifen wären natürlich schon mal ein Ansatz.

 

[musiKk]

Ich hätte wohl noch das gleichmäßige Verteilung erwähnen müssen.

Yeah.

Du musst diese "Gleichmäßigkeit" irgendwie quantifizieren. Wie, das hängt von Deinem Problem/Chef/Gutdünken/etc. ab. Du könntest z. B. das Verhältnis von Höhe zu Breite der Teilflächen nehmen und beginnend mit einer Spalte (also nur Streifen) so lange neue Spalten hinzunehmen, bis dieses Verhältnis optimal ist.

 

[Marco13]

Ich schätze mal, dass man "Gleichmäßigkeit" in diesem Fall mit "Quadratischkeit" gleichsetzen kann. Dann könnte man sich verschiedene Ansätze überlegen. Geht es wirklich um Flächen (und Flächenanzahlen) die ein Computer NICHT innerhalb von 100 Millisekunden einfach durchprobieren kann?

 

[Tyvan]

Also ich habe mir mal folgendes überlegt:

Wenn ich eine Flächenanzahl von 10 bekomme, dann versuche ich zwei Multiplikanten zu bekommen die einen sehr geringen abstand zueinander haben und deren Produkt natürlich 10 ergibt.
Die beste Wahl ist hier 2x5 oder 5x2. Bei 20 wären das 5x4 oder 4x5.

So habe ich ja schonmal Flächen die möglichst gleichverteilt sind und annähernd quadratisch.
Denn möglich wäre ja auch 1x10, aber das sieht ja nicht gleichverteilt aus.
Ungerade Flächenanzahlen verwende ich nicht. Wenn ich dennoch 11 bekomme, erhöhe ich diesen Wert auf die nächste gerade Zahl, also 12. Und bei 12 ist die beste Aufteilung 3x4 oder 4x3.

Das Problem hierbei wiederum ist das nicht bei jeder flächengröße diese aufteilung immer so einfach sind.
bei einer fläche von 632x512 zum Beispiel und der Zahl 10 wäre eine Fläche 126,4x256 gross. Aber in Pixeln gibt es keine unganzen Zahl wie die 126,4. Also müsste ich 127 wählen, hätte aber am Ende zu viele Pixel in der Breite und würde über die Ursprungsfläche hinaus gehen. Das war das eigentliche Problem.

Ich könnte natürlich ganz einfach die Gesamtfläche nehmen, sie durch die Flächenanzahl teilen, dann diese Zahl in die Wurzel nehmen und so hätte ich die durchschnittliche Breite und Höhe einer jeden Fläche, aber die Flächenausnutzung wäre ja nicht garantiert.

 

[Marco13]

Das Problem mit den "ungeraden" Pixelzahlen hat genau 2 Lösungsmöglchkeiten: Entweder, die Rechtecke sind nicht alle gleich breit (sondern weichen z.B. um 1 Pixel voneinander ab), oder die Fläche wird nicht ganz ausgefüllt. (<-Punkt. Mehr gibt's da nicht).

Ansonsten klingt das mit den Faktoren und der Wurzel nach dem, was mir auch als erstes in den Sinn kam, aber so einfach ist das u.U. nicht. Bei einer Fläche von 1000x10 sollte eine Einteilung in 10 Unterflächen ja evtl. nicht 5x2 (der Größe 200x5) liefern, sondern vielleicht 10x1 (der Größe 100x10).

Aber nochmal: Solange es da um Zahlen wie 10 oder auch 100 geht, kann man innerhalb von wenigen Mikrosekunden alle Kombinationen durchprobieren....

 

[faetzminator]

Der gesuchte Faktor muss einfach möglichst nah an der Fläche sein.

 

[Landei]

Vielleicht hilft das: Delaunay-Triangulation ? Wikipedia