rechteck als determinante < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:46 So 09.08.2009 | | Autor: | cubase |
servus
unter http://newsgroups.derkeiler.com/Archive/De/de.sci.mathematik/2006-05/msg00488.html
habe ich einen interessanten ansatz gesehen, wie man überprüfen kann ob ein beliebiger punkt p in einem rechteck mit den punkten a, b, c d liegt. die antwort in diesem forum war sehr kurz und mich interessiert eigentlich mehr der hintergrund. wie kann man ein rechteck als determinate schreiben bzw welche mathematische funktion steckt dahinter?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:13 So 09.08.2009 | | Autor: | Andrey |
Da steckt nichts weiter dahinter, als die Interpretation der Determinante als orientiertes Volumen des aufgespannten n-Spats.
Berechnet man die Determinante $det( (a-p),(b-p) )$, dann betrachtet man ja im Prinzip das Volumen des durch Vektoren (a-p) und (b-p) aufgespannten Parallelograms: dieser ist positiv, wenn (a-p) "im uhrzeigersinn rechts von (b-p)" ist, wenn man das ins "übliche" Koordinatensystem einzeichnet. Wenn die ganze folge dieser determinanten durchgehend positiv ist, dann heißt es, dass die eckpunkte a,b,c,d... alle gegen den uhrzeigersinn bzgl. p ausgerichtet sind, die umlaufzahl um p ist größer 0, also ist p in diesem berandeten konvexen Polygon drin.
Alternativ könnte ich da noch die geometrisch wesentlich einfachere Methode vorschlagen: Seien a,b,c drei ecken des parallelograms, und p ein punkt.
Berechne mit
[mm] $\frac{1}{(a_1-c_1)(b_2-c_2)-(b_1-c_1)(a_2-c_2)}\pmat{b_2-c_2 & -b_1+c_1 \\ -a_2+c_2 & a_1-c_1 }\vektor{p_1-c_1\\p_2-c_2}$
[/mm]
die "lokalen koordinaten" von p im parallelogramm. Wenn beide komponenten des ergebnisses in [0,1] liegen, liegt p natürlich im parallelogramm drin, ansonsten nicht. Will man statt des parallelogramms nur die hälfte, also nur das dreieck abc, prüfe man zusätzlich, ob die summe der beiden komponenten kleiner 1 ist.
Diese methode hat imho den vorteil, dass wenn man mehrere punkte testen muss, man die inverse matrix nur einmal zu berechnen hat, und dann muss man nur noch die ganzen punkte einsetzten, da muss man nicht jedes mal alles von anfang an berechnen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:15 So 09.08.2009 | | Autor: | felixf |
Hallo zusammen
> Alternativ könnte ich da noch die geometrisch wesentlich
> einfachere Methode vorschlagen: Seien a,b,c drei ecken des
> parallelograms, und p ein punkt.
> Berechne mit
>
> [mm]\frac{1}{(a_1-c_1)(b_2-c_2)-(b_1-c_1)(a_2-c_2)}\pmat{b_2-c_2 & -b_1+c_1 \\ -a_2+c_2 & a_1-c_1 }\vektor{p_1-c_1\\p_2-c_2}[/mm]
>
> die "lokalen koordinaten" von p im parallelogramm.
Dies funktioniert natuerlich nur, wenn das auch wirklich ein Parallelogramm ist, und nicht ein beliebiges Viereck. Die Determinanten-Methode funktioniert naemlich auch fuer beliebige konvexe Vierecke und nicht nur fuer Parallelogramme.
> Diese methode hat imho den vorteil, dass wenn man mehrere
> punkte testen muss, man die inverse matrix nur einmal zu
> berechnen hat, und dann muss man nur noch die ganzen punkte
> einsetzten, da muss man nicht jedes mal alles von anfang an
> berechnen.
Bei der Determinanten-Methode kann man auch einiges Vorberechnen; wenn man [mm] $p_1$ [/mm] und [mm] $p_2$ [/mm] jeweils ausklammert, muss man dort ebenfalls nur sehr wenig berechnen. Es bleiben trotzdem doppelt so viele Multiplikationen wie bei Andreys Methode, dafuer funktioniert sie halt auch bei allgemeinen konvexen Polygonen.
LG Felix
|
|
|
|
