Berechnung von Schnittpunkten auf 2 Geraden des Polygons

Garzec · Beiträge: 29

Hallo

ich versuche den Schnittpunkt von zwei Geraden zu berechnen. Benötigen tue ich das für eine Berechnung einer Fläche eines zufällig generierten Polygons. Mir geht es hierbei aber erstmal nur um die Schnittpunktberechnung. Momentan sieht diese so aus:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:

private void SchnittpunktBerechnung(int startIndex1, int startIndex2)
        {
            //Strecke AB = Punkt1 + s * (Punkt2 - Punkt1)
            //Strecke CD = Punkt3 + t * (Punkt4 - Punkt3)

            int endeIndex1 = startIndex1 + 1;
            int endeIndex2 = startIndex2 + 1;

            Point start1 = punktListe[startIndex1];
            Point ende1 = punktListe[endeIndex1];
            Point start2 = punktListe[startIndex2];
            Point ende2 = punktListe[endeIndex2];

            // Streckenfarben

            Color farbe1 = farbenListe[startIndex1];
            Color farbe2 = farbenListe[startIndex2];

            // Punkte

            int x1 = start1.X;      //Punkt1 X
            int x2 = ende1.X;       //Punkt2 X
            int x3 = start2.X;      //Punkt3 X
            int x4 = ende2.X;       //Punkt4 X

            int y1 = start1.Y;      //Punkt1 Y
            int y2 = ende1.Y;       //Punkt2 Y
            int y3 = start2.Y;      //Punkt3 Y
            int y4 = ende2.Y;       //Punkt4 Y

            // Konstanten

            int mx = x2 - x1;
            int nx = x3 - x4;  //x4 - x3;
            int ox = x3 - x4;  //x3 - x1;

            int my = y2 - y1;
            int ny = y3 - y4;  //y4 - y3;
            int oy = y3 - y4;  //y3 - y1;

            // Determinanten

            int d1 = mx * ny - my * nx;
            int d2 = ox * ny - oy * nx;
            int d3 = mx * oy - my * ox;

            // Fallunterscheidung

            if (d1 == d2 && d1 == d3 && d1 == 0)
            {
                Console.WriteLine("Strecken liegen aufeinander");    //------- TEST
            }
            else if (d1 == 0 && d2 != 0 && d3 != 0)
            {
                Console.WriteLine("kein Schnittpunkt");    //------- TEST
            }
            else if (d1 != 0)
            {
                Console.WriteLine("Schnittpunkt");    //------- TEST
            }

            // s und t

            double s = 1F * d2 / d1;
            double t = 1F * d3 / d1;

            // Überprüfung s und t

            Console.WriteLine("Strecke: " + farbe1 + "Strecke: " + farbe2);    //------- TEST

            if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
            {
                Console.WriteLine("Schnittpunkt auf den Strecken");    //------- TEST
            }
            else
            {
                Console.WriteLine("Schnittpunkt auf den Geraden aber nicht auf den Strecken");    //------- TEST
            }

            // Schnittpunktberechnung

            int sx = Round(x1 + s * (x2 - x1));
            int sy = Round(y1 + s * (y2 - y1));

            // Schnittpunkt

            Point schnittPunkt = new Point(sx, sy);

            Console.WriteLine(schnittPunkt);    //------- TEST

            Console.WriteLine("s: " + s + " t: " + t);

            Console.WriteLine("************************************************************");    //------- TEST
        }

Das Problem an der Sache ist, das bei meiner Testroutine immer s=0 und t=1 ist. Und das Problem liegt wohl oben bei den Konstanten. Rechts auskommentiert habe ich meine vorherige Berechnung, diese stimmte aber auch nicht ganz. Kennt ein Mathe-Ass die richtige Rechnung?

Moderiert von Christian S.: C#-Tags hinzugefügt
Moderiert von Christian S.: Topic aus C# - Die Sprache verschoben am Mo 02.05.2016 um 10:50

Blup · Beiträge: 173 Erhaltene Danke: 43

Hab hier grad nur Delphi, aber zumindest stimmen (hoffentlich) die Ergebnisse:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:

type
  TFloatPoint = record
    x, y: Extended;
  end;

procedure Swap(var A, B: Extended);
var
  C: Extended;
begin
  C := A;
  A := B;
  B := C;
end;

function IsBetween(AValue, A, B: Extended): Boolean;
begin
  if A > B then
    Swap(A, B);

  Result := (A <= AValue) and (AValue <= B);
end;

function IsPointBetween(S, P1, P2: TFloatPoint): Boolean;
begin
  Result := IsBetween(S.x, P1.x, P2.x) and IsBetween(S.y, P1.y, P2.y);
end;

function Schnittpunkt(P1, P2, P3, P4: TFloatPoint; out S: TFloatPoint): Boolean;
var
  mx, nx, ox, my, ny, oy, d1, d2, d3: Extended;
begin
  mx := P2.x - P1.x;
  nx := P4.x - P3.x;
  ox := P4.x * P3.y - P3.x * P4.y;

  my := P2.y - P1.y;
  ny := P4.y - P3.y;
  oy := P2.x * P1.y - P1.x * P2.y;

  d1 := mx * ny - my * nx;
  d2 := nx * oy - mx * ox;
  d3 := ny * oy - my * ox;

  if d1 = 0 then
  begin
    // Strecken sind parallel
    S.x := 0;
    S.y := 0;
    Result := False;
  end
  else
  begin
    S.x := d2 / d1;
    S.y := d3 / d1;
    Result := IsPointBetween(S, P1, P2) and IsPointBetween(S, P3, P4);
  end;
end;

Th69 · Verfasst: Mo 02.05.16 18:09

Hallo und

bitte Crossposts immer verlinken: myCSharp - Berechnung von Schnittpunkten auf 2 Geraden des Polygons

Garzec · Beiträge: 29

Danke für die Hilfe,

wenn ich jetzt nur Delphi komplett verstehen würde

Wieso werden da per "Swap" Punkte getauscht?

Und wieso rechnest du bei ox und oy etwas anderes? Also 1. anders wie meins und 2. auch noch bei beiden etwas unterschiedliches =?

Und dein else-Fall sagt mir nicht so recht etwas

, ich denke S.y soll die y-Koordinate des Schnittpunktes darstellen, bei der Ausgabe wird S.y aber nie verwendet, sondern nur x-Koordinaten. Ist das so richtig =?

Blup · Beiträge: 173 Erhaltene Danke: 43

Garzec hat folgendes geschrieben :

Wieso werden da per "Swap" Punkte getauscht?

P1 kann links oder rechts von P2 liegen. Abhängig davon gilt für einen Punkt der auf der Strecke liegt:
(P1.x <= S.x <= P2.x) oder (P2.x <= S.x <= P1.x)
Das Swap tauscht hier nur die X-Werte. Das vereinfacht den nachfolgenden Vergleich, ob der Schnittpunkt der Geraden noch innerhalb der Strecke liegt.

Garzec hat folgendes geschrieben :

Und wieso rechnest du bei ox und oy etwas anderes? Also 1. anders wie meins und 2. auch noch bei beiden etwas unterschiedliches =?

Vieleicht hätte ich den Variablen andere Namen geben sollen, das sind einfach nur Zwischenergebnisse zur Berechnung des Schnittpunkts zweier Geraden.

de.wikipedia.org/wiki/Schnittpunkt

Garzec hat folgendes geschrieben :

Und dein else-Fall sagt mir nicht so recht etwas

, ich denke S.y soll die y-Koordinate des Schnittpunktes darstellen, bei der Ausgabe wird S.y aber nie verwendet, sondern nur x-Koordinaten. Ist das so richtig =?

S.x enthält die x-Koordinate und S.y die y-Koordinate, S ist mit "out" als zusätzlicher Rückgabewert vereinbart.
S ist damit eine Referenz auf eine Variable außerhalb der Funktion, ich hätte S ohne "out" auch als Pointer auf eine Variablen dieses Typs vereinbaren können.
"out" ermöglicht dem Compiler aber eine Prüfung des Codes, ob die Variable auch richtig verwendet wird.
Der eigentliche Rückgabewert heißt immer "Result" und ist hier vom Typ Boolean. Liegt der Schnittpunkt der Geraden innerhalb beider Strecken, ist das Ergebnis "True".
Ich habe den Vergleich jetzt noch auf die Y-Koordinaten erweitert, für den Sonderfall das eine Strecke genau senkrecht verläuft.

Garzec · Beiträge: 29

Danke für die Erklärungen. Meine Frage bei ox und oy war eigentlich nur wieso du bei ox "was anderes" rechnest als bei oy. Oben rechnest du

ox := P4.x * P3.y - P3.x * P4.y;

und unten

oy := P2.x * P1.y - P1.x * P2.y;

Daher einfach nur meine Frage ob das so passt.

Weil die anderen Rechnungen sind ja gleich, nur das sich x und y unterscheiden. Hast du deinen Code mal testen können? Meiner wird nämlich wohl falsch sein aber bevor ich alles umwerfe wollte ich dich fragen, ob dein Code wahrscheinlich zum richtigen Ergebnis führt

Blup · Beiträge: 173 Erhaltene Danke: 43

Im Anhang eine Testanwendung.

Einloggen, um Attachments anzusehen!

Garzec · Beiträge: 29

Ja sehr cool! Vielen Dank

Dann muss ich deinen Code nur noch in C# übersetzen.

Kleine Frage, habe den Code jetzt in C# übersetzt, kann deine Rechnung auch mit den ganzen Sonderfällen umgehen? Z.B. Senkrechte etc. ?

mandras · Verfasst: Mi 04.05.16 00:03

> Z.B. Senkrechte etc.

Du meinst wahrscheinlich Parallele. Ist entspr. im Kommentar des Quelltextes. Aber:
Aus eigener Erfahrung sollte man das "= 0" ersetzen durch: "abs < ...."
also eine Betragsschwelle für die Erkennung einer Null-Determinante einbauen, da bei derartigen
Berechnungen eine Determinante wirklich sehr selten ganz zu Null wird ("Rundungseffekte")

Garzec · Beiträge: 29

Sorry wenn ich mich falsch ausgedrückt hatte. Aber ich meinte wirklich die Prüfung ob eine Gerade senkrecht zu einer anderen steht, das war ja auch ein Sonderfall. Bei der Parallelen würden sie sich ja nie schneiden, was sie ja bei einer Senkrechten einmal tun.

Also ich habe nun 2 Berechnungen, wobei ich weiß das die 2. Berechnung wohl das richtige Ergebnis liefert, die 1. Methode (meine Berechnung) noch nicht.

Meine Berechnung sieht momentan so aus:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:

        private void SchnittpunktBerechnung(int startIndex1, int startIndex2)
        {
            // Punktindex

            int endeIndex1 = startIndex1 + 1;
            int endeIndex2 = startIndex2 + 1;

            Point start1 = punktListe[startIndex1];
            Point ende1 = punktListe[endeIndex1];
            Point start2 = punktListe[startIndex2];
            Point ende2 = punktListe[endeIndex2];

            // Zwischenwerte

            int x1 = ende1.X - start1.X;
            int x2 = start2.X - ende2.X;
            int x3 = start2.X - start1.X;

            int y1 = ende1.Y - start1.Y;
            int y2 = start2.Y - ende2.Y;
            int y3 = start2.Y - start1.Y;

            // Determinanten

            decimal d1 = x1 * y2 - y1 * x2;
            decimal d2 = x3 * y2 - y3 * x2;
            decimal d3 = x1 * y3 - y1 * x3;

            // s und t

            decimal s = d2 / d1;
            decimal t = d3 / d1;

            // Schnittpunktberechnung

            decimal schnittpunktX = start1.X + s * x1;
            decimal schnittpunktY = start1.Y + s * y1;

            // Überprüfung

            if (s >= 0 && t >= 0 && s <= 1 && t <= 1)
            {
                //Schnittpunkt auf der Strecke
            }
        }

Die neue Berechnung sieht wie folgt aus:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:

        private void Tausche(float start, float ende)
        {
            float helper;
            helper = start;
            start = ende;
            ende = helper;
        }

        private bool LiegtDazwischen(float value, float start, float ende)
        {
            if (start > ende)
            {
                Tausche(start, ende);
            }
            return (start <= value) && (value <= ende);
        }

        private bool PunktLiegtDazwischen(PointF schnittpunkt, PointF punkt1, PointF punkt2)
        {
            return LiegtDazwischen(schnittpunkt.X, punkt1.X, punkt2.X) && LiegtDazwischen(schnittpunkt.Y, punkt1.Y, punkt2.Y);
        }

        private bool BerechneSchnittpunkt(PointF punkt1, PointF punkt2, PointF punkt3, PointF punkt4, PointF schnittpunkt)
        {
            float mx = punkt2.X - punkt1.X;
            float nx = punkt4.X - punkt3.X;
            float ox = punkt4.X * punkt3.Y - punkt3.X * punkt4.Y;

            float my = punkt2.Y - punkt1.Y;
            float ny = punkt4.Y - punkt3.Y;
            float oy = punkt2.X * punkt1.Y - punkt1.X * punkt2.Y;

            float d1 = mx * ny - my * nx;
            float d2 = nx * oy - mx * ox;
            float d3 = ny * oy - my * ox;

            if (d1 == 0)
            {
                //parallel
                schnittpunkt.X = 0;
                schnittpunkt.Y = 0;
                return false;
            }
            else
            {
                schnittpunkt.X = d2 / d1;
                schnittpunkt.Y = d3 / d1;
                return PunktLiegtDazwischen(schnittpunkt, punkt1, punkt2) && PunktLiegtDazwischen(schnittpunkt, punkt3, punkt4);
            }
        }

Aufgerufen wird meine Methode über eine Schleife, die dann über sämtliche Punkte geht:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

  private void BerechneSchnittpunkte()
        {
            for (int i = 0; i < 5; i++)
            {
                for (int j = i + 2; j < 5; j++)
                {
                    SchnittpunktBerechnung(i, j);
                }
            }
        }

Würde es Sinn machen das Ganze hin zur 2. Berechnung umzubauen? Wenn ich versuche die 2. Berechnung mit 4 Methoden so abzuändern, dass diese Methode genauso wie meine Berechnung in der Schleife aufgerufen wird, dann komme ich als Anfänger sehr schnell mit den Parametern durcheinander, sodass es vorne und hinten nicht mehr stimmt.

Kann ich auch meine eigene Berechnung dahingehend abändern, dass die Methoden der 2. Berechnung greifen?

Blup · Beiträge: 173 Erhaltene Danke: 43

Die Parameterübergabe scheint mir noch nicht richtig deklariert zu sein:

markieren

C#-Quelltext

1:
2:
3:

private void Tausche(ref float start, ref float ende)

private bool BerechneSchnittpunkt(PointF punkt1, PointF punkt2, PointF punkt3, PointF punkt4, out PointF schnittpunkt)

Mir ist nicht klar was die Methode "BerechneSchnittpunkte()" überhaupt machen soll.
Vieleicht hilft dieser Ansatz:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

PointF start1 = punktListe[i];
PointF ende1  = punktListe[i + 1];
PointF start2 = punktListe[j];
PointF ende2  = punktListe[j + 1];
PointF schnittpunkt;

if (SchnittpunktBerechnung(start1, ende1, start2, ende2, schnittpunkt))
{

}
else
{

}

Moderiert von Th69: Code- durch C#-Tags ersetzt

Garzec · Beiträge: 29

Die Methode bzw. Schleife geht einmal über alle Punkte und berechnet so die Schnittpunkte von Punkt zu Punkt.

Meinst du mit

markieren

C#-Quelltext

1:
2:

S.x := d2 / d1;
S.y := d3 / d1;

eigentlich schon die Koordinaten für den Schnittpunkt? Oder fehlt die Berechnung noch? Weil ich rechne ja dann noch

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

decimal s = d2 / d1;
decimal t = d3 / d1;

// Schnittpunktberechnung

decimal schnittpunktX = start1.X + s * x1;
decimal schnittpunktY = start1.Y + s * y1;

// Überprüfung

if (s >= 0 && t >= 0 && s <= 1 && t <= 1)
{
    //Schnittpunkt auf der Strecke
}

Hat sich geklärt

Moderiert von Th69: Beitragsformatierung überarbeitet.

Garzec · Beiträge: 29

@Blup

Kannst du mir noch verraten, ob deine Berechnung auch mit den Sonderfällen umgehen kann =?

Wenn zb eine Gerade senkrecht verläuft?

mandras · Verfasst: Mo 09.05.16 14:10

Du weist mehrfach auf senkrechte Geraden hin - warum sind die so wichtig bzw. ein Sonderfall?
Für mich sind Parallele Sonderfälle, da hier Determinanten Null werden...

Garzec · Beiträge: 29

Senkrechte Geraden sind nicht explizit wichtig, ich dachte nur es sei wichtig bei den Berechnungen sämtliche Fälle abzudecken, bevor falsche Ergebnisse entstehen.

Ich nutze nun die "neue" Berechnung, und versuche die 5 Parameter bei Methodenaufruf zu übergeben. Leider kommt es da zu Fehlern. Der Code:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

            for (int i = 0; i < punktListe.Count; i++)
            {
                for (int j = i + 2; j < 5; j++)
                {
                    PointF schnittpunkt = new PointF();
                    BerechneSchnittpunkt(punktListe[i], punktListe[j], punktListe[i + 1], punktListe[j +       1], out schnittpunkt);
                }
            }

Ich habe 2 Schleifen genommen, da er eine Exception bei einer Schleife wirft. Der Index übersteigt das Maximum und es geht nicht weiter. Dennoch kommen bei dieser Methode noch falsche Schnittpunkte heraus, meistens sind es sogar zu viele, ich denke er erkennt manche Eckpunkte noch als Schnittpunkte.

Meine Frage:

Stimmt meine neue Berechnung immer noch nicht oder übergebe ich die Parameter einfach nur falsch?

Ich habe zum Testen eine Schnittpunktliste erstellt, lasse ich die Schnittpunkte dazu malen, gehen die Linien kreuz und quer durch das Bild, die Berechnung muss also noch falsch sein ...

Edit: Ich habs jetzt erstmal so gelöst

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

            PointF schnittpunkt = new PointF();
            if (BerechneSchnittpunkt(punktListe[0], punktListe[1], punktListe[2], punktListe[3], out schnittpunkt))
                Console.WriteLine(schnittpunkt);
            if (BerechneSchnittpunkt(punktListe[1], punktListe[2], punktListe[3], punktListe[4], out schnittpunkt))
                Console.WriteLine(schnittpunkt);
            if (BerechneSchnittpunkt(punktListe[2], punktListe[3], punktListe[4], punktListe[5], out schnittpunkt))
                Console.WriteLine(schnittpunkt);
            if (BerechneSchnittpunkt(punktListe[3], punktListe[4], punktListe[5], punktListe[0], out schnittpunkt))
                Console.WriteLine(schnittpunkt);
            if (BerechneSchnittpunkt(punktListe[4], punktListe[5], punktListe[0], punktListe[1], out schnittpunkt))
                Console.WriteLine(schnittpunkt);
            if (BerechneSchnittpunkt(punktListe[5], punktListe[0], punktListe[1], punktListe[2], out schnittpunkt))
                Console.WriteLine(schnittpunkt);

Blup · Beiträge: 173 Erhaltene Danke: 43

Natürlich werden auch senkrechte Geraden berücksichtigt. Deshalb wird bei den Schnittpunkten der Geraden nicht nur geprüft ob der Schnittpunkt im X-Bereich der Strecke liegt, sondern zusätzlich auch der Y-Bereich.

"Index übersteigt das Maximum" sagt doch schon alles.
Die Variable "i" verweist nacheinander auf alle Punkte deiner Liste.
Wenn "i" auf den letzten Punkt verweist, worauf verweist "i + 1" ?
Bei der innere Schleife mit j kann natürlich das selbe Problem auftauchen, ich weis nicht wie gross die Punkteliste tatsächlich ist.

Wenn zwei Strecken einen gemeinsamen Endpunkt haben, dann ist das natürlich auch der Schnittpunkt.

Du wertest das Ergebnis der Funktion in deinem Code nirgends aus.
Das Ergebnis ist vom Typ Boolean und sagt aus, ob ein Schnittpunkt ermittelt werden konnte.
Nur dann enthält der Rückgabewert "Schnittpunkt" einen gültigen Wert.

Mir ist nicht klar welche Beziehung die Punkte in deiner Liste untereinander haben.
In deinem ursprünglichen Code hies es:

markieren

Quelltext

1:
2:
3:
4:

            Point start1 = punktListe[startIndex1];
            Point ende1  = punktListe[endeIndex1];
            Point start2 = punktListe[startIndex2];
            Point ende2  = punktListe[endeIndex2];

Jetzt übergibst du als Parameter:

markieren

Quelltext

1:
2:
3:
4:

            Point start1 = punktListe[startIndex1]; // i
            Point ende1  = punktListe[startIndex2]; // j
            Point start2 = punktListe[endeIndex1];  // i + 1
            Point ende2  = punktListe[endeIndex2];  // j + 1

Was willst du mit diesen beiden Schleifen eigentlich erreichen oder ermitteln?
Vieleicht kannst du das erst mal beschreiben, so ergibt der Code keinen Sinn.

mandras · Verfasst: Mo 09.05.16 22:01

Warum so kompliziert mit dem PointBetween und dem Swap?

Zur Schnittpunktberechnung werden die Strecken in "PunktRichtungs"-Form (oder wie auch immer das in
der Schule vor Zig Jahren genannt wurde - Parameterdarstellung?) betrachtet, also:
S = P1+a*(P2-P1), wobei a dann ja im Bereich 0 bis einschl. 1 sein muß.
Wenn das Gleichungssystem mittels Determinanten gelöst wurde haben wir ein "a1" für Strecke 1 und ein "a2" für Strecke 2.

Wenn a1 und a2 gleichzeitig im Bereich [0 bis 1] sind haben die Strecken einen Schnittpunkt.
Da muß man die konkreten Koordinaten nicht mehr betrachten.

Sonderfälle sind ja nur:
a) Nennerdeterminante wird 0, Zählerdeterminanten ungleich Null: Strecken sind parallel
b) Nennerdet. 0, Zählerdet. auch 0 - Strecken (als Geraden) sind deckungsgleich
c) Alle Determinanten ungleich 0, aber das a1 und/oder a2 liegt nicht im Bereich [0 bis 1]. Folge: als "Geraden" schneiden sie sich, als "Strecken" betrachtet liegt der Schnittpunkt nicht auf diesen, auch wenn sie sich in der Verlängerung schneiden.

"Wenn Endpunkte gleich -> schneiden sich" stimmt so nicht immer. Die Strecken könnten auch indentisch sein

Blup · Beiträge: 173 Erhaltene Danke: 43

@Mandaras
Ob die Berechnung des Schnittpunkts über s und t einfacher zu coden ist sei dahin gestellt.
Entsprechenden Quellcode hast du nicht zum Vergleich vorgestellt.

Zitat:

"Wenn Endpunkte gleich -> schneiden sich" stimmt so nicht immer. Die Strecken könnten auch indentisch sein

Das ist in dieser Funktion nur ein Sonderfall von "Strecken sind parallel", muss aber nicht gesondert behandelt werden.

Die Funktion scheint schon das richtige Ergebnis zu liefern, nur in der Benutzung zur Lösung eines uns noch nicht eindeutig beschriebenen Anwendungsfalls scheint der TE noch Probleme zu haben.

Blup · Beiträge: 173 Erhaltene Danke: 43

Ich gehe davon aus punktListe[] ist ein Array von Punkten, das die Eckpunkte eines N-Ecks enthält.
Die enthaltenen Punkte nenne ich [P0, P1 ... Pn].
Die Strecken dazwischen:
a (P0, P1)
b (P1, P2)
...
Die letzte Strecke ist als Sonderfall:
(Pn, P0)
Die Anzahl der Strecken ist damit identisch der Anzahl der Punkte.

Ermittelt werden soll, ob tatsächlich nur eine Gesamtfläche umschlossen wird.
Wenn sich Linien kreuzen ist das nicht der Fall.

Die Strecken dürfen nicht aufeinander liegen oder identisch sein,
das zu prüfen ist nicht Aufgabe der Funktion BerechneSchnittpunkt.

Aufeinander folgende bzw. benachbarte Kanten müssen deshalb nicht geprüft werden.
3 Punkte -> a,b,c
keine Prüfung notwendig

4 Punkte -> Strecken a,b,c,d:
a und c,
b und d

5 Punkte -> Strecken a,b,c,d,e:
a und c, a und d,
b und d, b und e,
c und e

6 Punkte -> Strecken a,b,c,d,e,f:
a und c, a und d, a und e,
b und d, b und e, b und f,
c und e, c und f
d und f

Daraus leite ich diesen Code ab (i und j ermitteln die zu vergleichenden Strecken):

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

private FPoint ErmittlePunkt(int n)
{
 return punktListe[n % punktListe.Count];
}

private void BerechneSchnittpunkte()
{
  for (int i = 0; i <= (punktListe.Count - 3); i++)
  {
    PointF P1 = ErmittlePunkt(i);
    PointF P2 = ErmittlePunkt(i + 1);
    
    int jmax = (punktListe.Count - 1);
    if (i = 0)
      jmax--;

    for (int j = i + 2; j <= jmax; j++)
    {
      PointF P3 = ErmittlePunkt(j);
      PointF P4 = ErmittlePunkt(j + 1);
      PointF schnittpunkt = new PointF();

      if (BerechneSchnittpunkt(P1, P2, P3, P4, schnittpunkt)
        Console.WriteLine(schnittpunkt);          
    }
  }
}

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme