spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Wir lagern das mal in PMs aus. Wenn der endgültige Algorithmus gefunden wurde oder wir Hilfe brauchen, dann melden wir uns. Falls das wem nicht passt sagt bescheid!

Weil wirs versprochen haben: Das Programm ist samt einer schönen GUI fertiggestellt. Kurze Erklärung und das Projekt folgen nun:

Das Backend kann zu jeder bliebigen geschlossenen 5-Punkte-Kette die Fläche (in FE) bestimmen. Das Polygon, das dabei entsteht muss nicht einfachsein - die Kanten dürfen sich überschneiden. Weil man die Fläche eines solchen Polygons aber nicht direkt bestimmen kann, zerlegt das Programm jedes Polygon in ein ebenes einfaches Polygonnetz. Dazu werden die Kanten miteinander geschnitten um alle Überschneidungen zu eliminieren. Siehe SchnittpunkteBerechnen().

Nach diesem Schritt liegt das Netz in einem ungerichteten Graphen vor: Jeder Punkt hat einen eindeutigen Namen, eine Position und kennt die Namen seiner direkten Nachbarn (Nachfolger). Siehe KnotenPunkt.

Bei einer Kette aus 5 Punkten kann mithilfe der Schnittpunktanzahl eindeutig festgelegt werden, wie die resultierenden Flächen in diesem Netz liegen müssen. Das ist in Bild A zu sehen. Weil das Programm zu jedem Knoten im Graphen weiß, ob er ein Schnittpunkt ist oder ein Ausgangspunkt, lassen sich die markanten Punkte im Netz leicht finden. Aus diesen markanten Punkten können relativ leicht die Flächen bestimmt werden. Siehe FindeTeilflächen().

Bevor Jemand fragt: Als Schnittpunkt sieht das Programm nur Punkte an, die NICHT auf den Enden der Strecken liegen, die geschnitten werden. Dadurch wird vermieden, dass die Formen für dieselbe Schnittpunktanzahl mehrdeutig sind. Außerdem sind ungünstige Fälle aufgetreten, in denen SchnittpunkteBerechnen() in endloser Interation versinkt...

Der Code ist komplett selbst geschrieben und erdacht! Keine einzige Zeile wurde irgendwo abgeschrieben. Zu Präsentationszwecken ist das Programm heftig kommentiert - nicht wundern.

CeDoMain & Garzec wünschen viel Spaß beim Ausprobieren!

Einfach drei Dreicke und addieren, da ist eigentlich kein größeres Problem...

Die negativen Flaechen werden automatisch negative Zahlen. Haengt natuerlich von dir ab, ob dieser "Flaecheninhalt" der ist, den du willst.

Zitat von »TGGC«

Die negativen Flaechen werden automatisch negative Zahlen. Haengt natuerlich von dir ab, ob dieser "Flaecheninhalt" der ist, den du willst.

Ist er iirc nicht, genau das war einer der ersten Vorschläge hier...

Genau! Das Problem an dieser Strategie sind die Überschneidungen die auftreten können. Da bekommst du dann eine größere oder kleinere raus. Habe ich auch ausprobiert - klappt wirklich nicht.

Zitat von »CeDoMain«

Genau! Das Problem an dieser Strategie sind die Überschneidungen die auftreten können. Da bekommst du dann eine größere oder kleinere raus. Habe ich auch ausprobiert - klappt wirklich nicht.

Noe, die Ueberscheidungen sind eigentlich kein Problem. Da kommt dann genau das gleiche raus. Das Problem ist, das viele ihre Flaechen dann ploetzlich umdefinieren. Es ist dann auf einmal nicht mehr das 5gon gemeint, von dem die Flaeche zu bestimmen ist sondern irgeneine neue Figur die sich aus den alten Ecken und den neuen Schnittpunkten ergibt. Mathematisch gesehen ist das aber nicht sehr sinnvoll, denn man möchte eigentlich moeglichst viele Dinge logisch fortsetzen. Man kann es anders definieren, aber allgemein ist ein ngon ein n-1gon an das man noch ein Dreieck dranpappt. Die Flaeche eines Dreiecks kennt man, also definiert man die Flaeche eines ngons per Induktion aus Dreiecken. Das geht zum Beispiel auch für die Innenwinkelsumme. Daher macht es eigentlich keinen Sinn, die Definition ploetzlich zu wechseln. Oder Zum Beispiel ist von Dreiecken bekannt, das die Flaeche aller Dreiecke mit gleicher Grundseite und gleicher Hoehe darauf gleich ist und damit führt man den Flaecheninhalt alle Dreiecke auf rechtwinlige Dreiecke zurueck. Das laesst sich genau so auf ngone uebertragen und es funktioniert auch fuer Ueberschlagene, solange man dort eben nicht ploetzlich die Definition des Flaecheninhalts wechselt.

Zudem finde ich in dem Thread auch keine eindeutige Definition - angenommen ich habe ein nicht degeneriertes Dreieck ABC, und der Zufallsgenrator macht das 5gon ABCBC. Ist das Ergebnis jetzt 1x, 2x oder 3x wenn x der Flaecheninhalt von ABC ist? Laut dem ersten Post soll ja "jede Fläche, die durch die Schnittpunkte entsteht, [...] ausgegeben werden". Sind jetzt Punkte aufeinander Schnittpunkte? Die Strecken schneiden sich in unendlich vielen Punkten? Also unendlich viele Flaechen? Und die Flaechen, die ohne Schnittpunkte enstehen sollen ja eigentlich auch gezaehlt werden? Aber hier liegen die aufeinander, also mehrfach zaehlen?

Zitat von »TGGC«

Das Problem ist, das viele ihre Flaechen dann ploetzlich umdefinieren.

Das ist für dich vielleicht ein Problem, das mag sein. Garzec hat aber die Aufgabe gestellt bekommen die Innenfläche auszurechnen und nicht irgendwelche anderen Flächen. Und was soll man sich dann darüber aufregen, wie sinnvoll sowas ist. Es wird programmiert und schluss.

Zitat von »TGGC«

Zudem finde ich in dem Thread auch keine eindeutige Definition - angenommen ich habe ein nicht degeneriertes Dreieck ABC, und der Zufallsgenrator macht das 5gon ABCBC. Ist das Ergebnis jetzt 1x, 2x oder 3x wenn x der Flaecheninhalt von ABC ist? Laut dem ersten Post soll ja "jede Fläche, die durch die Schnittpunkte entsteht, [...] ausgegeben werden". Sind jetzt Punkte aufeinander Schnittpunkte? Die Strecken schneiden sich in unendlich vielen Punkten? Also unendlich viele Flaechen? Und die Flaechen, die ohne Schnittpunkte enstehen sollen ja eigentlich auch gezaehlt werden? Aber hier liegen die aufeinander, also mehrfach zaehlen?

Sorry, haben wir vielleicht nicht so ganz klargestellt: Es werden nur Flächen vorgegeben, deren 5 Punkte alle verschieden sind und nicht kollinear sind.

Hoffe jetzt ist die gewünschte Fläche und die Ausgangssituation eindeutig definiert. Habs leider nicht so mit den Fachbegriffen, weil ich sowas nie jemandem erklären muss und dann kann ich mir die nicht behalten.