Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Polygone in Dreiecke umwandeln

Polygone in Dreiecke umwandeln

Universität / Fachhochschule

Tags: Dreieck, Polygon

polygon aktiv_icon

23:58 Uhr, 13.06.2012

Hi!

Ich suche eine Mathe-Studenten für ein Programm, an dem ich momentan arbeite. Es geht um 3D-Programmierung. Ich programmiere momentan in JavaScript und möchte Objekte mittels WebGL dreidimensional darstellen.

Mein Problem ist, dass mir Daten als Polygone vorliegen können, die sich sowohl überkreuzen als auch Löcher haben können. Und ich weiß nicht, wie ich das programmieren könnte.

Darum suche ich einen Studenten von der UNI Wien, der mir bei der Lösung dieses Problems helfen könnte.

Ich hoffe, es meldet sich hier wer bei mir.

Christian

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Flächeninhalt und Umfang eines Dreiecks
Flächeninhalte
Winkelsumme

Zu diesem Thema passende Musteraufgaben einblenden

Photon aktiv_icon

21:19 Uhr, 14.06.2012

Ich bin zwar weder Mathe-Student, noch aus Wien, noch kann ich ordentlich programmieren, aber trotzdem eine Anmerkung: Was ist denn das Problem? Was soll mit den Polygonen geschehen, die sich überkreuzen? Sollen neue Koordinaten berechnet werden, sodass sie sich nicht mehr überkreuzen? Oder sollen sie so wie sie sind dargestellt werden? Und wie können Polygone Löcher haben, sind doch nur Streckenzüge?

polygon aktiv_icon

10:39 Uhr, 15.06.2012

Es geht um 3D-Programmierung. Ein Polygon definiert eine Fläche. Und so eine Fläche kann Löcher haben. Diese werden wiederum mittels Polygone definiert. Es gibt also ein äußeres Polygon, das die Fläche definiert und ev. innere Polygone, die die Löcher definieren.

Ich vermute, dass man einen neuen Punkt definieren muss, sofern sich Linien eines Polygons überkreuzen. Bei

2 D

ist das kein Problem. Wie das bei

3 D

ausschaut, weiß ich nicht. Hier spielt auch die Rechengenauigkeit eine Rolle. Vermutlich wird man die Distanzen zwischen den Linien berechnen müssen. Und ist eine Distanz unter einem gewissen Wert, gilt das dann vielleicht als "überkreuzen". Aber das ist nur geraten.

hagman aktiv_icon

10:59 Uhr, 17.06.2012

Sind deine Polynome denn "eigentlich" in einer Ebene (bis auf Rechengenauigkeit)?
Oder kann es sein, dass du auch das "Viereck" mit Ecken

(0 | 0 | 0), (1 | 0 | 0), (0 | 1 | 0), (0 | 0 | 1)

zeichnen möchtest?

Im ersteren Fall würde ich, wenn du die entsprechenden Fragestellungen in

2 D

ja schon zu beherrschen scheinst, alles auf die "Soll"-Ebene projizieren, dort behandeln und rückabbilden.
Sprich:
1. Bestimme einen gemeinsamen Normalvektor

n,

für den also

n \cdot x_{i}

(so gut wie) konstant ist
2. Bestimme zwei zu

n

orthogonale (Einheits?-)Vektoren

u

und

v

3. Projizieren entlang

n

auf die u-v-Ebene:

x_{i} \mapsto (x_{i} \cdot u, y_{i} \cdot v)

4. Löse dort dein Problem,

d . h

. bestimme die Indizes aller Ecken, die durch Diagonalen zu verbinden sind.
5. Verbinde die diesen Indizes entsprechenden Originalecken.

Das ganze Problem ist eigentlich "affin",

d . h

. es kommt eigentlich (sofern du nicht irgendwelche Nebenziele hast wie möglichst beinahe-gleichseitige Dreiecke) auf keinerlei Maßstab an.
Insofern muss weder

n

in Schritt 1 besonders senkrecht stehen, noch müssen

u, v

aufeinander senkrecht stehen oder gleich lang sein.
Daher schlage ich vor, 1. und 2. wie folgt zu ersetzen:
1. Bestimme Punkte

x_{i}, x_{j}

mit maximalem Abstand und setze

u = x_{i} - x_{j}

.
2. Bestimme Punkte

x_{k}, x_{l},

die

u \times (x_{k} - x_{l})

maximieren und setze

v = x_{k} - x_{l}

.

Die beiden Schritte bräuchten jeweils

O (n^{2})

und auch das lässt sich verbessern:
1. Bestimme Maximum und Minimum der

x -,

y-,z-Koordinaten. Von der Koordinate mit der größeten "Spannweite" wähle einen maximalen und einen minimalen Punkt

x_{i}

bzw.

x_{j}

und setze

u = x_{i} - x_{j}

.
2. Wie

1 .,

wobei jedoch die x-y-z-Koordinaten aller

x_{i} \times u

verwendet werden.
Das geht dann in

O (n)

polygon aktiv_icon

15:26 Uhr, 17.06.2012

Die Polygone müssen nicht plan sein. Sie können beliebiges Aussehen haben. Und es können 4ecke, 5ecke, 6ecke,

. .

. sein. Die Fläche kann konkav und konvex sein. Und Linien eines Polygons können sich überkreuzen. Also alles, was man sich vorstellen kann.

hagman aktiv_icon

16:07 Uhr, 17.06.2012

OK, nur was willst du denn dann darstellen?
Die zugehörigen Minimalflächen ("Seifenhäute")?

polygon aktiv_icon

08:47 Uhr, 18.06.2012

Ich will die Fläche, die die Polygone bilden, durch Dreiecke abbilden.

Es geht darum, dass ich COLLADA-Dateien parsen möchte. Das sind Dateien aus 3D-Rendering-Programmen. Sie sind im XML-Format. Es gibt dort ein polygon-XML-Element. Das beinhaltet die Daten für die Polygone. Die muss ich dann in Dreiecke umwandeln. Denn die Daten sollen dann WebGL übergeben werden können. Und WebGL kann nur mit Dreiecken umgehen.

hagman aktiv_icon

16:17 Uhr, 18.06.2012

Dadruch ist immer noch nicht klar, welche Ausgabe du erwartest, wenn ein Polygon (nicht nur wegen Rundungsfehlern) nicht planar ist.
Beispeil: Die vier Ecken

A, B, C, D

eines regulären Tetraeders als Viereck

A B C D

aufgefasst kann man wahlweise per

A C

oder per

B D

in zwei Dreiecke zerlegen. Mit sehr unterschiedlichen Ergebnissen!

polygon aktiv_icon

07:34 Uhr, 21.06.2012

AC wäre eine Linie, kein Dreieck.

Hat man ein Quadrat mit den Vertices ABCD, wären die Dreiecke

z

. B. ABC und CBD.

Das kann ich dann selbst entscheiden, wie die Dreiecke dann aussehen sollen. Wichtig ist nur, dass es wirklich Dreiecke sind. Und natürlich dürfen keine Flächen verschwinden oder hinzukommen. Die Flächen der Dreiecke müssen der Fläche des Polygons entsprechen.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1013377

1011739

	Status: nicht eingeloggt	Noch nicht registriert?