Ich entwickle für die Universität Heidelberg eine 3D-Applikation, welche auf den Daten von OpenStreetMap basiert (sie wird nach Abschluss kostenlos im Netz zur Verfügung gestellt.)
Bei meiner Arbeit bin ich auf ein für mich großes Problem gestoßen: Wenn ich beispielsweise ein Gebäude darstellen möchte, dann verbinde ich die einzelnen Knoten der Gebäuderandkante aus der OSM-Datei zu einem Streckenzug und erhalte den Gebäuderand. Doch wie kann ich den Inhalt der Fläche färben?
Was ich gegeben habe, sind die Knoten aus der OSM-Datei, die verbunden den Gebäuderand ergeben. Außerdem habe ich eine Funktion, mit der ich bestimmen kann, ob ein Punkt innerhalb oder außerhalb eines Polygons ist und ich habe einen Zeichenalgorithmus, mit dem ich konvexe Fläche zeichnen kann. Nun sind aber leider die meisten Gebäude- oder Naturflächen konkav, weswegen ich die konkave Fläche in konvexe Teilflächen zerlegen möchte, damit ich diese darstellen kann.
Leider schlug bisher jede Idee von mir die konkave Fläche zu zerlegen fehl. Ich wäre unheimlich dankbar, wenn mir jemand helfen könnte. Ich brauche dies, um Dächer von Gebäuden oder Grünflächen darstellen zu können. Das Programm ist zwar 3D, aber da ich nur planare Flächen verwende, reicht es, wenn mir jemand für den zweidimensionalen Fall helfen könnte.
Warum zerlegst Du die Fläche nicht in Dreiecke? Das ist das “normale” Vorgehen. Aber die Lösung kommt mir so einfach vor, dass ich wahrscheinlich das Problem nicht völlig verstanden habe;)
Doch, das würde funktionieren, wenn ich wüsste, welche Dreiecke ich bräuchte, um die ganze Fläche mit Teilflächen (also Dreiecken) auszufüllen. Hast du dafür auch einen Vorschlag?
Das naive Vorgehen wäre, dass ich je drei Punkte eines Polygons zu einem Dreieck verbinde, wenn das Dreieck vollständig in der Fläche liegt. Klingt einfach und ist es an sich auch - aber das Programm ist danach nicht nutzbar, weil er sich zu Tode rechnet. Bei nur 100 Gebäuden mit je 20 Knotenpunkten wären das alleine 800.000 Dreiecke. Jede Überprüfung, ob ein Dreieck in der Fläche liegt benötigt schon 200 Rechenoperationen, also liegst du, wenn du 30 Bilder pro Sekunde darstellen willst mindestens 4.8 Milliarden Rechenoperationen pro Sekunde. Das ist zu uneffizient
Ein geschlossener Polygonzug mit den Punkten P1 … Pn läßt sich relativ leicht in Dreiecke aufteilen. Du beginnst am Anfang (logo;) und nimmst die ersten drei Punkte des Polygonzugs für das erste Dreieck, d.h. P1/P2/P3. Den ersten Punkt behältst Du bei, die anderen beiden “wandern” um das Polygon. Das nächste Dreieck wäre P1/P3/P4, dann P1/P4/P5 usw. Wenn Du das Dreieck P1/Pn-1/Pn gezeichnet hast, bist Du fertig. Ein Polygon mit n Ecken wird so in n-2 Dreiecke zerlegt.
Beim Zeichnen der Dreiecke musst Du etwas aufpassen, weil der Renderer die Kanten von zwei nebeneinanderliegenden Dreiecken so zeichnen muss, dass dazwischen keine Lücken entstehen. Das kann passieren, weil die Annäherung einer Gerade durch eine Menge an Pixeln nicht exakt ist. Aber dieses Problem würde ich erstmal ignorieren, ob es eins ist merkst Du früh genug:-)
Nun ist der Abend doch etwas fortgeschritten und ich weiß nicht, ob ich das Problem richtig verstanden habe:
In OSM ist die “Projektion” eines Gebäudes zu finden.
Von diesem (eigentlichen) Gebäude soll eine 3D-Darstellung angezeigt werden
Die Projektion wird zwar oftmals konkav sein (wenn das Gebäude viele (mehr als 3) Ecken hat)
Das Gebäude erhebt sich jedoch rechtwinklig zur Projektion (dieses Konstrukt ist also immer konvex !)
Ich definiere eine (fiktive) Gebäudehöhe
Nun lassen sich entweder Dreiecke (oder in diesem Fall sogar rechtwinklige Vierecke) über der Projektion mit der entsprechenden Höhe konstruieren (Wände).
Ausgehend vom Augenpunkt können nun die sichtbaren sowie die nicht sichtbaren Punkte in diesen Wänden ermittelt werden (hidden-lines)
Der Rest ist dann: Einfärben
Oder habe ich das Probleme ebenfalls (noch) nicht verstanden ?
Ich definiere mir eine Höhe für alle Gebäude und zwischen zwei aufeinander folgenden Punkte bilde ich ein Rechteck, das orthogonal zum Untergrund steht - also quasi Wände. Mein Problem ist das Zeichnen des Dachs.
Wenn ich einen Lösungsweg für das Zweidimensionale hätte, würde mir das reichen, da ich es für die 3D-Anwendung lediglich in der y-Koordinate verschieben müsste. Ich sehe aber momentan nicht, wie mir dein siebter Punkt bei meinem Problem helfen soll, mapdiger.
Es geht mir darum, wie ich den konkaven - zweidimensionalen! - Flächeninhalt mit konkaven Teilflächen definieren kann.
