Liebe Entwickler,
ich habe eine große Anzahl von Linien. Zusammen ergeben sie ein Netz. Nun möchte ich wissen, welche Linien eine Teilfläche beschreiben.
Normalerweise würde ich dieses als Architekt von Hand in einem 3D-Programm(Rhino3D oder AutoCad) machen. Das dauert mir aber zu lange und das Netzt ändert sich häufig. Auf dem Bild ist nur ein Beispiel zu sehen. Es hat 3- und 5-Ecke, bei anderen Problemen gibt es unterschiedlichste Flächen.
In Rhino3D gibt es die Möglichkeit C# zu nutzen, um diesen Prozess zu beschleunigen. Da das Arbeiten im Code für mich eher neu ist und ich keine Ahnung zu den Begrifflichkeiten habe, fällt mir natürlich auch die Suche nicht einfach.
Kennt jemand ein paar Stichworte, die das Problem eingrenzen oder eventuell einen Algorithmus?

Vielen Dank
caja22

Ich meine hier fehlen einfach sämtliche Vorgaben.
Wie liegen die Daten vor? Ich vermute einmal, das angehängte Bild wurde anhand von Linien gezeichnet, wobei jede Linie durch eine Anzahl Punkte definiert wurde?

Wie soll nun "Teilfläche" definiert werden?
Für unsere Augen ist es relativ einfach, in dem beigefügten Bild intuitiv Teilflächen zu erkennen, ein Programm müßte eine genaue Definition haben, was eine Teilfläche ist.
Denn unsere Augen identifizieren erst einmal die scheinbaren Schnittpunkte der Linien als Eckpunkte einer Fläche.
(Wobei ich nun nicht weiß, ob sich die Linien (im 3D) wirklich schneiden oder nur nahe aneinander vorbeigehen... nächstes Problem)

Aus dem Bauch heraus würde ich eine Teilfläche wie folgt definieren:
- Eine Teilfläche wird aufgespannt durch ein Polygon dessen Eckpunkte alle Schnittpunkte von Linien enthält
- weiterhin darf das Polygon im inneren keine weiteren Schnittpunkte von Linien enthalten.

Dies ist natürlich ein primitiver, aufgrund der Menge möglicher Kombinationen kaum realisierbarer, Ansatz.

Vor allem: Ob in einem Polygon ein Punkt liegt läßt sich hier nicht sinnvoll feststellen, da die Polygone nicht eben sind, sie bestehen wie es aussieht ja aus der Umrandung gekrümmter Flächen.
Außerdem ist bei diesem Vorgehen die Reihenfolge der Eckpunkte nicht klar.
Das im Beispielbild markierte Sechseck könnte bei anderer Reihenfolge der Eckpunkte z.B. einen Stern ergeben.

Ich interpretiere das völlig anders

IMHO hat der TE eine CAD-Software, mit der er/sie diese Grafiken erstellt. Das CAD-Programm bietet eine Art Makrosprache in Form von C# an, vergleichbar mit VBA in Excel/Word/Access. Und so, wie man in Excel komplexe Probleme in VBA löst, weil Excel selbst gar keine Lösung anzubieten hat, möchte der TE eben sein Problem in C# lösen. Und sein problem ist, die Linien herauszufinden, die die markierte Fläche bilden.

Ich denke, das eigentliche Problem wird sein, jemanden zu finden, der sich mit dem 3D-Programm überhaupt auskennt und grob eine Marschrichtung vorgeben kann.

Typischerweise gibt es die Möglichkeit, die Daten zu exportieren (z.B. als Wavefront .obj). Damit hätte man erstmal die lästige Fixierung auf C# und dem konkreten CAD-Programm aus dem Weg geräumt.

Dann stellt sich natürlich, wie schon gesagt wurde, die zentrale Frage, wie die Daten vorliegen. Ein CAD-Programm sollte präzise sein und die Schnittpunkte als Punkte der Linie im Idealfall im Export schon entsprechend definieren. Allerdings nur im Idealfall. Ansonsten müsste man erstmal alle Schnittpunkte berechnen (Problem 1 - ein dummer BruteForce-Algorithmus wäre wohl zu langsam). Das geht allerdings wohl erstmal nicht so ohne weiteres, da die Linien sich in dem Fall vermutlich nicht wirklich schneiden (Problem 2 - Schnittpunkte von Linien mit gewisser Unschärfe versehen). Wenn es überhaupt Linien sind, und nicht irgendwelche Kurven oder so fieser Kram .

Wenn man die Schnittpunkte hat, kann man sich einen Graph aufbauen (Problem 3 - sollte einfach sein).

Anhand des Graphen kann man dann alle Flächen bestimmen (Problem 4 - einen effizienten Algorithmus müsste man sich überlegen, evtl. problematisch bei Flächen mit vielen Eckpunkten...irgendwas in Richtung Tiefensuche vermutlich)

Interessant wäre auch das Ziel des ganzen, vielleicht kann man dieses auch ganz anders und viel einfacher erreichen

Vielen Dank für die Antworten.
Damit das große Ziel klar ist, möchte ich diese Seite empfehlen:
www.tragwerk-arch.un...ialien/tarantel.html
Wir haben das Tool "Tarantel" auf der Basis von Processing -Simple Java- für Architekten entwicklet. Es handlet sich um ein erweitertes Masse-Feder-System. de.wikipedia.org/wik...%28Computergrafik%29
Wir können die Strukturen als DXF importieten, verändern und später auch exportieren. Leider handelt es sich immer um Stäbe/Linien/Träger, da die Berechnung auf Knoten und deren Verbindungen basiert. Die Flächen benötigen wir hauptsächlich für Renderings, später aber auch für Parameter, die sich aus der Größe, der Krümmung , der Ausrichutng usw. ableiten könnten.

Wir könnten natürlich die Ausgangsstruktur als Fläche importieren und sie dann im Programm unterteilen. Für die Tragstruktur und hauptsächlich für das Entwerfen ist genau dieser Punkt interessant, daher wollen wir diesen von Hand machen.

Wir haben das ganze Projekt in Processing gestartet, da wir aber bei der täglichen Arbeit ein vollwertiges CAD-Programm benötigen, scheint uns die Implementierung in die Rhino/Grashopper Umgebung sehr interessat und wichtig. Im Moment arbeite ich an dieser Überführung.

Zurück zum Detail.
Es handelt sich also um 2D Netze, die im 3D verformt werden. Die Daten liegen im Moment in einem verschachtelten Klassensystem vor(Java - Processing). System / Kräfte/ Stäbe/ Knoten/ GUI....
Aus der Erfahrung könnte ich sagen, dass bis jetzt kaum/nie Teilflächen mit mehr als 8 Punkten aufgetreten sind. Das könnte ich also eingrenzen.

Ich werde mal mit dem Stichwort "Tiefensuche" starten.
Nochmals vielen Dank

caja22 hat folgendes geschrieben :

Ich werde mal mit dem Stichwort "Tiefensuche" starten.

Tiefensuche ist ein einfacher Algorithmus für die Suche von Kreisen in Graphen, ein Graph sind einfach nur Knoten und Kanten, also das erste, woran ich denke, wenn die Rede von einem "Netz" oder "Knoten und Verbindungen" die Rede ist.
Eine Fläche ist immer auch ein Kreis in dem Graphen.
Die Betrachtung der Flächen in solchen Graphen ist z.B. bei dem Vier-Farben-Satz von Bedeutung. Der Graph dort ist aber planar. Das wäre aber auf jeden Fall meine grobe Marschrichtung.

caja22 hat folgendes geschrieben :

Es handelt sich also um 2D Netze, die im 3D verformt werden.

Sollten die Flächen des 2D-Netzes nicht unverändert bleiben bei der Verformung (im Bezug auf die umgebenden Punkte) (d.h. es werden nicht mehr oder weniger Flächen, sie verformen sich nur)? Dann könnte man die Flächen im 2D-Netz bestimmen (einfachere Problemstellung vermutlich), die entsprechenden Eckpunkte speichern und später, zum Rendering, einfach die Koordinaten der "verformten" Eckpunkte als Fläche interpretieren und darstellen?

Ich habe mir die Demos zu Tarantel einmal angesehen.
Da die Transformation vom 3D-"Stabtragwerk" ins zweidimensionale nicht reversibel ist*), bleibt m.E. nach nur folgender Weg:

- Finde die Teilflächen im 3D-dafür gibt es Algorithmen, einer wäre:
0. Für alle Punkte:
1. Nimm einen Punkt, gehe von diesem ausgehend die Kanten immer in gleicher Richtung entlang bis man wieder bei diesem Punkt angelangt ist. (gleiche Richtung: im/gegen Uhrzeigersinn auf der so aufgespannten als planar angesehenen Polygonfläche).
2. Wenn diese Fläche noch nicht in der Ergebnismenge enthalten ist, füge sie dieser zu, evtl. mit zusätzlichen Operationen wie der Überführung in die 2D-Ansicht sowie ggf. zusätzlichen Parametern.

*) Sie ist nicht reversibel, da das 3D-Stabtragwerk üblicherweise keine Durchdringungen aufweist, die Projektion ins 2D durchaus, wie man an der beigefügten Beispielgrafik sehen kann