# Optimale Flächenaufteilung (2D)



## Tyvan (14. Jun 2009)

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 (14. Jun 2009)

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 (14. Jun 2009)

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 (14. Jun 2009)

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 (14. Jun 2009)

Tyvan hat gesagt.:


> 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 (14. Jun 2009)

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 (14. Jun 2009)

Tyvan hat gesagt.:


> 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 (14. Jun 2009)

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 (14. Jun 2009)

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 (14. Jun 2009)

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 (14. Jun 2009)

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


----------



## Landei (15. Jun 2009)

Vielleicht hilft das: Delaunay-Triangulation ? Wikipedia


----------

