Raute

Neue Frage »

CodeRonin Auf diesen Beitrag antworten »
Raute
Hallo,
ich habe da eine Frage zur Raute.
Bin eigentlich Programmierer und nicht so sehr Theoretiker, daher werde ich hier wahrscheinlich klingen wie ein Anfänger, aber habt bitte trotzdem Geduld mit mir Augenzwinkern .

Also, folgendes Problem:

Man nehme ein Koordinatensystem, beginnend bei 0/0, welches seinen Startpunkt links oben hat, sprich, die x-Koordinaten vergrößern sich gegen links, die y-Koordinaten nach unten hin.

Nun schreibe man in dieses Koordinatensystem eine Raute mit der Höhe 40 und der Breite 60 ein, sodass die Höhe Parallel zur y-Achse und die Breite parallel zur x-Achse sind (Sprich, keinerelei Rotation).

Hier das Basisproblem:

Gegeben seie der Punkt (xm/ym), welcher an einer Beliebigen Stelle im Koordinatensystem liegen darf. Es ist nun zu prüfen, ob er sich innerhalb besagter Raute befindet.

Mein Ansatz war der, dass ich die Raute in vier rechtwinkelige Dreiecke geteilt habe und über Verhältnisse (a/a1 = b/b1 --> x/xm = y/ym) die Y-Koordinate der Hypothenuse für das entsprechene x ausgerechnet habe.

Somit ergab sich, dass xm/ym in der Raute liegt, wenn
x =< rautenanfang + rautenbreite
x >= rautenanfang
y in abhängigkeit von x und der Lage des dreiecks, da bei den Unteren Dreiecken die Obergrenze des y-Wertes berechnet wird, bei den oberen Dreiecken die Untergrenze.

Bald habe ich gemerkt, dass diese Lösung sub-otpimal, da zu kompliziert ist, und habe mich auf die Geradengleichung y = kx + d besonnen, wobei x = xm, k, k, kann man berechnen, wobei man wahlweise
y = 40
x = 0
oder
x= 60
y = 0
einsetzt, da dies die Koordinatenpaare sind, welche in den Eckpunkten liegen.

Auch somit kann ich nach Bestimmung der Lage des Dreiecks die Ober/Untergrenze für ym bestimmen, also, ab wann es sich nicht mehr in der Raute befindet.

Leider ist auch diese Lösung kompliziert und langsam, daher bitte ich um Anregungen, es besser zu machen...
Danke,
CodeRonin
Marco_the_Chief Auf diesen Beitrag antworten »
RE: Raute
Grüß Dich,

Habe mir folgendes überlegt:

Spiegelst Du den Mittelpunkt der Raute an ihren Seiten, so muß ein Punkt, der in der Raute liegt immer näher an dem Mittelpunkt liegen, als an den gespiegelten Punkten:

=> Die Strecke vom Punkt zum Mittelpunkt < Strecke vom Punkt zu einem gespiegeltem Punkt
Leopold Auf diesen Beitrag antworten »

Mit Hilfe der Normalform einer Geradengleichung kann man überprüfen, in welcher der durch eine Gerade bestimmten Halbebenen ein Punkt liegt.

Ich verwende die folgenden Bezeichnungen:

M(u|v): Mittelpunkt der Raute
b,h: Breite bzw. Höhe der Raute
A,A': linker bzw. rechter Eckpunkt der Raute
B,B': unter bzw. oberer Eckpunkt der Raute

Dann gilt:

A ( u-½·b | v )
B ( u | v+½·b )
A' ( u+½·b | v )
B' ( u | v-½·b )

Und für die Geraden AB, BA', A'B', B'A erhältst du die folgenden Linearformen:

AB: 2h(x-u)-2b(y-v)+bh
BA': 2h(x-u)+2b(y-v)-bh
A'B': 2h(x-u)-2b(y-v)-bh
B'A: 2h(x-u)+2b(y-v)+bh

Setzt du nun in einen der Terme für x,y die Koordinaten eines beliebigen Punktes der Ebene ein, so ergibt sich 0, wenn der Punkt auf der entsprechenden Geraden liegt und ein Wert ungleich 0 andernfalls. Und wenn Punkte in derselben durch die Gerade bestimmten Halbebene liegen, dann haben die Termwerte dasselbe Vorzeichen.

Wenn du nun einen Punkt P hast, so mußt du also nur testen, ob für M(u|v) und für P(s|t) dasselbe Vorzeichen herauskommt, wenn du die Koordinaten für x bzw. y einsetzt, und zwar bei allen vier Geraden.

Ich empfehle, die Koordinaten aller Punkte sowie b und h als Gleitkommazahlen zu behandeln und alle Rechnungen mit Gleitkommazahlen durchzuführen. (Und nur fürs Zeichen sollten dann die Gleitkommazahlen in Integer-Werte gerundet werden.) So hast du die größte Flexibilität, wenn du z.B. mit "krummen Koordinaten" rechnen willst.

Edit:

Und da man die Längen b,h ja >0 annehmen kann, ergibt sich beim Einsetzen der Koordinaten von M

bei AB: bh>0
bei BA': -bh<0
bei A'B': -bh<0
bei B'A: bh>0

Deshalb kannst du mit einer Booleschen Variablen

LiegtImInnern := (2h(x-u)-2b(y-v)+bh>0) and (2h(x-u)+2b(y-v)-bh<0) and (2h(x-u)-2b(y-v)-bh<0) and (2h(x-u)+2b(y-v)+bh>0)

(wobei x,y die Koordinaten eines Punktes P sind)

leicht das Gewünschte überprüfen. Und wenn du die Hilfsgrößen x'=2h(x-u), y'=2b(y-v), z'=bh einführst, schreibt es sich noch eleganter:

LiegtImInnern : = (x'-y'+z'>0) and (x'+y'-z'<0) and (x'-y'-z'<0) and (x'+y'+z'>0)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »