Huhu,
ich hab ein mathematisches Problem für das ich leider zu blöd oder zu müde bin…
Ich habe eine Fläche die aus kleinen 4ecken besteht (4x4). Definiert ist die Fläche durch eine lange Liste von Vektoren die jeweils den Mittelpunkt eins kleinen 4ecks beschreiben (z.B.: ; ; usw.). Die x und y Werte liegen immer zwischen 2 und 254, der z Wert wird nicht benötigt. Nun muss ich die Fläche in möglichst wenige 4ecke (Rechtecke) unterteilen. Von den neuen 4ecken benötige ich dann die Kantenlängen und den Mittelpunkt.
Ich hab mal zwei Beispiel-Bilder gemacht:
http://img296.imageshack.us/img296/9615/beispiel1ro7…
http://img222.imageshack.us/img222/7097/beispiel2uq5…
Meine Frage wäre, gibt es irgendeine Art Formal oder Trick um die optimale Unterteilung der Fläche in große 4eck zu errechnen? Mir stehen umfangreiche statistische und mathematische Operationen zur Verfügung. Ich kann dabei einzelne Vektoren verarbeiten, Gruppen oder nur ein Werte-Gruppe der Vektoren.
Für Hilfe wäre ich dankbar!
Gruß
Nick
Moin, Nick,
Du kannst die Ecken bestimmen, fragen, ob sie innen oder außen liegen, und von dort aus suchen, wie weit es von den innen liegenden bis zum nächsten Rand und von den außen liegenden bis zur nächsten Ecke ist.
Gruß Ralf
Hallo Nick,
Lösung habe ich leider keine für Dich, allerdings wollte ich Dich darauf hinweisen, dass das Problem ohne Zusatzbedingungen gar nicht eindeutig lösbar ist. Ein Beispiel: Das Vieleck
+--+
| |
| +--+
| |
+-----+
kann man so
+--+
| |
| +--+
| | |
+-----+
und so
+--+
| |
|--+--+
| |
+-----+
in zwei Rechtecke zerlegen.
Um doch noch auf einen Lösungsansatz zu kommen: Überlege Dir einfach, wie Du händisch vorgehst, daraus lässt sich sicher ein Algorithmus zaubern.
Gruß
Martin
@Martin: Ja, ich hatte zuvor schon etwas rum gesucht und eine bildliche Erklärung leider ohne mathematischen Ansatz gefunden. Dort wurde erklärt es gäbe wohl jeweils 4 mögliche Wege, Vertikal von links nach rechts, Vertikal von rechts nach links und das ganze nochmal für Horizontal. Es gäbe ja die Möglichkeit jeweils alle Wege zu untersuchen und sich dann für den besten zu entscheiden. Wobei ich nicht sicher bin ob es bei einem der 4 Wege überhaupt einen Unterschied in der letztendlichen Anzahl der 4ecke gibt.
@Ralf: Es irgendwie über die Ecken zu Versuchen war bisher auch mein Ansatz, ich werd da mal weiter basteln…
Danke an euch!
