Komplexe Termumformung

Question

ich habe eine Berechnung für einen Algorithmus, den ich programmiere. Dabei nutze ich die Vektorrechnung um die Schnittpunkte von Geraden zu berechnen. Leider stimmt mein Rechenanfang anscheinend noch nicht. Das Ganze sieht so aus:

 // "x" von y = ax+b

            float faktor1;

            float faktor2;

            /*

            g = punkt1 + (punkt2-punkt1) * faktor1

            h = punkt3 + (punkt4-punkt3) * faktor2

            /// ------------------------------------------------------------------------------------------------------------------------

            gleichsetzen : punkt1 + (punkt2-punkt1) * faktor1 = punkt3 + (punkt4-punkt3) * faktor2

            /// ------------------------------------------------------------------------------------------------------------------------

            1. Gleichung:    punkt1.x + (punkt2.x-punkt1.x) * faktor1.x = punkt3.x + (punkt4.x-punkt3.x) * faktor2

| - punkt1.x

            (punkt2.x-punkt1.x) * faktor1.x = punkt3.x + (punkt4.x-punkt3.x) * faktor2 - punkt1.x

| / (punkt2.x-punkt1.x)

            faktor1 = (punkt3.x + (punkt4.x-punkt3.x) * faktor2 - punkt1.x) / (punkt2.x-punkt1.x)

            /// ------------------------------------------------------------------------------------------------------------------------

            2. Gleichung:    punkt1.y + (punkt2.y-punkt1.y) * faktor1 = punkt3.y + (punkt4.y-punkt3.y) * faktor2

            umformen:        p1.y - p3.y + f1 * (p2.y - p1.y ) = f2 * ( p4.y - p3.y )

            f1 einsetzen:    p1.y - p3.y +((p3.x-p1.x)+ f2(p4.x - p3.x )) / ( p2.x-p1.x)  * (p2.y - p1.y ) = f2 * ( p4.y - p3.y )

 | * (p2.x-p1.x)

                             (p1.y - p3.y)* ( p2.x-p1.x) + ( (p3.x-p1.x)+ f2(p4.x - p3.x ))  * (p2.y - p1.y ) = f2 * ( p4.y - p3.y )* ( p2.x-p1.x)

            umformen:        (p1.y - p3.y)* ( p2.x-p1.x) + ( (p3.x-p1.x)  * (p2.y - p1.y ) + f2(p4.x - p3.x ) * (p2.y - p1.y ) = f2 * ( p4.y - p3.y )* ( p2.x-p1.x)

| f auf eine Seite bringen

                             (p1.y - p3.y)* ( p2.x-p1.x) + ( (p3.x-p1.x)  * (p2.y - p1.y ) = f2 * ( p4.y - p3.y )* ( p2.x-p1.x) - f2(p4.x - p3.x ) * (p2.y - p1.y )

  | f ausklammern

                             (p1.y - p3.y)* ( p2.x-p1.x) + ( (p3.x-p1.x)  * (p2.y - p1.y )= f2 * ( ( p4.y - p3.y )* ( p2.x-p1.x) - (p4.x - p3.x ) * (p2.y - p1.y ) )        | / ( ( p4.y - p3.y )* ( p2.x-p1.x) - (p4.x - p3.x ) * (p2.y - p1.y ) )

            faktor2 =        ( (p1.y - p3.y)* ( p2.x-p1.x) + ( (p3.x-p1.x)  * (p2.y - p1.y ) ) / ( ( p4.y - p3.y )* ( p2.x-p1.x) -  (p4.x - p3.x ) * (p2.y - p1.y ) )

            */

            faktor2 = (punkt1.Y - punkt3.Y) * (punkt2.X - punkt1.X) + ((punkt3.X - punkt1.X) * (punkt2.Y - punkt1.Y)) / ((punkt4.Y - punkt3.Y) * (punkt2.X - punkt1.X) - (punkt4.X - punkt3.X) * (punkt2.Y - punkt1.Y));

            faktor1 = (punkt3.X + (punkt4.X - punkt3.X) * faktor2 - punkt1.X) / (punkt2.X - punkt1.X);

Es wäre cool, wenn jemand da mal gegenrechnen würde, da faktor1 und faktor2 bei mir sehr groß werden also zb faktor1 = 1481266 und dadurch die Prüfungen, wie die beiden Geraden liegen, natürlich fehlschlagen.

Comments

Mir würde es sehr helfen wenn du einmal einmal eine
Skizze einstellen würdest.
So werde ich aus den Angaben nicht schlau.

mfg Georg

---

Sorry, hier einmal meine Berechnung in "schöner". Ich hoffe man kann es ausreichend gut lesen. Das 2. Bild ist mein Programm. Ich versuche also die Schnittpunkte der Geraden zu berechnen. Um dann hinterher jede einzelne Teilfläche des zufällig generierten Polygons zu berechnen. Aber meine Frage deutet erst einmal nur auf die Berechnung zu faktor1 und faktor2 hin.

---

Du hast vor ein paar Wochen diese Frage schon einmal eingestellt ?

Deine Anfrage läßt sich in 2 Fragen teilen.
- Flächenberechnung eines geschlossenen Polygons
( Anfangspunkt = Endpunkt ) ohne Kreuzung von Linien
- falls Kreuzungspunkte vorliegen : Berechnung derselben
und damit Auifteilung 1 Polygons in 2 Polygone.

Die verwegenste Lösung ist :
Du zeichnest das Polygon auf den Bildschirm.
Als Bildgröße wählst du ( min_x -10, min_y - 10, max_x + 10, max_y + 10 )
Dann nimmst du einen Eckpunkt und füllst mit " Floodfill " ( in Pascal )
( 1,1,Farbe ) den Bildschirm Die Hintergrundfläche wird damit eingefärbt.

Dann liest du jeden Pixel des Bildschirms aus ob er den Wert " Farbe " hat.

Nun kannst du das Verhältnis ( gesamte Pxelanzahl ) / ( Farbpixel ) bilden
und mit ein paar Umrechnungen alle Flächen ( Hintergundfläche / Polygonfläche )
bestimmen.

Ich warte einmal deine Reaktion ab.

mfg Georg

---

Hier eine Skizze

---

Die Lösung ist leider nicht erlaubt, weil Pixelzählen keinen exakten Flächeninhalt liefert.

Ja, ich habe die Frage schonmal gestellt, die Lösung stimmt aber nicht, für faktor1 und faktor2 kommen riesige Zahlen heraus. Dadurch findet das Programm niemals Schnittpunkte, da nur ein Schnittpunkt auf der STRECKE, also nicht auf der Geraden, vorliegt, wenn

faktor1 >= 0 && faktor1 <= 1 && faktor2 >= 0 && faktor2 <= 1

ist. Und das wird bei den Werten natürlich nie passieren. Also bei jeglichen Versuchen sind die Faktoren im Tausenderbereich.

---

Und 2. muss der Algorithmus jeden Flächeninhalt zu JEDER entstandenen Teilfläche liefern. Dafür brauche ich die Schnittpunkte. Bei einem Pentagramm zb habe ich ja viele einzelne Teilflächen die berechnet werden müssen.

Answer 1

Hier einmal der Algorithmus für Polygone deren Linien
sich nicht schneiden.

Die ermittelte Summe sollte zur Sicherheit immer in Betragsstriche gesetzt werden.

Ob der Algorithmus auch für Polygone mit sich schneidenen Linein
gilt weiß ich nicht.
ich würde dies an deiner Stelle auch einmal ausprobieren.
Dies wäre wesentlich einfacher als Schnittpunkte zu berechnen.

Comments

Schnittpunkt.
1 Gerade zwischen Punkt A und B
2 Gerade zwischen Punkt C und D

Geradengleichungen aufstellen

f1 ( x ) = m1 * x + b1
f2 ( x ) = m2 * x + b2

Schnittpunkt
f1 ( x ) = f2 ( x )

Es gibt Ausnahmen
Die Geraden verlaufen parallel
am schlimmsten : 2 senkrechte Geraden

Ansonsten
S ( xs | ys )

Und dann mußt du nachsehen
ob der Kreuzungspunkt S  wirklich
zwischen (AB) (CD) liegt.
Dann ist es ein echter Schnittpunkt.

Ich habe so etwas schon einmal gemacht.
Viel Spaß.

---

Danke für den Ansatz, aber dieser funktioniert leider nicht, da man ja zwischen den ganzen Polygonarten unterscheiden muss.

Die Berechnung habe ich vereinfacht, indem ich mir für die ganzen Punkte variablen genommen habe, das macht es übersichtlicher.