maximale Fläche < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:45 Do 24.03.2005 | | Autor: | jerela |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Man hat 4 Punkte A, B, C, D, welche ein Viereck bilden in einem zweidimensionalem Koordinatensystem.
Gesucht ist das Rechteck,
- das sich vollständig im Viereck befindet,
- deren Kanten jeweils parallel zur x und y Achse sind
- und die maximale Fläche hat.
Meine konkrete Frage ist:
"Wie ermittelt man dieses Rechteck?"
|
|
| |
|
Hi, also ich nehme an das wir bei der Vektorrechnugn sind oder?
Also zuerst kannst du alle Richtungen aufstellen, wenn du alle Punkte gegeben hast. Die Richtungsvektoren der gegenüberliegenden Seiten sollten nun ein Vielfaches voneinander sein.
Um jetzt noch herauszufinden ob es ein Viereck mit 4 * 90° ist oder ob es ein Parallelogramm ist, kannst du zwei nicht gegenüberliegende Seiten auf Orthogonalität überprüfen.
Was nun deine Frage betrifft, bin ich ein wenig verwirrt, sollst du nun nur die Fläche ausrechnen oder ist es eine Extremwertaufgabe?
Gruß Jens
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:04 Fr 25.03.2005 | | Autor: | jerela |
> Hi, also ich nehme an das wir bei der Vektorrechnugn sind oder?
Das schien mir am naheliegensten, da ich aber die Lösung nicht kenne,
kann ich das nur vermuten.
> Also zuerst kannst du alle Richtungen aufstellen, wenn du alle Punkte
> gegeben hast.
Was heißt "alle Richtungen aufstellen"
> Die Richtungsvektoren der gegenüberliegenden Seiten
> sollten nun ein Vielfaches voneinander sein.
Warum das?
> Um jetzt noch herauszufinden ob es ein Viereck mit 4 * 90° ist oder ob
> es ein Parallelogramm ist, kannst du zwei nicht gegenüberliegende
> Seiten auf Orthogonalität überprüfen.
Das Viereck braucht weder 4 * 90° noch eine Parallelogramm zu sein.
Beispiel: A(0,0) B(1,3) C(2,4) D(5,2)
> Was nun deine Frage betrifft, bin ich ein wenig verwirrt, sollst du nun
> nur die Fläche ausrechnen oder ist es eine Extremwertaufgabe?
Wie gesagt, ich kenne die Lösung nicht, deshalb weiß ich nicht, ob es eine Extremwertaufgabe ist oder nicht, was ich wissen möchte sind die 4 Punkte des Rechtecks, welches sich innerhalb des Vierecks befinden.
|
|
|
| |
|
Hallo jerela,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> > Hi, also ich nehme an das wir bei der Vektorrechnugn sind
> oder?
> Das schien mir am naheliegensten, da ich aber die Lösung
> nicht kenne, kann ich das nur vermuten.
aber du kennst doch den Zusammenhang, in dem diese Aufgabe gestellt wurde?!
Analysis oder Geometrie?
>
> Das Viereck braucht weder 4 * 90° noch eine Parallelogramm
> zu sein.
> Beispiel: A(0,0) B(1,3) C(2,4) D(5,2)
Sieht eine Planskizze vielleicht so aus?
[Dateianhang nicht öffentlich]
Hier erkennst du, dass die beiden Punkte C und D auf den rechten beiden Seiten des Vierecks liegen müssen
und eine der linken Ecken auf einer der beiden anderen Seiten.
Ich bin mir nicht ganz schlüssig, ob man diese Aufgabe mit Vektoren oder lieber doch mit Analysis lösen kann.
Aber das kannst du nur aus dem Zusammenhang der Aufgabe entscheiden: äußere dich bitte mal.
> > Was nun deine Frage betrifft, bin ich ein wenig verwirrt,
> sollst du nun
> > nur die Fläche ausrechnen oder ist es eine
> Extremwertaufgabe?
> Wie gesagt, ich kenne die Lösung nicht, deshalb weiß ich
> nicht, ob es eine Extremwertaufgabe ist oder nicht, was ich
> wissen möchte sind die 4 Punkte des Rechtecks, welches sich
> innerhalb des Vierecks befinden.
>
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:45 Sa 26.03.2005 | | Autor: | jerela |
Hallo,
> aber du kennst doch den Zusammenhang, in dem diese Aufgabe
> gestellt wurde?!
Die Aufgabe hat sich mir im wahren Leben gestellt.
(Ich möchte einfach nur die Lösung wissen. :))
> Sieht eine Planskizze vielleicht so aus?
> [Dateianhang nicht öffentlich]
Leider weiß ich nicht was ein "Planskizze" ist, aber man kann sich die Aufgabe so vorstellen.
> Hier erkennst du, dass die beiden Punkte C und D auf den
> rechten beiden Seiten des Vierecks liegen müssen
> und eine der linken Ecken auf einer der beiden anderen
> Seiten.
ja und?!?!
> Ich bin mir nicht ganz schlüssig, ob man diese Aufgabe mit
> Vektoren oder lieber doch mit Analysis lösen kann.
> Aber das kannst du nur aus dem Zusammenhang der Aufgabe
> entscheiden: äußere dich bitte mal.
Wie gesagt, die Aufgabe hat sich mir gestellt, ohne dass jemand dabei war der dazu ein Themengebiet geliefert hat.
|
|
|
| |
|
Hallo jerela,
Die Aufgabe ist nicht ganz so einfach, wie sie am Anfang erscheinen mag. Siehe dir mal ![[]](/images/popup.gif) folgende Diskussion dazu an.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:03 Mi 30.03.2005 | | Autor: | jerela |
Leider haben mir die Links nicht geholfen, sondern nur gezeigt, dass auch andere die Lösung nicht wissen.
Kann mir denn niemand helfen?
Es muss doch jemanden geben, der eine solche Aufgabe lösen kann.
|
|
|
| |
|
Hallo jerela,
> Leider haben mir die Links nicht geholfen, sondern nur
> gezeigt, dass auch andere die Lösung nicht wissen.
> Kann mir denn niemand helfen?
Nicht verzweifeln. 
Ich habe gerade die Begriffe "largest rectangle" und "quadrilateral" aus einer der oberen Diskussionen rauskopiert und Googles Web-Suche damit gefüttert. Hier ist eine Seite, die dir vielleicht hilft. Sollte dir diese Seite nicht reichen, kannst Du dich vielleicht noch mit den Leuten von diesem Geometrie-Projekt per E-Mail in Verbindung setzen. Vielleicht können sie dir weiterhelfen.
Viele Grüße
Karl
[P.S. Auf der Seite gibt es auch ein Java-Applet mit dem Du für ein beliebiges Polygon das flächengrößte innere Rechteck bestimmen kannst. Schau dir dieses Applet mal an.]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:59 Mi 30.03.2005 | | Autor: | jerela |
Googleergebnisse helfen mir wirklich nicht weiter.
Das Googlen hatte ich schon hinter mir, bevor ich
die Aufgabe hier gestellt habe.
Ich wäre wirklich dankbar, wenn man mir einfach
die Lösung dieser Aufgabe verraten würde.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:50 Do 31.03.2005 | | Autor: | leduart |
Hallo
> Googleergebnisse helfen mir wirklich nicht weiter.
> Das Googlen hatte ich schon hinter mir, bevor ich
> die Aufgabe hier gestellt habe.
> Ich wäre wirklich dankbar, wenn man mir einfach
> die Lösung dieser Aufgabe verraten würde.
Es fehlt hier ein Ende?
Dein Ton ist nicht sehr nett! Hast du nicht gemerkt, dass sich mehrere Leute Mühe gegben haben?
Es hilft dir vielleicht, wenn du weisst, dass es wirklich keine allgemeine Lösung dafür gibt!
Wenn du bestimmte Pkt A B C D gibst, kann man dir vielleicht helfen, Oder Aufgaben laufen ja nicht so auf der Strasse rum und betteln: "Haste mal ne Lösung" Wenn du uns verrättst, woher sie kommt?
Wenn du das letzte Link von Karl Pech wirklich aufmachst, findest du am Ende ein Applet, mit dem du jede konkrete Aufgabe lösen kannst!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:37 Do 31.03.2005 | | Autor: | jerela |
Lieber leduart,
> Dein Ton ist nicht sehr nett! Hast du nicht gemerkt, dass
> sich mehrere Leute Mühe gegben haben?
es tut mir leid, es war mir wirklich nicht bewusst, dass mein
Ton unfreundlich war.
Es war wirklich nett, dass sich so schnell mehrere Leute
zu dem Thema gemeldet haben.
Die Antworten haben mir aber bisher nicht geholfen.
Und damit diese Frage nicht als beantwortet gilt, muss
ich das doch mitteilen.
> Es hilft dir vielleicht, wenn du weisst, dass es wirklich
> keine allgemeine Lösung dafür gibt!
Warum sollte es die nicht geben?
Es wurden doch schon ganz andere Dinge berechnet.
Und ich bin mir sicher, dass es auch hier eine
allgemeie Lösung gibt.
> Wenn du bestimmte Pkt A B C D gibst, kann man dir
> vielleicht helfen, Oder Aufgaben laufen ja nicht so auf der
> Strasse rum und betteln: "Haste mal ne Lösung" Wenn du uns
> verrättst, woher sie kommt?
Also wirklich, jetzt wirst du aber unfreundlich.
Seit ca. der 8 Klasse habe ich kaum noch mit Zahlen in der
Schule gerechnet und an der Uni sowieso nicht mehr.
Die Lösung mit bestimmten Zahlen hilft mir nicht, wenn man
sie nicht verallgemeinern kann.
> Wenn du das letzte Link von Karl Pech wirklich
> aufmachst, findest du am Ende ein Applet, mit dem du jede
> konkrete Aufgabe lösen kannst!
Ich habe diesen Link aufgemacht.
Er liefert keine Lösung, sondern einen Algorithmus mit einen
Aufwand von O(n). Ich würde aber gerne die mathematische
Lösung wissen.
>
> Gruss leduart
>
Viele Grüße
jerela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:22 Do 31.03.2005 | | Autor: | Karl_Pech |
Hallo jerela,
> Die Lösung mit bestimmten Zahlen hilft mir nicht, wenn
> man
> sie nicht verallgemeinern kann.
>
> Ich habe diesen Link aufgemacht.
> Er liefert keine Lösung, sondern einen Algorithmus mit
> einen
> Aufwand von O(n). Ich würde aber gerne die mathematische
> Lösung wissen.
Was ist denn an einem Algorithmus "unmathematisch"? Die Herleitung für solche Algorithmen ist sogar sehr mathematisch und mindestens genauso schwer wie reine Mathematik (siehe z.B. cg-Verfahren aus der Numerik). Was Du willst, ist vermutlich eine Formel für dieses Problem. Aber nur für die allerwenigsten Probleme gibt es solche geschlossenen Lösungen.
Auf der Seite, die ich dir gegeben habe, gibt es übrigens den Quellcode für deren Applet (unter dem Link "applet source code" [mm] $\to$ [/mm] "RectangleFind.java"). Was will man mehr?
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:02 Do 31.03.2005 | | Autor: | jerela |
Hallo,
Es geht mir doch nicht darum möglichst viel mathematisches zu haben.
Die mathematischen Dinge, sind doch "nur" Beweise dafür, dass man bestimmte Dinge voraussetzen darf. Der Algorithmus ansich ist auch nur eine Näherung an das Problem.
Und das Problem was dort behandelt wird ist auch nicht exakt das Problem was ich habe. Es werden Dinge vorausgesetzt die ich nicht voraussetzen kann.
Bitte helft mit.
Ich bin sicher, dass es jemanden gibt, der mit mit einfachen Worten sagen kann, wie ich das Problem lösen kann.
Wie lautet also die Lösung zu meiner Aufgabe?
Viele Grüße
jerela
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:14 Sa 02.04.2005 | | Autor: | leduart |
Hallo,
>
> Es geht mir doch nicht darum möglichst viel mathematisches
> zu haben.
> Die mathematischen Dinge, sind doch "nur" Beweise dafür,
> dass man bestimmte Dinge voraussetzen darf.
Nein, das ist eigentlich nicht Mathematik. Sondern man macht Vorraussetzungen und beweist dann etwas. Wenn man die Mathe in der realen WQelt anwendet, überprüft man dann, ob die Vorruassetzungen erfüllt sind!
> Der Algorithmus ansich ist auch nur eine Näherung an das Problem.
> Und das Problem was dort behandelt wird ist auch nicht
> exakt das Problem was ich habe. Es werden Dinge
> vorausgesetzt die ich nicht voraussetzen kann.
Was kannst du nicht vorraussetzen? Ist dein Viereck konvex? könnte auch A=B sein?
Warum verrätst du uns nicht woher das Problem stammt?
Ist für dich die Formel [mm] r^{2}* \pi [/mm] für den Flächeninhalt des Kreises eine Lösung?
Für Mathematiker ist [mm] \pi [/mm] nur eine Abkürzung für eine reelle Zahl, die man durch verschiedene Algorithmen auf eine gewisse Genauigkeit kennt, aber nie genau kennt.
In diesem Sinne ist die Lösung in dem Link genauso exakt wie man den Kreisinhalt kennt!
Der Flächeninhalt eines gleichseitigen Dreiecks imit Seitenlänge 1 ist 0,25* [mm] \wurzel{3}, [/mm] sieht genau aus, aber dein Taschenrechner sagt dir die [mm] \wurzel{3} [/mm] auch nur auf 10 Stellen genau, Ein guter Computer vielleicht auf 20 Stellen oder mehr, aber nie genau. Um [mm] \wurzel{3} [/mm] auszurechnen braucht man einen Algorithmus!
>
> Bitte helft mit.
>
> Ich bin sicher, dass es jemanden gibt, der mit mit
> einfachen Worten sagen kann, wie ich das Problem lösen
> kann.
>
> Wie lautet also die Lösung zu meiner Aufgabe?
Fläche= [mm] \Phi(A;B;C;D) [/mm] dabei wird [mm] \Phi [/mm] durch einen Algorithmus bestimmt.
Das ist dicher nicht was du erwartest, Aber schreib doch mal ne falsche Formel mit A,B,C,D auf in der Art, wie du denkst, dass eine Lösung aussieht,die du erwartest!
Ich hab eben erst nachgesehen,dass du Student bist, also meine Ausführungen waren eher für eine SchülerIn gedacht, vielleicht hilft es doch?
Gruss lkeduart
> Viele Grüße
> jerela
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:52 So 03.04.2005 | | Autor: | jerela |
Hallo lkeduart
> Was kannst du nicht vorraussetzen? Ist dein Viereck
> konvex? könnte auch A=B sein?
Die Kanten vom Rechteck sollen, parallel zur x und y Achse sein,
ich Algorithmus wird vorausgesetzt, dass dieser Fall nicht gegeben sein muss.
Oder anderum, ich setzte voraus, dass die Kanten des Rechtecks parallel zur x-und y-Achse sein soll, was im Algorithmus nicht gefordert ist.
Ein Viereck muss nicht konvex sein.
Beispiel: A(0,0) B(0,10) C(10,0) D(5,5) wobei AB, BC, CD, DA sie Verbindungen sind.
Der Einfachheit halber wäre ich aber auch mit einen konvexen Viereck einverstanden, wenn es dafür eine für mich verständliche Lösung
geben würde.
> Warum verrätst du uns nicht woher das Problem stammt?
Dann müsste ich sehr viel über mich erzählen, was ich hier jetzt nicht machen möchte.
> Ist für dich die Formel [mm]r^{2}* \pi[/mm] für den Flächeninhalt
> des Kreises eine Lösung?
ja
> Für Mathematiker ist [mm]\pi[/mm] nur eine Abkürzung für eine
> reelle Zahl, die man durch verschiedene Algorithmen auf
> eine gewisse Genauigkeit kennt, aber nie genau kennt.
Ich bin kein Mathematiker und für mich ist Pi einen unendlichgroße Zahl.
Wenn ich mal einen Kreisinhalt berechne, entscheide ich dann von Fall zu Fall wieviele Stellen ich von Pi haben möchte.
> > Wie lautet also die Lösung zu meiner Aufgabe?
> Fläche= [mm]\Phi(A;B;C;D)[/mm] dabei wird [mm]\Phi[/mm] durch einen
> Algorithmus bestimmt.
Nicht ganz: Rechteck(A',B',C',D') = [mm]\Phi(A;B;C;D)[/mm] , wobei A',B',C',D' die vier Ecken des Rechtecks sind.
Also soweit war ich auch schon, obwohl ich ja nicht wirklich das Vertrauen zu dem Algorithmus habe.
Aber da dass nun der einzige Weg zu sein scheint, konzentriere ich mich jetzt mal auf den Algorithmus.
Ich habe also diese vier Punkte A, B, C, D.
Dann bestimme ich vier Ketten a, b, c, d
und was muss ich dann machen um auf die Punkte
A' B' C' D' zu kommen?
> Das ist dicher nicht was du erwartest, Aber schreib doch
> mal ne falsche Formel mit A,B,C,D auf in der Art, wie du
> denkst, dass eine Lösung aussieht,die du erwartest!
A' = ((x vom A + x von B)/2,(y vom A + y von B)/2 )
B' = ......
C' = .....
D' = ....
Ich möchte nochmal extra betonen, das dass nicht die Lösung ist.
Viele Grüße
jerela
|
|
|
| |
|
Hallo jerala,
An diesem Bild von informix möchte ich nochmals ansetzen.
Zur Lösung des Problems bietet sich meiner Meinung nach eine Fallunterscheidung an.
Wähle 3 Seiten des Vierecks aus.(Die Fallunterscheidung besteht darin das Du dasgleiche für alle Möglichen Kombinationen dieser 3 Seiten auch machen mußt). Dann hast Du die Nebenbedingung das 3 Eckpunkte des Rechtecks auf den Seiten des Vierecks liegen müssen. Der Flächeninhalt ergibt sich aus den 2 gegenüberliegenden Punkten. Nun gibt es 2 Möglichkeiten entweder das Extremmum liegt wie im Bild zu vermuten auf einem der Randpunkte(hier B). Dies müsstest Du jeweils checken. Oder Du kannst es mittels Lagrange Ansatz(Extrema mit Nebenbedingungen) bestimmen.
Für den Fall eines konkaven Vierecks müsstest Du noch eine weitere Fallunterscheidung hinzufügen. Nämlich den Fall das eine Seite des Rechtecks durch einen Punkt des Vierecks begrenzt ist.
viele Grüße
mathemaduenn
|
|
|
|
