Algo gesucht: grösstes Dreieck im Quadrat

  • Allgemein

Es gibt 44 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    ErfinderDesRades schrieb:

    hübsche Formeln, aber was rechnen die aus?

    Ich zumindest bräuchte eine Function, der man von einem Dreieck eine Seite übergibt (2 Punkte), sowie die 3 Winkel, und zurück bekommt man den 3. Punkt.
    Damit liesse sich der vom TE in post#3 skizzierte Algo implementieren.

    Genau das hab ich gemacht.

    Ich hab den Dreieck die Kante des Quadrats übergeben. Dabei ist darauf zu achten, das die längste Kante des Dreiecks genommen wird. Dann hab ich den 3. Punkt berechnet. Das ist HBx und HBy .Die anderen Punkte haben sich durch die Positionierung des Dreiecks genau auf der Kante des Quadrates in voller Länge ergeben . Dann wird das Dreieck in eine Position gedreht, wo es die größte mögliche Fläche besitzt.

    aber dann müsste die Zeichnung doch ein 3-eck zeigen, von dem mindestens eine Seite >= 200 ist.

    Code aus derTestanwendung:

    VB.NET-Quellcode

    1. Private Sub frmTriangleInSquare_Paint(sender As Object, e As System.Windows.Forms.PaintEventArgs) Handles Me.Paint
    2. Dim rct = New RectangleF(200, 100, 200, 200)
    3. e.Graphics.DrawRectangles(Pens.Blue, {rct})
    4. e.Graphics.DrawPolygon(Pens.Red, GetTriangle(rct, 22.24106, 109.03332, 48.72563))
    5. End Sub
    7. Private Function GetTriangle(rct As RectangleF, Alpha As Double, Beta As Double, Gamma As Double) As PointF()
    8. Dim Dpl As Double = rct.Width 'Quadratgröße
    9. Dim Deg As Double = Math.PI / 180 'Umrechnung in Grad
    10. Dim HBy As Double = Dpl * Math.Sin(Alpha * Deg) / Math.Sin(Beta * Deg) * Math.Sin(Gamma * Deg)
    11. Dim HBx As Double = Dpl - (HBy * Math.Tan((90 - Gamma) * Deg))
    12. Dim By As Double = Dpl
    13. Dim Bx As Double = HBx - (Dpl - HBy) * Math.Tan(Alpha * Deg)
    14. Dim Cy As Double = Dpl - (Dpl - Bx) / (Math.Tan((90 - (180 - (Math.Atan(Dpl / Bx) * 180 / Math.PI) - Beta)) * Deg))
    15. Dim Cx As Double = Dpl
    16. Return {HBx, Bx, Cx}.Zip({HBy, By, Cy}, Function(x, y) New PointF(CSng(x), CSng(y))).ToArray
    17. End Function
    sieht mir aber gar nicht so aus.

    Es ist doch ein Dreieck , wo nur die Winkel bekannt sind. Auf der Ebene ist keine Position vorgegeben. Die Seiten des Dreiecks können jede beliebige Größe haben. Bedingng ist nur, das die Winkel sich nicht ändern. Nun ist es die Aufgabe, das Dreieck so zu positionieren, das das Quadrat möglichst großflächig bedeckt ohne die Winkel des dreiecks zu ändern. Dabei muß das Dreieck in die richtige Position gedreht nund auch gestreckt werde. das ich die Kantenlänge des quadrates nehme ist nur um den Dreieck eine Fläche zu geben. Denn das ist ja die einzige Länge, die die Aufgabe zuläßt. man könnte sie zwar noch teilen. Aber wozu?Da ich die längste Seite des Dreiecks nehme, Brauch ich das Dreieck bloß noch soweit drehen bis ich mit den 3. Punkt an den nächsten Rand des Quadrats stoße. Das Dumme ist nur, das ich beim drehen gleichzeitig auch strecken muß. Bei etlichen Versuchen gestern ist mir dann eine Gesetzmäßigkeit oder sagen wir mal lieber-Regelmäßigkeit aufgefallen. was sehr zur Lösung des Problems beigetragen hat.
    Man muß auch bedenken, das ein Dreieck ohne Längen im Prinzip keine Fläche hat.

    Hab deine Frage ehrlich gesagt nicht verstanden!
    Gruß hlghyr

    und ich verstehe deine Erklärung nicht.
    jedenfalls rechnet deine Rechnung nicht das optimal große 3-Eck aus, dessen kannst du dich überzeugen, wenn du die Testanwendung laufen lässt.

    Vielleicht habe ich deine Formeln auch falsch eingebaut, aber es sollte dir ja ein leichtes sein, die richtig einzubauen.

    Der gegebene Rahmen ist die Methode GetTriAngle, und die bekommt das Quadrat gegeben + die 3 Winkel, und sie gibt ein Array von 3 PointF zurück, nämlich die Eckpunte eines 3-Ecks.
    Wenn du da die Rechnung richtig einfrickelst, dann wird man die Richtigkeit des Ergebnisses direkt angugge können.

    Man könnte doch versuchen es algorithmisch näherungsweise und nicht exakt zu berechnen. Dazu muss man halt möglichst viele Möglichkeiten durchgehen. Diese können schon mal stark eingegrenzt werden. Das Dreieck lässt sich zum Besispiel, wegen der Symmetrie des Quadrates, durch die drei Winkel und einen Punkt auf der unteren Seite und einen Punkt auf der linken Seite eindeutig bestimmen.

    Die Punkte kann man z.B. als Vektoren betrachten, also (x,0) und (0,y), wenn man das Einheitsquadrat mit der linken unteren Ecke im Nullpunkt betrachtet.
    Dabei wählt man x,y aus [0,1]. Es lässt sich sogar zeigen, dass es ausreicht, falls x<0.5 ist auch für y nur Werte aus [0,0.5) zu betrachten.

    Der Flächeninhalt lässt sich den mittels Vektoren mehr oder weniger kompliziert mit einer Formel berechnen.
    Setzt man dies in einem schlauen Algorithmus um, sollte das Problem relativ genau gelöst werden können.
    Für einen schlauen Algorithmus fehlt z.B. noch wie man sich bestmöglich der Lösung nähert.

    Edit:
    Müssen die Eckpunkte überhaupt auf dem Quadrat liegen? Falls nicht muss ich meinen Beitrag nochmal überdenken :)

    Edit 2:
    Falls nicht reicht es aber nicht ein Dreieck mit den passenden Winkeln zu nehmen und es zu drehen und zu strecken, bis es den maximalen Flächeninhalt hat. Man kann es doch auch noch verschieben. Außerdem um welchen Punkt wird gedreht?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ponmalka“ ()

    ja, so weit waren wir schon glaub in post#3.

    wie gesagt: mir fehlt zur Umsetzung nur eine Methode, die aus 2 Eckpunkten und 2 Winkeln (der 3. Winkel ergibt sich dann ja) den 3. Eckpunkt berechnet.
    alles annere ist trivial (und genannte Berechnung ist auch nix weiter als maximal Gymnasium-Schul-Mathe-Grundkurs).

    Ja stimmt. Sorry ich hab einiges nur überflogen.

    Edit:
    Also mit der Drehmatrix (s. Wikipedia) [cos(a), -sin(a); sin(a), cos(a)] dreht man einen Vektor um a.

    Wenn x,y die beiden Eckpunkte, a der Winkel an x und b der Winkel an y, so dreht man den Vektor (y-x) um a und den Vektor (x-y) um b Grad.
    Um dann den Schnittpunkt der beiden Vektoren zu berechnen muss man ein GLS mit zwei Unbekannten lösen.

    Hier die allgemeine Lösung von "http://www.emath.de/Mathe-Board/messages/6/29346.html?1330075054":
    Beispiel:

    Für ein Gleichungssystem

    a1*x + b1*y = c1
    a2*x + b2*y = c2

    läßt sich angeben

    x = (c1*b2-c2*b1)/(a1*b2-a2*b1) und
    y = (a1*c2-a2*c1)/(a1*b2-a2*b1).
    Damit kann man dann direkt den dritten Punkt des Dreiecks ausrechnen.
    Für den Flächeninhalt funktioniert es ähnlich...

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ponmalka“ ()

    EDR ich hab Dein Programm nicht zum laufen bekommen. Hab auch noch nie mit Forms gearbeitet. Will ich auch nicht mehr mit anfangen. Hab jetzt mal 3 Bilder mit ran gehängt. Und ich hoffe nun das man versteht was ich meine. Man muss immer davon ausgehen das nur die Winkel im Raum mit einer Beziehung zueinander rumschwirren. Es muss nicht mal ein Ort vorhanden sein. Das 2. Bild materialisiert das Dreieck erst. Und zwar mit einer bestimmten Größe. Aber das ist nur ein Zwischenschritt.--- Winkel im Raum--- bringt mich auf eine Idee für meine nächste Aufgabe.
    Auch hatte ich vor einigen post geschrieben, das es nicht komplett ist(das Programm). Es fehlen noch die verschiedenen Arten von Dreiecken.
    Aber wenn Ihr die 4 Werte (Winkel und Kantenlänge) in das Programm übertragt, müßte das richtige Ergebnis bei raus kommen. Die werte stehen bis auf Hbx und Hby in der Zeichnung.
    Bilder

    • Bild 1.png

      11,44 kB, 814×695, 89 mal angesehen

    • Bild 2.png

      12,85 kB, 700×600, 80 mal angesehen

    • Bild 3.png

      9,94 kB, 814×695, 85 mal angesehen

    wie gesagt: Seit post#3 ist mir die Lösung sonnenklar:
    man fängt an mit deim Bild#2 - also die lange Seite des 3ecks liegt auf der oberen Quadrat-Kante.
    Dann geht man schrittweise (oder binär interpoilierend) mit dem rechten punkt nach unten, also immer die rechte Kante des Quadrats lang. Dadurch wird die lange Seite des 3ecks logisch immer länger, bis maximal Quadrat-Ecke unten rechts.
    Und das ist auch der Punkt, wo die lange seite auf der Diagonalen liegt.
    Oder der 3.Punkt stößt auf eine der beiden anneren Quadrat-Kanten, dann beendet der Algo, bevor die lange 3eck-Seite auf der Diagonalen liegt.

    Du siehst: keine Fallunterscheidung. Einfach nur den Algo anwenden - ist der 3.Winkel >90°, so stößt er eben an keine Quadrat-Kante, sondern der Algo endet mit lange 3eck-Seite auf der Diagonalen.

    einziges Problem: Wie rechne ich den 3. Punkt, wenn ich alle Winkel und 2 Punkte eines 3ecks habe?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    ErfinderDesRades schrieb:

    einziges Problem: Wie rechne ich den 3. Punkt, wenn ich alle Winkel und 2 Punkte eines 3ecks habe?

    Du stellst zuerst 2 (mathematische) Funktionen auf, die 2 Geraden beschreiben, die durch einen der Punkte laufen und auch den richtigen Winkel haben. Jetzt musst du nur noch den Schnittpunkt der beiden Geraden berechnen und hast deinen dritten Punkt.

    Den Schnittpunkt berechnest du so: community.topcoder.com/tc?modu…d1=tutorials&d2=geometry2 Da wird auch das Aufstellen der Geradengleichungen erklärt. Das wird dort mit je 2 Punkten gemacht. Da du ja für die beiden bekannten Ecken sowohl den Punkt als auch den Winkel hast, kannst du dir entweder so einen 2. Punkt berechnen oder die Geradengleichung einfach in der Form y=a*x+b angeben, wobei a die Steigung und b die Y-Achsen-Nullstelle ist. a sollte sich durch tan(Winkel) berechnen lassen. Dann setzt du die Steigung für a und den gegeben Punkt für x und y ein und übrig bleibt b, dass du somit ausrechnen kannst. Fertig ist die Formel.

    Wenn ich das richtig sehe, ist in der Formel Ax+By=C dann A=-a, B=1 und C=b, wenn du die umwandeln willst/musst, um die Schnittpunktsberechnung wie im Link erklärt, durchführen zu können.

    Skybird schrieb:

    Das sind ja Ubisoftmethoden hier !

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „vb-checker“ ()

    ErfinderDesRades schrieb:

    Du siehst: keine Fallunterscheidung. Einfach nur den Algo anwenden - ist der 3.Winkel >90°, so stößt er eben an keine Quadrat-Kante, sondern der Algo endet mit lange 3eck-Seite auf der Diagonalen.


    Diese Aussage ist falsch. Sie trifft nur zu wenn 2 Winkel <45 sind. Denn 100° >90° ein Winkel, 20°<45° nächster Winkel 60°>45°letzter Winkel. Würde ich jetzt nach Deiner Aussage die lange Seite Diagonal anordnen, würde der letzte Punkt das Quadrat verlassen. Denn 90° /2=45°. Das kann man aber leicht prüfen und auch umsetzen. Ein weiteres Problem sind noch Dreiecke wo alle Winkel über 45° vielleicht auch 50° sind. Das muss ich noch prüfen.
    Die Koordinaten des 3.Punktes berechnet man normaler weise mit der pq-Formel. Doch das wollte ich mir ersparen, weil diese Formel immer 2 Ergebnisse raus gibt. Einmal über der Strecke und einmal drunter. Somit hätte man erst noch entscheiden müssen, welchen Punkt man braucht. Bei den Hilfsdreieck wär das kein Problem. Aber beim letzten Dreieck sehe ich das auf der Schnelle anders. Hab zwar mit der Formel schon gearbeitet aber hab , was das Problem mit den Dreiecken angeht, keine Gedanken dran verloren.

    dann hast du den algo nicht verstanden. Der Algo endet nur dann mit der langen seite auf der Diagonalen, wenn beide Winkel <45°. Ansonsten findet er die Position, wo der 3.Punkt auf der unteren Kante liegt.

    schön.
    also jeder weiß theoretisch, wie man die 3. Ecke eines Dreiecks ausrechnet, von dem Winkel, Seite, Winkel bekannt sind. Nur der praktische Code fehlt dazu noch.

    ERD! Wenn Du mein Algo meinst, hab ich den verstanden. Denn der ist von mir. Mein letztes post bezog sich auf die Aussage mit den >90°. Denn das ist eine schwammige Aussage. Da sie in nicht allen Fällen zutrifft. Der 3. Punkt für das Hilfsdreieck wird doch mit Hbx und Hby berechnet.
    Wenn Du jetzt Dein Algo meinst, dann versuch das mal um zu setzen. Du müßtest Dich an das Ergebnis rantasten und irgendwann sagen: Ist genau genug!
    Oder hab ich Dich falsch verstanden?

    ErfinderDesRades schrieb:

    schön.
    also jeder weiß theoretisch, wie man die 3. Ecke eines Dreiecks ausrechnet, von dem Winkel, Seite, Winkel bekannt sind. Nur der praktische Code fehlt dazu noch.

    Warum machst du denn nicht, was ich geschrieben habe? Hier, komplett lauffertig:

    VB.NET-Quellcode

    1. Public Class Form1
    2. Private ReadOnly Punkt1 As New Point(0, 0)
    3. Private ReadOnly Winkel1 As Double = 330
    4. Private ReadOnly Punkt2 As New Point(20, 0)
    5. Private ReadOnly Winkel2 As Double = 250
    7. Private Sub Form1_Shown(sender As Object, e As EventArgs) Handles Me.Shown
    8. Dim steigung1 As Double = Math.Tan(Winkel1)
    9. Dim steigung2 As Double = Math.Tan(Winkel2)
    10. Dim b1 As Double = Punkt1.Y - steigung1 * Punkt1.X
    11. Dim b2 As Double = Punkt2.Y - steigung2 * Punkt2.X
    12. Dim det As Double = (-steigung1) - (-steigung2)
    13. Dim x As Double = (b1 - b2) / det
    14. Dim y As Double = ((-steigung1) * b2 - (-steigung2) * b1) / det
    15. End Sub
    16. End Class


    Grafischer Beweis, dass die Lösung stimmt:
    Bilder

    • Unbenannt.png

      4,24 kB, 569×190, 55 mal angesehen

    Skybird schrieb:

    Das sind ja Ubisoftmethoden hier !

    so, endlich geht voran - thx für den Ansatz mitte Steigung.
    War noch sehr zu erweitern, denn deine Steigungs-Formeln bezogen sich nur auf eine horizontale 3eck-Seite, und dann gabs noch ein trigonometrisches Vorzeichen-Problem.
    Aber v.a. dass der Tangens die Steigung ist hat meiner Geometrie gefehlt ?(

    VB.NET-Quellcode

    1. Private Function Get3rdCorner(pt0 As PointF, pt1 As PointF, angle0 As Double, angle1 As Double) As PointF
    2. Dim m01 = (pt0.Y - pt1.Y) / (pt0.X - pt1.X) 'Steigung pt0->pt1
    3. Dim angleAdd = Math.Atan(m01)
    4. Dim tmp = Math.PI / 180
    5. angle0 *= tmp
    6. angle1 *= tmp
    7. Dim m02 = Math.Tan(angle0 + angleAdd) 'Steigung pt0->pt2
    8. Dim m12 = Math.Tan(-angle1 + angleAdd) 'Steigung pt1->pt2
    9. Dim b1 = pt0.Y - m02 * pt0.X
    10. Dim b2 = pt1.Y - m12 * pt1.X
    11. Dim det = m12 - m02
    12. Dim x = (b1 - b2) / det
    13. Dim y = (m12 * b1 - m02 * b2) / det
    14. Return New PointF(CSng(x), CSng(y))
    15. End Function


    Aber nun kann man den kleinsten Winkel in die topLeft-Ecke des Quadrats packen, den 2.-kleinsten nach topRight, und auf der rechten Seite schrittweise runterlaufen:

    VB.NET-Quellcode

    1. Private Sub frmTriangleInSquare_Paint(sender As Object, e As System.Windows.Forms.PaintEventArgs) Handles Me.Paint
    2. Dim quadrat = New RectangleF(200, 100, 400, 400)
    3. e.Graphics.DrawRectangles(penRect, {quadrat})
    4. Dim corners = {quadrat.Location, New PointF(quadrat.X + quadrat.Width, quadrat.Y), PointF.Empty} 'topLeft, topRight, empty
    5. For y = 0 To quadrat.Height Step 50
    6. corners(2) = Get3rdCorner(corners(0), corners(1), Angles(0), Angles(1))
    7. e.Graphics.DrawPolygon(Pens.Red, corners)
    8. corners(1).Y += 50 'increment topRight
    9. Next
    10. End Sub


    Das gibt schomal diese Figur:


    Und da kann man sich ja ebensogut binär interpolierend an die Quadrat-Unterkante annähern, aber weil ich die Darstellung so eiglich hübscher finde als das fertige Endergebnis, schenke ich mir das.
    Dateien

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    EDR!
    Da ist mir gerade eine Idee gekommen. Du legst das Dreieck an die obere Kante. Dann berechnest du ein Dreieck was mit der rechten Ecke diagonal im Quadrat liegt. nun ist der 3.Eckpunkt außerhalb des Quadrates. Wenn man jetzt das Verhältnis von Hilsdreieck 3.punkt bis Unterkante zum Quadrat zu Dreick 3.Punkt biz unterkante Quadrat nimmt, müsste man das doch durch das Verhältnis berechnen können. so das es genau rein passt.

    Noch besser wenn du Die dreiereckpunkte verbindest, schneiden die die untergante und du brauchst nur den Schnittpunkt berechnen.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „hlghyr“ ()

    hab nicht verstanden, welche Verhältnisse du meinst.
    Ich glaub auch nicht, dass das mit Verhältnisrechnung lösbar ist.
    allenfalls lässt man da einen indischen Super-Mathematiker drauf los, der da gschwind eine f(x) zu aufstellt, und dann iwas greuliches mit Differentialrechnung mit anstellt.

Facebook
Telefonspende