Rechteck im Viereck
Christian S
hat jemand von euch einer Idee, wie man das flächengrößte Rechteck in einem
Viereck
finden kann, von dem man die einzelnen Eckpunkte kennt?
Ich vermute, daß es mit der Integralrechnung funktionieren könnte, finde
bislang aber
keinen gescheiten Ansatz.
Christian Schmitz
Hero Wunders
> hat jemand von euch einer Idee, wie man das flächengrößte Rechteck
> in einem Viereck
> finden kann, von dem man die einzelnen Eckpunkte kennt?
Ich habe das Gefühl, dass du etwas Anderes meinst als du schreibst.
Wenn du das meinst was du schreibst, ist die Lösung:
Das flächengrößte Rechteck in einem Viereck ist das Viereck selbst.
herojoker
Rainer Rosenthal
Hero Wunders wrote
> Das flächengrößte Rechteck in einem Viereck
> ist das Viereck selbst.
Sind Trapeze keine Vierecke?
Rainer Rosenthal
r.ros...@web.de
Hero Wunders
> > Das flächengrößte Rechteck in einem Viereck
> > ist das Viereck selbst.
>
> Sind Trapeze keine Vierecke?
Urgs...
Hatte irgendwie nur *Quadrate* im Kopf...
*schlaf*
herojoker
Rainer Rosenthal
Christian S wrote
> wie man das flächengrößte Rechteck in einem Viereck
> finden kann, von dem man die einzelnen Eckpunkte kennt?
Die Aufgabe sieht spannend aus. Woher kommt sie?
Ich habe mal ein paar "sehr beliebige" Vierecke
gezeichnet und dabei gar den Verdacht gewonnen,
dass es evtl. Vierecke ohne Innenrechteck geben
könne. Hmm... mal suchen *wedel*
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
> den Verdacht gewonnen, dass es evtl. Vierecke
> ohne Innenrechteck geben könne.
Schmarr'n ...
So schief kann man ein Viereck gar nicht zeichnen,
dass nicht wenigstens eine Seite s existiert, der
eine Ecke E gegenüberliegt.
Dann muss man nur eine Parallele zu s zeichnen, die
genügend dicht bei E das Viereck schneidet. Nenne
die Schnittpunkte P und Q und zeichne die Senkrechten
dazu, die bei P' und Q' durch s gehen.
Dann bilden P, P', Q, Q' ein Rechteck, das dem Vier-
ecke einbeschrieben ist.
Also gut, dann kann's ja weitergehen mit der Suche
nach dem grössten Rechteck.
Aber nicht mehr jetzt :-)
Rainer Rosenthal
r.ros...@web.de
Rainer Willis
> Hero Wunders wrote
>
> > Das flächengrößte Rechteck in einem Viereck
> > ist das Viereck selbst.
>
> Sind Trapeze keine Vierecke?
Hallo Rainer,
nicht nur Trapeze, ich hatte (wie du vermutlich auch) den OP so
verstanden, dass er beliebige Vierecke meint, womit seine Frage nicht
mehr trivial ist. Wie ist es z.B. bei einem (Affin-)drachen?
Meine Idee wäre, sich die kürzeste Seite auszusuchen und darauf "bis
zur Grenze" ein Rechteck zu konstruieren. Andererseits könnte ein
"verkanntet" einbeschriebenes Rechteck trotzdem größer sein.
Just my two cents.
Gruß, Rainer
--
für emails net statt de
Rainer Rosenthal
Rainer Willis wrote
> nicht nur Trapeze,
das war ein dezenter Hinweis, dass es noch
andere Vierecke gibt. Damit HW nicht so lange
suchen musste, habe ich schon mal ein
Beispiel gegeben.
Ja, das Thema ist hübsch. Vielleicht lernen
wir noch vom OP, woher und wozu es ist.
Rainer R.
Florian Schaudel
54909.news.uni-berlin.de:
> Rainer Rosenthal schrieb
>
>> den Verdacht gewonnen, dass es evtl. Vierecke
>> ohne Innenrechteck geben könne.
>
> Schmarr'n ...
> So schief kann man ein Viereck gar nicht zeichnen,
> dass nicht wenigstens eine Seite s existiert, der
> eine Ecke E gegenüberliegt.
> Dann muss man nur eine Parallele zu s zeichnen, die
> genügend dicht bei E das Viereck schneidet. Nenne
> die Schnittpunkte P und Q und zeichne die Senkrechten
> dazu, die bei P' und Q' durch s gehen.
> Dann bilden P, P', Q, Q' ein Rechteck, das dem Vier-
> ecke einbeschrieben ist.
Da sieht man mal wieder, dass nachts um 2 Denken noch schwieriger ist, als
um 1!
Es ist nämlich in der Tat so, dass man in einige nicht-konvexe 4-ecke kein
Rechteck einbeschreiben kann, zumindest wenn man von einem einbeschriebenen
Rechteck verlangt, dass es:
1. Ein Rechteck mit Flächeninhalt >0 ist
2. Alle Ecken dieses Rechtecks auf Kanten des umgebenden 4-Ecks liegen
3. Die Fläche des Rechtecks vollsändig im Umgebenden 4-Eck enthalten ist
Bei Deiner "Konstruktionsvorschrift" geht bei manchen nicht-konvexen 4-
Ecken die Regel 3 schief.
Am ehesten diskutieren könnte man über Regel 2: Wenn man zulassen würde,
dass bei solch einem einbeschriebenen Rechteck eine Ecke "in der Luft"
hängt, hätte natürlich jedes 4-Eck mit Fläche>0 auch ein einbeschriebenes
Rechteck mit Fläche > 0
Gruss,
Florian
Christian Möller
> "Rainer Rosenthal" <r.ros...@web.de> wrote in
> news:bt2gs1$2krok$1@ID- 54909.news.uni-berlin.de:
>
>> Rainer Rosenthal schrieb
>
> kein Rechteck einbeschreiben kann, zumindest wenn man von einem
> einbeschriebenen Rechteck verlangt, dass es:
>
> 1. Ein Rechteck mit Flächeninhalt >0 ist
> 2. Alle Ecken dieses Rechtecks auf Kanten des umgebenden 4-Ecks liegen
Ich würde allenfalls fordern, dass mindestens eine Ecke des Rechtecks
auf Kanten des umgebenden 4-Ecks liegt. Dann gibt es offensichtlich
immer ein Innen-Rechteck. Nun ist aber immer noch von den ach so
vielen das Größte zu finden...
MfG Christian
Florian Schaudel
18756.news.uni-berlin.de:
>> 1. Ein Rechteck mit Flächeninhalt >0 ist
>> 2. Alle Ecken dieses Rechtecks auf Kanten des umgebenden 4-Ecks liegen
>
> Ich würde allenfalls fordern, dass mindestens eine Ecke des Rechtecks
> auf Kanten des umgebenden 4-Ecks liegt. Dann gibt es offensichtlich
> immer ein Innen-Rechteck. Nun ist aber immer noch von den ach so
> vielen das Größte zu finden...
Es ist sehr simpel zu zeigen, dass beim maximalen "einbeschriebenen"
Rechteck mindestens 3 der Ecken auf Kanten des umgebenden 4-Ecks liegen.
Gruss, Florian
Christian S
da die Frage nach dem Woher aufkam: Ich suche auf eingescannten
Leiterplatten die
Körper der Bauelemente. Durch einen Farbvergleich finde ich diese zwar im
Groben,
aber diese Formen, die dort entstehen, kann man einen Benutzer nicht
zumuten.
Da ich nun weiß, daß die Formen rechteckig sind, wollte ich das BESTE
Rechteck aus
den Konturen herausoptimieren. Mittels einer Houghtransformation gewinne ich
schon
mal das beste Viereck. Aus diesem möchte ich dann das größte Rechteck
gewinnen.
Wie schon vermutet, wird wahrscheinlich eine Ecke nie auf dem Viereck
liegen.
Meine erste Lösungsidee war, daß eine Linie zwischen zwei Seiten laufen
lasse und die restlichen berechne. Das sollte in einer Extremwertaufgabe
ausarten. Dummerweise ist es nicht klar, zwischen welchen Seiten man eine
Linie laufen lassen muß. Und alle durchzuprobieren habe ich keine Lust.
Der zweite Ansatz wäre, Nebenbedingungen auszustellen, die besagen, daß alle
x- bzw.y-Koordinaten des Rechtecks zwischen den linken und rechten Seite
bzw. zwischen den oberen und unteren Seiten liegen müssen. Zudem müßte man
die Eigenart des Rechtecks als NB einbringen, daß es eben rechte Ecken hat.
Puh, ...
Ich gebe aber noch nicht auf.
Also: Viereck (x1,y1);(x2,y2);(x3;y3);(x4;y4); Punkte rechtsherum gezählt.
Begrenzungen:
xl=x1+txl*(x4-x1)
xu=x2+txu*(x3-x2)
xl<=x<=xu; für alle Ecken des Rechtecks
yl=y1+tyl*(y2-y1)
yh=y3+tyh*(y4-y3)
yl<=y<=yu; für alle Ecken des Rechtecks
.....
Alternativ könnte man die konvexe Hülle des Vierecks berechnen, zu dieser
müßte dann eine kleinstes eingeschriebenes Rechteck zu finden sein.
Aber warum mit Kanonen auf Spatzen schiessen?
Ach ja, und da nachher das der Computer ausrechnen soll, müßte die Lösung
so
aussehen, daß man nicht 1000 Sonderfälle berücksichten muß (Tippfaul).
Christian
Christian S
> Rechteck mindestens 3 der Ecken auf Kanten des umgebenden 4-Ecks liegen.
Wenn du das in weniger als einer Stunde schaffst, schenke ich dir ein
Rechteck.
Hier als Vorgeschmack schon mal eine Ecke !_
Christian
Klaus Nagel
Christian S schrieb:
>>Es ist sehr simpel zu zeigen, dass beim maximalen "einbeschriebenen"
>>Rechteck mindestens 3 der Ecken auf Kanten des umgebenden 4-Ecks liegen.
>>
>
> Wenn du das in weniger als einer Stunde schaffst, schenke ich dir ein
> Rechteck.
>
Ich hatte versucht, die Behauptung zu beweisen, und war so weit gekommen:
Wenn zwei Ecken des Rechtecks im Inneren des Vierecks liegen, dann
läßt sich das Rechteck vergrößern:
1. Fall. Zwei benachbarte Ecken A und B. Die Seite AB wird parallel
verschoben.
2. Fall. Gegenüberliegende Ecken A und C. B und D bleiben fest, A und C
werden auf dem Umkreis des Rechtecks (Thaleskreis) so verschoben, daß
die Rechtsfläche wächst.
Dann merkte ich, daß sich im Fall 2 das Rechteck nicht vergrößern läßt,
wenn es ein Quadrat ist. Dieses scheint mir ein Gegenbeispiel zu sein:
Eine echte Raute, in die ein Quadrat so eingezeichnet ist, daß die
kürzere Rautendiagonale auch Diagonale des Quadrats ist.
Gruß,
Klaus Nagel
Rainer Rosenthal
Klaus Nagel wrote
>
> Dann merkte ich, daß sich im Fall 2 das
> Rechteck nicht vergrößern läßt, wenn es
> ein Quadrat ist. Dieses scheint mir ein
Hallo Klaus,
das freut mich, dass Du bei diesem hübschen Thema
"anbeisst". Im Selberarbeiten bin ich ja nicht so
toll(*), aber dieses Thema ruft doch geradezu:
Genetischer Algorithmus!
So skeptisch ich als Möchtegern-Philosoph diesem
Konzept gegenüberstehe, so sehr haben mich doch
Deine Simulationen zum Maschendrahtzaun erfreut:
http://home.t-online.de/home/nagel.klaus/zaundir/zaun.htm
Ich sehe schon dies kleine sich aufblähende und
zappelnd mal länger mal breiter werdende grüne Reckteck
in dem rot umrandeten (allgemeinen) Viereck, dessen
Eckpunkte der erfreute User locker mit dem Mauszeiger
platziert. Daneben sieht man den aktuellen Flächeninhalt
und den bisher maximal erreichten. Eine Vision!
(*) Durchbruch bei der Jungfrau-und-Unhold-Aufgabe
AKA "Fox and Duck":
Message-ID: <bt28vh$2julv$1...@ID-54909.news.uni-berlin.de>
Gruss,
Rainer
P.S. Bitte gib doch bei Deinen Postings immer auch Deine
URL mit an. Auf der Suche nach derselben habe ich allerdings
was Schönes entdeckt: Gauss.pdf - (SiehTeXt gut aus!)
Rainer Rosenthal
Rainer Rosenthal wrote
> ... haben mich doch Deine Simulationen zum Maschen-
> drahtzaun erfreut:
> http://home.t-online.de/home/nagel.klaus/zaundir/zaun.htm
Kleiner Nachtrag: Habe gleich nochmal damit gespielt und
schon nach ein paarmal "100 Schritte" was sehr Zepp-ähnliches
bekommen. Es wäre eine GUTE Sache, wenn in dem einleitenden
Kommentar oder sichtbar neben dem Applet
die theoretische Obergrenze sichtbar
wäre, die ja 15468.55911 Euro beträgt,
wie ich in Wolfgang Kirschenhofers PDF gerade nochmal nachgelesen
habe. ( Dies PDF kann man jederzeit gerne bei mir anfordern, oder
wohl auch beim Autor selbst. Es sieht danach aus, als würde
auch 2004 wieder ein Zepp-Jahr werden :-)
Gruss,
Rainer
Florian Schaudel
online.de:
> Dann merkte ich, daß sich im Fall 2 das Rechteck nicht vergrößern läßt,
> wenn es ein Quadrat ist. Dieses scheint mir ein Gegenbeispiel zu sein:
> Eine echte Raute, in die ein Quadrat so eingezeichnet ist, daß die
> kürzere Rautendiagonale auch Diagonale des Quadrats ist.
Leider richtig: Genaugenommen ist es dann ein Gegenbeispiel, wenn die
kleinere Diagonale länger als 1/2 der größeren Diagonale ist.
Gruss, Florian
Hermann Jurksch
> Ach ja, und da nachher das der Computer ausrechnen soll, müßte die Lösung
> so
> aussehen, daß man nicht 1000 Sonderfälle berücksichten muß (Tippfaul).
Gehe es doch pragmatisch an und suche eine gute Näherung. Das größte
Rechteck mit vorgegebener Seitenrichtung zu finden ist ja trivial, und
der Computer ist schnell ...
MfG
Hermann
Christian S
> Rechteck mit vorgegebener Seitenrichtung zu finden ist ja trivial, und
> der Computer ist schnell ...
Das habe ich in meiner Not bereits getan, allerdings ist der Rechner niemals
schnell genug. Abgesehen davon, daß er noch anderes zu tun hat, sollte die
Auswertung von 50000 Meßfeldern nicht wesentlich länger als 2 sec dauern.
Das dumme an guten Näherungen ist, das sie eben nur gut und nicht perfekt
sind.
Ich darf nur 10 Pseudofehler pro 1Mio Messungen haben. Das entspricht einem
auf 5E9 Messfelder.
Das schlimmste an guten Näherungen aber ist, sie sind nicht immer
nachvollziehbar, meistens funktionieren sie gut, aber manchmal ticken sie
eben aus. Das führt dazu, daß man geneigt ist, bei jedem Austicken etwas
beizufrickeln, was wiederum zur Folge hat, daß im nachhinein nichts mehr
funktioniert.
Christian Schmitz
Rainer Rosenthal
Christian S wrote
> Das führt dazu, daß man geneigt ist, bei jedem
> Austicken etwas beizufrickeln, was wiederum zur
> Folge hat, daß im nachhinein nichts mehr funktioniert.
Das Wort zum Tage.
Stimmt. Und nun also: Mathematik ist gefragt :-)
Schön genug ist das Thema ja.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Klaus G
> > Hero Wunders wrote
> >
> Hallo Rainer,
>
> nicht nur Trapeze, ich hatte (wie du vermutlich auch) den OP so
> verstanden, dass er beliebige Vierecke meint, womit seine Frage nicht
> mehr trivial ist. Wie ist es z.B. bei einem (Affin-)drachen?
> Meine Idee wäre, sich die kürzeste Seite auszusuchen und darauf "bis
> zur Grenze" ein Rechteck zu konstruieren. Andererseits könnte ein
> "verkanntet" einbeschriebenes Rechteck trotzdem größer sein.
Was bedeutet das?
> ...
> Gruß, Rainer
Klaus G.
--
semf is alle
Rainer Rosenthal
Klaus G fragte
> > "verkanntet"
> ^^^^^^^^^^^^^???
>
> Was bedeutet das?
>
O Mann, ey. Noch nie 'n verkanntet Jenie jesehn?
Ernsthafter Nachsatz:
Habe das Thema gerade mit folgenden Worten in sci.math
untergebracht:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Let me translate a nice question from de.sci.mathematik,
for which we still don't have an answer.
Given a quadrilateral Q with corners A,B,C,D in that
order, i.e. with sides AB, BC, CD, DA.
How to find the largest rectangle R, such that R is
completely within Q?
My feeling is, that one has to distinguish between
a lot of cases, regarding the shape of Q. So we
need clever algorithms for shape-classification,
followed by some rules for the computation in each
class.
There are strong time constraints, as I learned.
The classification idea itself is mathematical stuff,
I believe. The rest will be better sought for in some
comp.sci.xxxx?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Bin morgen unterwegs, kann also nicht berichten, ob da
was kommt. Bitte selber mal schauen, wen's interessiert.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Rainer Willis
[Ich schrieb]
> > "verkanntet" einbeschriebenes Rechteck trotzdem größer sein.
> ^^^^^^^^^^^^^???
>
> Was bedeutet das?
Hallo Klaus,
lol, ist mir auch aufgefallen, leider zu spät.
Obwohl: HW hat ja gezeigt, dass es auch verkannte Rechtecke gibt ... :-)
Gruß, Rainer
--
email: net statt de
Hermann Jurksch
>> Gehe es doch pragmatisch an und suche eine gute Näherung. Das größte
>> Rechteck mit vorgegebener Seitenrichtung zu finden ist ja trivial, und
>> der Computer ist schnell ...
> Das dumme an guten Näherungen ist, das sie eben nur gut und nicht perfekt
> sind.
> Ich darf nur 10 Pseudofehler pro 1Mio Messungen haben. Das entspricht einem
> auf 5E9 Messfelder.
Dann muß Du doch mehr Zeit investieren :-)
> Das schlimmste an guten Näherungen aber ist, sie sind nicht immer
> nachvollziehbar, meistens funktionieren sie gut, aber manchmal ticken sie
> eben aus. Das führt dazu, daß man geneigt ist, bei jedem Austicken etwas
> beizufrickeln, was wiederum zur Folge hat, daß im nachhinein nichts mehr
> funktioniert.
Was führt zu Deinem Glauben, die exakte Lösung wäre zwangsläufig numerisch
stabil?
MfG
Hermann
Christian Schmitz
> stabil?
Ich glaube zwar, aber ich glaube, daß hat nichts mit Glauben zu tun.
Christian
Alfred Heiligenbrunner
> Hallo,
> da die Frage nach dem Woher aufkam: Ich suche auf eingescannten
> Leiterplatten die
> Körper der Bauelemente. Durch einen Farbvergleich finde ich diese zwar im
> Groben,
> aber diese Formen, die dort entstehen, kann man einen Benutzer nicht
> zumuten.
> Da ich nun weiß, daß die Formen rechteckig sind, wollte ich das BESTE
> Rechteck aus
> den Konturen herausoptimieren. Mittels einer Houghtransformation gewinne ich
> schon
> mal das beste Viereck. Aus diesem möchte ich dann das größte Rechteck
> gewinnen.
Warum ist das _größte_ _einbeschriebene_ Rechteck das beste?
Kannst Du für deine konkrete Aufgabe nicht genausogut ein zum Viereck
flächengleiches Rechteck verwenden? (Ev. mit gleicher längster Seite
wie das Viereck.)
Christian Schmitz
> Warum ist das _größte_ _einbeschriebene_ Rechteck das beste?
> Kannst Du für deine konkrete Aufgabe nicht genausogut ein zum Viereck
> flächengleiches Rechteck verwenden? (Ev. mit gleicher längster Seite
> wie das Viereck.)
Das Viereck entsteht durch Störungen am äußeren Rand des Rechtecks. Das
eingeschriebene Rechteck scheint das richtige zu sein. (Zumindestens nach
dem, was ich so beobachte). Einen mathematischen Beweiß muß ich schuldig
bleiben.
Christian