Graphentheoretisches Problem
-
Hallo, mir ist ein Problem untergekommen, das wahrscheinlich in die Richtung Graphentheorie gehen müsste. Das Dumme ist, dass meine Kenntnisse da nur sehr rudimentär sind. Vielleicht fällt ja jemandem der sich da besser auskennt was ein? Sorry, falls die Problembeschreibung etwas laienhaft klingt
Adjazenzen aufbauen mit implizit gegebenen und teuren Kanten: Gegeben ist die nichtüberlappende Partition eines Polyeders in viele kleine Polyeder. Gesucht ist eine Adjazenz zwischen den sich (im Sinne einer gemeinsamen Fläche) berührenden Polyedern. Das heißt, um rauszufinden ob A und B durch eine "Kante" (im Sinne der Adjazenz) verbunden sind muss ich deren Randflächen schneiden, was als Operation gesehen ziemlich teuer ist. Wie baue ich also bei vielen Polyedern eine Adjazenz auf (z.B. A grenzt an B und G usw.), wobei ich möglichst wenige solcher teurer Prüfungen machen muss?
Die Prüfung ob A an B grenzt ist vorhanden und sicher auch noch nicht optimal gelöst, aber ich vermute massives Einsparpotential in dem oben skizzierten Part, denn mein jetziger Ansatz ist ziemlich Brute-Force, dementsprechend also auch sehr schlecht skalierbar.
-
Da du eine nicht überlappende Partitionierung hast, sind zwei Polyeder genau dann adjazent, wenn sie zwei sich schneidende Randflächen mit gleichem Normalenvektor haben. Du kannst also für jede Randfläche den Normalenvektor und das Skalarprodukt eines Punktes der Fläche mit dem Normalenvektor speichern und alle Randflächen gemäß dieser Werte gruppieren. Zwei Polyeder können nämlich nur dann adjazent sein, wenn es Randflächen gibt, für die beide Werte übereinstimmen.
In welcher Dimension befindet sich dein Problem?
-
Drei Dimensionen, wobei es eine gewisse Struktur gibt. Man kann sich das vorstellen wie bei einem Gebäude, wo Räume aneinander grenzen.