trimmen-Funktion -> Brechnen des/der Schnittpunkte von Gerade und Kreis



  • Hallo,
    ich habe eine Strecke und einen Kreisbogen gegeben (Parallelen der Ursprünklichen Kontur einer Polylinie).
    Diese möchte ich miteinander trimmen, sodass ich wieder eine geschlossene Kontur erhalte.
    Ich habe bereits über einen längeren Zeitraum intensiv rechercheirt wie ich rechnerisch zum gesuchten Schnittpunkt kommen kann,
    und vermute jetzt, das ich beim umstellen der Formeln Fehler gemacht habe. Finde jedoch nicht wo.

    Die Daten der Strecke und des Kreises hole ich mir jeweils aus den Klassen die ich mir hierfür geschrieben habe.
    (Das ganze ist teil eines wesentlich größeren Programmes mit GUI)

    Es wäre echt super toll, wenn jemand hier sich die Zeit nehmen könnte und sich meiner annimmt 🕶 .

    Sorry für den langen Code-Ausschnitt. Ich habe meine Kommentare der Übersicht halber nicht heraus genommen:

    strecke s(text_a);
            bogen b(text_b);
    
            if(s.endp() == b.start())
            {
                return;
            }
    
            //Kreisformel aufstellen:
            //  mx = Kreismittelpunkt X-Wert
            //  my = Kreismittelpunkt Y-Wert
            //  r  = Kreisradius
            //  (x-mx)²+(y-my)²=r²
            double mx = b.mitte().x();
            double my = b.mitte().y();
            double r  = b.rad();
    
            //Geradenformel aufstellen:
            //  y = m*x+n
            //  m = (y2-y1)/(x2-x1) =Steigung
            //    x1 = X-Wert der vom Startpunkt der Strecke
            //    x2 = X-Wert der vom Endpunkt der Strecke
            //    y1 = Y-Wert der vom Startpunkt der Strecke
            //    y2 = Y-Wert der vom Endpunkt der Strecke
            double x1= s.startp().x();
            double x2= s.endp().x();
            double y1= s.startp().y();
            double y2= s.endp().y();
            double m = (y2-y1)/(x2-x1);
            //  n = Länge -->N bekommt man raus indem man m in die Geradenformel einsetzt
            //               mit den Werten von einem der Punkte
            //    y1 = m*x1+n   /-m*x1
            //    n = y1-m*x1
            double n = y1-m*x1;
    
            //Geradenformel in Kreisformel einsetzen:
            //  (x-mx)²+(   y   -my)²=r²
            //  (x-mx)²+((m*x+n)-my)²=r²
    
            //(x-mx)²            + (y-my)²           = r²  wobei y=m*x-n
            //-->(x-mx²) = x²-mx*x-mx*x+mx² = x²-2*mx*x+mx²
            //-->(y-my²) = y²-my*y-my*y+my² = y²-2*my*y+my²
            //
            //x² - 2*mx*x - mx²  + y² - 2*my*y - my² = r²
            //y ersetzen mit m*x-n:
            //x² - 2*mx*x - mx²  + (m*x-n)² - 2*my*(m*x-n) - my² = r²
            //-->(m*x-n)² = (m*x)²-(m*x)*n-(m*x)*n-n² = (m*x)²-2*(m*x)*n+n²
            //
            //x² - 2*mx*x - mx²  + (m*x)² - 2*(m*x)*n + n² - 2*my*(m*x-n) - my² = r²
            //-->(m*x)² = m²*x²
            //
            //x² - 2*mx*x - mx²  +  m²*x² - 2*m*x*n   + n² - 2*my*(m*x-n) - my² = r²
            //umsortieren:
            //
            //x² - 2*mx*x   + m²*x² - 2*m*x*n  - 2*my*(m*x-n)   +n²-mx²-my² = r²
            //umsortieren:
            //
            //x²+(m²)*x²  -(2*mx)*x -(2*m*n)*x - 2*my*(m*x-n)   +n²-mx²-my² = r²
            //-->x²+(m²)*x² = (m²+1)*x²
            //
            //(m²+1)*x²  -(2*mx)*x -(2*m*n)*x - 2*my*(m*x-n)   +n²-mx²-my² = r²
            //-->-(2*mx)*x -(2*m*n)*x = -((2*mx)+(2*m*n))*x
            //
            //(m²+1)*x²  -((2*mx)+(2*m*n))*x - 2*my*(m*x-n)   +n²-mx²-my² = r²
            //--> -2*my*(m*x-n) = -my*(m*x-n) -my*(m*x-n)
            //
            //(m²+1)*x²  -((2*mx)+(2*m*n))*x -my*(m*x-n) -my*(m*x-n)   +n²-mx²-my² = r²
            //--> -my*(m*x-n) = -my*m*x +my*n
            //
            //(m²+1)*x²  -((2*mx)+(2*m*n))*x -my*m*x +my*n - my*m*x +my*n   +n²-mx²-my² = r²
            //-->-my*m*x +my*n - my*m*x +my*n = -2*my*m*x +2*my*n
            //
            //(m²+1)*x²  -((2*mx)+(2*m*n))*x - 2*my*m*x    +2*my*n +n²-mx²-my² = r²
            //--> ((2*mx)+(2*m*n))*x - 2*my*m*x = -((2*mx)+(2*m*n)+(2*my*m))*x
            //
            //(m²+1)*x²  -((2*mx)+(2*m*n)+(2*my*m))*x      +2*my*n +n²-mx²-my² = r²      /-r²
            //
            //(m²+1)*x²  -((2*mx)+(2*m*n)+(2*my*m))*x      +2*my*n +n²-mx²-my²-r² = 0
            //  a   *x²  +             b           *x    +      c                 = 0
    
            //Lösung mit ABC-Formel eritteln:
            // a = (m²+1)
            // b = -1* ((2*mx)+(2*m*n)+(2*my*m))
            // b = (2*mx)-(2*m*n)-(2*my*m)
            // c = 2*my*n +n²-mx²-my²-r²
    
            double var_a = m*m+1;
            double var_b = (2*mx)-(2*m*n)-(2*my*m);
            double var_c = 2*my*n+n*n-mx*mx-my*my-r*r;
    
            // d = b²-4*a*c
            //wenn d > 0 dann gibt es 2 Lösungen
            //wenn d = 0 dann gibt es 1 Lösung
            //wenn d < 0 dann gibt es keine Lösung
            double var_d = var_b*var_b-4*var_a*var_c;
    
            if(var_d == 0)
            {
                //Es gibt genau eine Lösung
                // x = (  -b + wurzel(b²-4*a*c)  )  /  2*a
                double var_x = (-var_b  +  sqrt(var_d))/2*var_a;
    
                //X in Geradengleichung einsetzen und das dazu gehörende Y berechnen
                //  y = m*x+n
                double var_y = m*var_x+n;
    
                punkt3d p3d = s.endp();
                p3d.set_x(var_x);
                p3d.set_y(var_y);
                s.set_ende(p3d);
                b.set_startpunkt(p3d);
    
            }else if(var_d > 0)
            {
                //Es gibt zwei Lösungen
                // x1 = (  -b + wurzel(b²-4*a*c)  )  /  2*a
                // x2 = (  -b - wurzel(b²-4*a*c)  )  /  2*a
    
                double var_x1 = (-var_b  +  sqrt(var_d))/2*var_a;
                double var_x2 = (-var_b  -  sqrt(var_d))/2*var_a;
    
                //X in Geradengleichung einsetzen und das dazu gehörende Y berechnen
                //  y = m*x+n
                double var_y1 = m*var_x1+n;
                double var_y2 = m*var_x2+n;
    
                punkt3d p3d1 = s.endp();
                punkt3d p3d2 = s.endp();
    
                p3d1.set_x(var_x1);
                p3d1.set_y(var_y1);
                p3d2.set_x(var_x2);
                p3d2.set_y(var_y2);
    
                //Hier muss vorab noch entschieden werden ob p3d1 oder p3d2 richtig sind
                //Derzeit sind leider beide Punkte flasch
                s.set_ende(p3d2);
                b.set_startpunkt(p3d2);
    
            }
    

    ~edit durch SeppJ: Codetags korrigiert~


  • Gesperrt

    Dieser Beitrag wurde gelöscht!


  • Danke für deine Antwort titan99_
    das mit dem m-Werlt der Geraden bei senkrechter Stellung hatte ich noch gar nicht auf dem Schirm.
    Leider ist das Ergebnis der Funktion auch bei z.B einer 45° stehenden Geraden falsch 😞 (Da habe ich ja dann einen guten m-Wert).



  • Spontan sehe ich in Zeile 44 Fehler: Es muss (x-mx)² = x² - 2*mx*x + mx² heißen, entsprechend für y.
    Falls noch mehr Fehler drin sind, hat aber wahrscheinlich niemand Lust das alles durchzurechnen.
    Verwende dann lieber eine fertige Formel: https://de.wikipedia.org/wiki/Schnittpunkt#Schnittpunkte_einer_Gerade_mit_einem_Kreis
    Die hat auch das Problem mit m=unendlich nicht.



  • Für senkrechte und wagerechte Geraden habe ich jetzt eine funktionierende Gleichung dank des Tipps von titan99_ 😃
    Naja, bis auf das ich dem Programm noch beibringen muss ob p3d1 oder p3d2 zu nehmen ist 🙄

    if(y1 == y2)//Die Gerade darf nicht parallel zur Y-Achse verlaufen, da 0/(x2-x1) nicht geht!!!
            {
                double var_y = y1;
                //y in Kreisgleichung einsetzen
                //  (x-mx)²+(y-my)²=r²      /-(y-my)²
                //  (x-mx)² = r²-(y-my)²
                //  -->(x-mx)² = x²-2*x*mx+mx²
                //  x²-2*x*mx+mx² = r²-(y-my)²
                //  x²-(2*mx)*x  +mx² = r²-(y-my)²  /-r²+(y-my)²
                //  x²-(2*mx)*x  +mx² -r²+(y-my)² = 0
                //Lösung mit ABC-Formel eritteln:
                //a = 1
                //b = -2*mx
                //c = mx²-r²+(y-my)²
    
                double var_a = 1;
                double var_b = -2*mx;
                double var_c = mx*mx-r*r+(var_y-my)*(var_y-my);
    
                // d = b²-4*a*c
                //wenn d > 0 dann gibt es 2 Lösungen
                //wenn d = 0 dann gibt es 1 Lösung
                //wenn d < 0 dann gibt es keine Lösung
                double var_d = var_b*var_b-4*var_a*var_c;
    
                if(var_d == 0)
                {
                    //Es gibt genau eine Lösung
                    // x = (  -b + wurzel(b²-4*a*c)  )  /  2*a
                    double var_x = (-var_b  +  sqrt(var_d))/2*var_a;
    
                    punkt3d p3d = s.endp();
                    p3d.set_x(var_x);
                    p3d.set_y(var_y);
                    s.set_ende(p3d);
                    b.set_startpunkt(p3d);
    
                }else if(var_d > 0)
                {
                    //Es gibt zwei Lösungen
                    // x1 = (  -b + wurzel(b²-4*a*c)  )  /  2*a
                    // x2 = (  -b - wurzel(b²-4*a*c)  )  /  2*a
    
                    double var_x1 = (-var_b  +  sqrt(var_d))/2*var_a;
                    double var_x2 = (-var_b  -  sqrt(var_d))/2*var_a;
    
                    punkt3d p3d1 = s.endp();
                    punkt3d p3d2 = s.endp();
    
                    p3d1.set_x(var_x1);
                    p3d1.set_y(var_y);
                    p3d2.set_x(var_x2);
                    p3d2.set_y(var_y);
    
                    //Hier muss vorab noch entschieden werden ob p3d1 oder p3d2 richtig sind
                    s.set_ende(p3d1);
                    b.set_startpunkt(p3d1);
    
                }
            }else if(x1 == x2)
            {
    
                double var_x = x1;
                //y in Kreisgleichung einsetzen
                //  (x-mx)²+(y-my)²=r²      /-(x-mx)
                //  (y-my)² = r²-(x-mx)²
                //  -->(y-my)² = y²-2*y*my+my²
                //  y²-2*y*my+my² = r²-(x-mx)²
                //  y²-(2*my)*y  +my² = r²-(x-mx)²  /-r²+(x-mx)²
                //  y²-(2*my)*y  +my² -r²+(x-mx)² = 0
                //Lösung mit ABC-Formel eritteln:
                //a = 1
                //b = -2*my
                //c = my²-r²+(x-mx)²
    
                double var_a = 1;
                double var_b = -2*my;
                double var_c = my*my-r*r+(var_x-mx)*(var_x-mx);
    
                // d = b²-4*a*c
                //wenn d > 0 dann gibt es 2 Lösungen
                //wenn d = 0 dann gibt es 1 Lösung
                //wenn d < 0 dann gibt es keine Lösung
                double var_d = var_b*var_b-4*var_a*var_c;
    
                if(var_d == 0)
                {
                    //Es gibt genau eine Lösung
                    // x = (  -b + wurzel(b²-4*a*c)  )  /  2*a
                    double var_y = (-var_b  +  sqrt(var_d))/2*var_a;
    
                    punkt3d p3d = s.endp();
                    p3d.set_x(var_x);
                    p3d.set_y(var_y);
                    s.set_ende(p3d);
                    b.set_startpunkt(p3d);
    
                }else if(var_d > 0)
                {
                    //Es gibt zwei Lösungen
                    // y1 = (  -b + wurzel(b²-4*a*c)  )  /  2*a
                    // y2 = (  -b - wurzel(b²-4*a*c)  )  /  2*a
    
                    double var_y1 = (-var_b  +  sqrt(var_d))/2*var_a;
                    double var_y2 = (-var_b  -  sqrt(var_d))/2*var_a;
    
                    punkt3d p3d1 = s.endp();
                    punkt3d p3d2 = s.endp();
    
                    p3d1.set_x(var_x);
                    p3d1.set_y(var_y1);
                    p3d2.set_x(var_x);
                    p3d2.set_y(var_y2);
    
                    //Hier muss vorab noch entschieden werden ob p3d1 oder p3d2 richtig sind
                    s.set_ende(p3d2);
                    b.set_startpunkt(p3d2);
    
                }
            }
    


  • ....



  • C14 schrieb:

    Spontan sehe ich in Zeile 44 Fehler: Es muss (x-mx)² = x² - 2*mx*x + mx² heißen, entsprechend für y.
    Falls noch mehr Fehler drin sind, hat aber wahrscheinlich niemand Lust das alles durchzurechnen.
    Verwende dann lieber eine fertige Formel: https://de.wikipedia.org/wiki/Schnittpunkt#Schnittpunkte_einer_Gerade_mit_einem_Kreis
    Die hat auch das Problem mit m=unendlich nicht.

    Danke C14
    Habe deine Beitrag gerade erst gesehen.
    Werde die Tage mal versuchen die Formel, die du verlinkt hast, soweit zu versthen das ich sie anwenden kann. Sieht erst einmal vielversprechend aus 👍



  • Ich habe jetzt versucht mit der Wikipedia-Lösung die C14 gepostet hat zum Ergebnis zu kommen, bin mir aber nicht sicher ob ich den Lösungsweg richtig verstanden habe. So wie ich ihn umgesetzt habe erhalte ich nur die richtigen Ergebnisse wenn die Gerade genau senkrecht oder genau waagerecht ist und ich verstehe nicht warum.

    strecke s(text_a);
            bogen b(text_b);
    
            if(s.endp() == b.start())
            {
                return;
            }
    
            //Kreisformel aufstellen:
            //  mx = Kreismittelpunkt X-Wert
            //  my = Kreismittelpunkt Y-Wert
            //  r  = Kreisradius
            //  (x-mx)²+(y-my)²=r²
            double mx = b.mitte().x();
            double my = b.mitte().y();
            double r  = b.rad();
    
            //Geradenformel aufstellen:
            //  a*x + b*y = c
            //    x1 = X-Wert der vom Startpunkt der Strecke
            //    x2 = X-Wert der vom Endpunkt der Strecke
            //    y1 = Y-Wert der vom Startpunkt der Strecke
            //    y2 = Y-Wert der vom Endpunkt der Strecke
            double x1= s.startp().x();
            double x2= s.endp().x();
            double y1= s.startp().y();
            double y2= s.endp().y();
            // a = y1-y2
            // b = x2-x1
            // c = x2*y1 - x1*y2
            double var_a = y1-y2;
            double var_b = x2-x1;
            double var_c = x2*y1 - x1*y2;
            // d = c-a*mx-b*my
            double var_d = var_c-var_a*mx-var_b*my;
            // e = r²*(a²+b²)-d²
            double var_e = r*r * (var_a*var_a + var_b*var_b) - var_d*var_d;
    
            //QMessageBox mb;
            //mb.setText("e= " + double_to_qstring(var_e));
            //mb.exec();
    
            if(var_e == 0)
            {
                //Es gibt genau eine Lösung
                // x = mx+ a*d / (a²+b²)
                double var_x = mx+ var_a*var_d / (var_a*var_a + var_b*var_b);
    
                // y = my+ b*d / (a²+b²)
                double var_y = my+ var_b*var_d / (var_a*var_a + var_b*var_b);
    
                punkt3d p3d = s.endp();
                p3d.set_x(var_x);
                p3d.set_y(var_y);
                s.set_ende(p3d);
                b.set_startpunkt(p3d);
    
            }else if(var_e > 0)
            {
                //Es gibt zwei Lösungen
                // x1 = mx+ (a*d + b* wurzel(e)) /  (a²+b²)
                // x2 = mx+ (a*d - b* wurzel(e)) /  (a²+b²)
                double var_x1 = mx+ (var_a*var_d + var_b*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
                double var_x2 = mx+ (var_a*var_d - var_b*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
    
                // y1 = my+ (b*d + a* wurzel(e)) /  (a²+b²)
                // y2 = my+ (b*d - a* wurzel(e)) /  (a²+b²)
                double var_y1 = my+ (var_b*var_d + var_a*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
                double var_y2 = my+ (var_b*var_d - var_a*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
    
                punkt3d p3d1 = s.endp();
                punkt3d p3d2 = s.endp();
    
                p3d1.set_x(var_x1);
                p3d1.set_y(var_y1);
                p3d2.set_x(var_x2);
                p3d2.set_y(var_y2);
    
                //Hier muss vorab noch entschieden werden ob p3d1 oder p3d2 richtig sind
                s.set_ende(p3d2);
                b.set_startpunkt(p3d2);
    
            }
    


  • Bei y1/2y_{1/2} hast du Minus und Plus vertauscht. In der Formel steht \mp, du hast ±\pm.



  • Danke, das du noch einmal drauf gesehen hast C14

    jetzt funktioniert dank eurer Hilfe alles so wie es soll 😃

    if(text_a.contains(STRECKE) && text_b.contains(BOGEN))
        {
            strecke s(text_a);
            bogen b(text_b);
    
            if(s.endp() == b.start())
            {
                return;
            }
    
            //Kreisformel aufstellen:
            //  mx = Kreismittelpunkt X-Wert
            //  my = Kreismittelpunkt Y-Wert
            //  r  = Kreisradius
            //  (x-mx)²+(y-my)²=r²
            double mx = b.mitte().x();
            double my = b.mitte().y();
            double r  = b.rad();
    
            //Geradenformel aufstellen:
            //  a*x + b*y = c
            //    x1 = X-Wert der vom Startpunkt der Strecke
            //    x2 = X-Wert der vom Endpunkt der Strecke
            //    y1 = Y-Wert der vom Startpunkt der Strecke
            //    y2 = Y-Wert der vom Endpunkt der Strecke
            double x1= s.startp().x();
            double x2= s.endp().x();
            double y1= s.startp().y();
            double y2= s.endp().y();
            // a = y1-y2
            // b = x2-x1
            // c = x2*y1 - x1*y2
            double var_a = y1-y2;
            double var_b = x2-x1;
            double var_c = x2*y1 - x1*y2;
            // d = c-a*mx-b*my
            double var_d = var_c-var_a*mx-var_b*my;
            // e = r²*(a²+b²)-d²
            double var_e = r*r * (var_a*var_a + var_b*var_b) - var_d*var_d;
    
            //QMessageBox mb;
            //mb.setText("e= " + double_to_qstring(var_e));
            //mb.exec();
    
            if(var_e == 0)
            {
                //Es gibt genau eine Lösung
                // x = mx+ a*d / (a²+b²)
                double var_x = mx+ var_a*var_d / (var_a*var_a + var_b*var_b);
    
                // y = my+ b*d / (a²+b²)
                double var_y = my+ var_b*var_d / (var_a*var_a + var_b*var_b);
    
                punkt3d p3d = s.endp();
                p3d.set_x(var_x);
                p3d.set_y(var_y);
                s.set_ende(p3d);
                b.set_startpunkt(p3d);
    
            }else if(var_e > 0)
            {
                //Es gibt zwei Lösungen
                // x1 = mx+ (a*d + b* wurzel(e)) /  (a²+b²)
                // x2 = mx+ (a*d - b* wurzel(e)) /  (a²+b²)
                double var_x1 = mx+ (var_a*var_d + var_b*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
                double var_x2 = mx+ (var_a*var_d - var_b*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
    
                // y1 = my+ (b*d - a* wurzel(e)) /  (a²+b²)
                // y2 = my+ (b*d + a* wurzel(e)) /  (a²+b²)
                double var_y1 = my+ (var_b*var_d - var_a*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
                double var_y2 = my+ (var_b*var_d + var_a*sqrt(var_e)) / (var_a*var_a + var_b*var_b);
    
                punkt3d p3d1 = s.endp();
                punkt3d p3d2 = s.endp();
    
                p3d1.set_x(var_x1);
                p3d1.set_y(var_y1);
                p3d2.set_x(var_x2);
                p3d2.set_y(var_y2);
    
                //entscheiden ob p3d1 oder p3d2 richtig sind:
                double winkel_orgi = winkel(b.start().x(),b.start().y(),\
                                            b.ende().x(),b.ende().y(),\
                                            b.mitte().x(),b.mitte().y());
                double winkep_p3d1 = winkel(p3d1.x(),p3d1.y(),\
                                            b.ende().x(),b.ende().y(),\
                                            b.mitte().x(),b.mitte().y());
                double winkep_p3d2 = winkel(p3d2.x(),p3d2.y(),\
                                            b.ende().x(),b.ende().y(),\
                                            b.mitte().x(),b.mitte().y());
                double diff_1 = winkel_orgi - winkep_p3d1;
                if(diff_1 < 0)
                {
                    diff_1 = -diff_1;
                }
                double diff_2 = winkel_orgi - winkep_p3d2;
                if(diff_2 < 0)
                {
                    diff_2 = -diff_2;
                }
                if(diff_1 < diff_2)
                {
                    s.set_ende(p3d1);
                    b.set_startpunkt(p3d1);
                }else
                {
                    s.set_ende(p3d2);
                    b.set_startpunkt(p3d2);
                }
            }
    
            //Werte zurück in die geo-QStrings schreiben:
            *geo1 = s.get_text();
            *geo2 = b.get_text();
    
        }
    

Anmelden zum Antworten