Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Algorithmus gesucht (evtl Stochastik)
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Algorithmus gesucht (evtl Stochastik)
 
Autor Nachricht
hoshis
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.10.2004
Beiträge: 1

BeitragVerfasst am: 01 Okt 2004 - 09:55:41    Titel: Algorithmus gesucht (evtl Stochastik)

Hallo zusammen,

ich programmiere in VBA ein größeres Tool zur Topologieprüfung von Vektordaten. Ich stehe jetzt vor einem relativ komplexen Problem, für welches ich mir erst einmal eine theoretische Lösung bereitstellen will. Dazu möchte ich in der Literratur und im Netz recherchieren, ich weiss nur nicht wonach ich suchen muss..

Meine Fragen dazu:

Ist dieses Problem schon einmal näher beleuchtet wurden? Gibt es Literatur? Unter welchen Stichworten muss ich nach Informationen suchen?


Problembeschreibung

Es handelt sich um mehrere verschieden große Flächen, die sich überlappen, ineinanderliegen, gleich oder disjunkt sind. Man kann sich das in etwa so vorstellen, dass man einen Stapel verschieden großer Karten nimmt und diesen auf den Boden wirft.

Ich möchte nun wissen, welche Flächen übereinanderliegen. Mir liegen jeweils die Informationen über die Beziehungen wischen 2 Flächen vor (A ist gleich B, A überlappt B, A liegt innerhalb B, A enthält B, A und B sind disjunkt). Beispiel: Flächen A,B,C --> Informationen A/B, A/C, B/C. Aus der Kombination dieser Informationen weiss ich 100%ig welche Flächenüberlagerungen es gibt, z.B. wenn alle drei Flächen identisch sind ergibt das die Überlagerung ABC.

Mir ist bekannt, wie ich vorgehen müsste, um alle Überlagerungen herauszufinden. Am besten lässt sich dass in mehreren Matritzen machen. In der ersten Spalte und Zeile stehen die zu vergleichenden Flächen. Die Matritzen werden dann mit den Informationen über die geometrischen Beziehungen gefüllt. Es sind folgende Schritte nötig:

- ich habe x Flächen A,B,..,Z

1. Vergleich der Flächen untereinander:
A mit B, A mit C, ... A mit Z
B mit C, B mit D, ... B mit Z
.....
Y mit Z

2. Vergleich von Schnittflächen (aus 2 Flächen) mit allen anderen Flächen
ausser den beiden verschnittenen Flächen
(Schnittfläche zwischen A und B = A.B)
A.B mit C, A.B mit D, ... A.B mit Z
B.C mit A, B.C mit D, ... B.C mit Z
.... usw.

3. Vergleich von Schnittflächen (aus 3 Flächen) mit allen anderen Flächen
ausser den 3 verschnittenen Flächen
A.B.C mit D, A.B.C mit E, ... A.B.C mit Z
A.B.D mit C, A.B.D mit E, ... A.B.D mit Z
usw.

Das ganze wird so lange getrieben, bis alle möglichen Kombinationen getestet wurden.

Zusätzlich muss noch geprüft werden, ob es ein Teilstück der Teilfläche (Zeile der Matrix) ohne Überlagerung gibt, z.B. A ohne B UND ohne C UND ... UND ohne Z.

Als Ergebnis erhalte ich Zeilen mit den geometrischen Beziehungen. Einige Beispiele der Ergebnisse:

Vergleich von A mit B,C, D -->> ich erhalte für jede Kombination disjkunt --> es gibt eine Fläche A aber kein AB, AC, AD, ABC, ABD, ACD, ABCD

Vergleich von A mit B,C, D -->> ich erhalte für jede Kombination A liegt in der anderen Fläche --> es existiert eine Fläche ABCD aber keine andere Kombination, da A immer in B,C und D liegt (Einzelaulistungen nach dem Motto, wenn ABC dann auch AB und AC nicht erlaubt)

Dazu muss man noch wissen, dass nur die Informationen "A liegt in B", "A und B sind gleich" und "A und B sind disjunkt" von nutzen sind. D.h. dass nur Zeilen ohne "überlappen" und "enthält" ein Ergebnis liefern.

Wenn man das ganze Problem durchspinnt, dann kommt man schon bei mehr als 5 Flächen in Probleme.

Ich habe einige Ideen bezüglich Abbruchbedingungen etc.
Das Programm ist meine Diplomarbeit, daher ist es wichtig, wenn ich wüsste, ob dieses oder ein ähnliche Problem schon einmal untersucht wurde. Wenn ja von wem bzw. unter welcher Thematik kann ich das finden?
Es gibt zwar google, aber ich weiss nicht einmal unter welchem Begriff ich suchen soll.

mfg
Sebastian
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Algorithmus gesucht (evtl Stochastik)
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum