Berechnen von Winkeln zwischen 2 Punkten...
-
Im Zweifel der Nullpunkt, d.h. Punkte als Vektoren verstehen. Dabei gilt:
cos <)= (a, b) = (a * b) / (|a| * |b|)...wobei a * b das Skalarprodukt der Vektoren a und b bedeutet und |a| die Länge des Vektors a mit dem selben Skalarprodukt.
Ich stelle mir das (für Schulmathematiker, also mit Skalarprodukt = Einheitsmatrix) etwa so vor:
typedef struct { double x; double y; } vektor; double skalarprodukt(vektor a, vektor b) { return a.x * b.x + a.y * b.y; } double vek_laenge(vektor a) { return sqrt(skalarprodukt(a, a)); } double vek_winkel(vektor a, vektor b) { return acos(skalarprodukt(a, b) / (vek_laenge(a) * vek_laenge(b))); }Code ungetestet. Tippfehler dürfen ggf. entfernt werden.
-
DirkB schrieb:
Die Funktion
atan2()ist für solche Sachen deutlich besser geeignet.Da spielt es auch keine Rolle wenn
ptr[k].x == minxist. Dann teilst du durch 0 und buffer wird unendlich, was das1.#IND00dann auch bedeutet.Als Vorgabe wurde uns die Funktion atan() gegeben, da kann ich leider nichts machen
Aber fuer mich persoenlich, wie wende ich denn die Funktion an? In die Funktion muss ja ein x und ein y Wert eingegeben werden, habe aber bei 2 Punkten 2 x und 2 y Werte .Kann ich die Aufgabe denn ueberhaupt nur mit atan() vernuenftig loesen ?
Und ja es war wieder eine lange Nacht, habe das vergessen umzuaendern, habe mittlerweile degrees genommen, so will es der Herr naemlich auch , hehe
@ Berniebutt, naja wenn ich 2 Punkte habe kann ich doch ein Dreick zeichnen und wenn ich dann y2 - y1 / x2 - x1 rechne und davon den arctan ziehe bekomme ich den Winkel
Hier nochmal der editierte Code. Den letzten Codefetzen habe ich mir noch nicht angeschaut, mache ich aber nachher. Danke schonmal dafuer!
/***************************************************************/ /* Programmer: Micha Hobert */ /* */ /* Program 14: Lowermost and Leftmost */ /* */ /* Approximate completion time: 5 hours */ /***************************************************************/ #include <stdio.h> #include <stdlib.h> #include <math.h> #define PI (3.141592653589793) typedef struct { double x; double y; }location; void angle ( location ptr[] , int n, double minx, double miny) { double buffer; double result; int k = 0; while ( k < n-1 ) { /* printf("ptrx %f minx %f ptry %f miny %f\n",ptr[k].x,minx,ptr[k].y,miny);*/ buffer = (ptr[k].y-miny) / (ptr[k].x-minx); result = atan ( buffer ) * 180 / PI; k++; if ( buffer == 0.0 ){ printf ( "The angle between Lowermost-Leftmost and point %d is 90 degrees.\n\n ",k ); } else printf ( "The angle between Lowermost-Leftmost and point %d is %f degrees.\n\n ",k ,result); } } void vector ( location ptr[] , int n ) { int r; int j; double miny; double minx; minx = ptr[0].x; miny = ptr[0].y; for (j=0; j<=n-1; j++){ if (ptr[j].y<miny){ miny=ptr[j].y; minx=ptr[j].x; while (r<=n-1){ if ( ptr[r].x < minx ){ miny=ptr[r].y; minx=ptr[r].x; break; } } } } printf( "The Lower Most, Left Most Point is: x = %f and y = %f\n", minx,miny ); angle ( ptr, n, minx, miny ); } int main ( ) { int n; location *ptr; int i=0; FILE *fin; fin = fopen ( "points.txt", "r"); fscanf ( fin, "%d", &n ); ptr = malloc ( n * sizeof(location) ); while(i <= n-1 ){ fscanf(fin, "%lf%lf", &ptr[i].x,&ptr[i].y); i++; } vector ( ptr , n ); return 0; }
-
Isengo schrieb:
Aber fuer mich persoenlich, wie wende ich denn die Funktion an? In die Funktion muss ja ein x und ein y Wert eingegeben werden, habe aber bei 2 Punkten 2 x und 2 y Werte .
// statt buffer = (ptr[k].y-miny) / (ptr[k].x-minx); result = atan( buffer ) * 180 / PI; // nimmt man result = atan2( ptr[k].y-miny , ptr[k].x-minx) * 180.0 / PI;90° hast du aber wenn buffer Unendlich wird. Du mußt vorher überprüfen ob
ptr[k].x-minxgegen 0.0 geht.Wenn buffer == 0.0 ist wird meist
ptr[k].y-min0.0 sein und somit ergibt das 0°.
-
Alles klar ! Hat mit der atan2() auch super geklappt
Bin jetzt gerade mal wieder an einem kritischen Punkt angelangt, grhhhh. Es ist schon wieder 1:30 in der Nacht, werde aber wohl bald zu Bett gehen. Die Aufgabenstellung ist folgende :
Program 19: Quick Sort Them Thetas
In class I showed you how to calculate the angle theta that is formed by using the lowest most, left most point as the reference point. So please read in n points from a file. Find the lowest most, left most point, and then calculate the
thetas. After you calculate the thetas, please sort the points in increasing angle. The lowest most left most point is the first point. A file, whose name is given in argv[1], contains a value n. It is then followed by n lines. Each line
contains an x value and a y value. You may assume that no point is duplicated.Also sortiert habe ich sie jetzt schon alle, allerdings habe ich ueberlesen das er die X und Y Werte in der Datei stehen haben moechte und nicht die Winkel Thetas. Fuer mich jetzt bloed weil ich mich schon wie ein Doofie gefreut hab das ich fertig bin. Muss ich da mit einem gemallocten Array arbeiten , also
double *ptr; ptr = malloc ( n * sizeof ( location ) )Und das dann in die Funktion angle einbringen ? Wie wuerdet ihr das am geschicktesten loesen. Ich bin derzeit ueberfragt, habe etwas den Ueberblick verloren um ehrlich zu sein
Hier nochmal der fertige Code, ich weiss das es noch viel zu viel ausgibt ( printf ), aber das hilft mir ganz gut die Schritte zu verfolgen und die Werte zu ueberpruefen...
/***************************************************************/ /* Programmer: Micha Hobert */ /* */ /* Program 14: Sort them Thetas */ /* */ /* Approximate completion time: 10+ hours */ /***************************************************************/ #include <stdio.h> #include <stdlib.h> #include <math.h> #define PI (3.141592653589793) void swap ( double *a, double *b ){ double temp; temp = *a ; *a = *b; *b = temp; } void printfirstpartofarray(FILE *name, double ptr2[], int n){ int i, j=0 ; while ( j <= n-1 ){ fprintf(name,"%f\n", ptr2[j]); j++; } printf("\n"); for ( i = 0 ; i < n ; i++) printf("%f\n", ptr2[i]); } void quick_sort ( double ptr2[], int low, int high){ int i, j , pivot; if ( high <= low) return; i = low - 1; j = high ; pivot = ptr2[high]; while (1) { do i = i + 1; while ( ( i < high ) && ( ptr2[i] < pivot)); do j = j - 1; while ( ( j >= low) && ( ptr2[j] > pivot )); if ( i >= j) break; swap ( &ptr2[i], &ptr2[j]); } swap(&ptr2[i], &ptr2[high]); quick_sort ( ptr2, low, i-1); quick_sort (ptr2, i+1, high); } /**********************************************************************/ typedef struct { double x; double y; }location; void angle ( FILE *name, location ptr[] , int n, double minx, double miny) { double buffer; double result; int k = 0; double *ptr2; ptr2 = malloc (n * sizeof (double) ); while ( k <= n-1 ) { buffer = (ptr[k].y-miny) / (ptr[k].x-minx); result = atan ( buffer ) * 180 / PI; if ( ptr[k].y-miny == 0.0){ printf("The angle between Lowermost-Leftmost and point %d is 0.000000 degrees.\n\n",k); ptr2[k] = 0.0; } else{ if ( ptr[k].x-minx == 0.0 ){ printf("The angle between Lowermost-Leftmost and point %d is 90.000000 degrees.\n\n",k); ptr2[k] = 90.0; } else { printf ("The angle between Lowermost-Leftmost and point %d is %f degrees.\n\n ",k ,result); ptr2[k] = result; } } k++; } quick_sort(ptr2,0,n-1); printfirstpartofarray(name,ptr2, n); } void vector (FILE *name, location ptr[] , int n ) { int r; int j; double miny; double minx; minx = ptr[0].x; miny = ptr[0].y; for (j=0; j<=n-1; j++){ if (ptr[j].y<miny){ miny=ptr[j].y; minx=ptr[j].x; while (r<=n-1){ if ( ptr[r].x < minx ){ miny=ptr[r].y; minx=ptr[r].x; break; } } } } printf( "The Lower Most, Left Most Point is: x = %f and y = %f\n\n", minx,miny ); angle (name, ptr, n, minx, miny ); } int main (int argc, char *argv[] ) { int n; location *ptr; int i=0,j=0; FILE *name, *fin; fin = fopen ("points.txt", "r"); fscanf ( fin, "%d", &n ); name = fopen (argv[1], "w+"); fprintf (name, "%d\n", n ); ptr = malloc ( n * sizeof(location) ); while(i <= n-1 ){ fscanf(fin, "%lf%lf", &ptr[i].x,&ptr[i].y); i++; } vector (name, ptr , n ); return 0; }
-
Isengo schrieb:
@ Berniebutt, naja wenn ich 2 Punkte habe kann ich doch ein Dreick zeichnen
Hut ab, ich brauch dafür 3 Punkte.
-
@ Belli
Ganz einfache Geometrie:
2 Punkte --> Zweick
3 Punkte --> Dreick
Zweick = DreickWas man hier im Forum alles so lernen kann, was einem die Lehrer nicht beigebracht haben. Belli und ich müssen unbedingt noch mal wieder zur Schule gehen!
-
Belli schrieb:
Isengo schrieb:
@ Berniebutt, naja wenn ich 2 Punkte habe kann ich doch ein Dreick zeichnen
Hut ab, ich brauch dafür 3 Punkte.
Ach Mensch, ihr wollt mich wieder nicht verstehen
http://img847.imageshack.us/img847/7033/matheq.jpg
Wir nehmen einfach an das X und Y auf der hoehe von A und B hier den dritten Punkt bilden.
-
Das wäre das letzte, was ich jetzt erwartet hätte. Aber wenn das so ist, kann ich dein Problem lösen: Die Antwort ist 90 Grad. Immer.
-
-.-
Nein eben nicht... Schau dir doch einfach mal die Aufgabenstellung und den Code an. Wie soll denn Arctan(theta) = arctan (y2-y1 / x2-x1) immer 90 Grad ergeben ?
Wie dem auch sei, das ist nicht mehr das Problem, siehe auf vorheriger Seite, geht jetzt nur noch um das sortieren der Winkel und das angeben der zugehoerigen X und Y Werte in einer Datei.
-
Du kannst auch die Indizes sortieren.
Du hast ein Array in dem die Reihenfolge notiert ist.// Unsortiert: int reihenfolge[4] = {0,1,2,3} sortieren(); // ergibt z.B. reihenfolge {2,3,1,0} // Der Punkt 2 ist dann die linke untere Ecke // Ausgabe for ( i = 0 ; i < n ; i++) printf("%f\n", ptr2[reihenfolge[i]]);
-
SeppJ schrieb:
Das wäre das letzte, was ich jetzt erwartet hätte. Aber wenn das so ist, kann ich dein Problem lösen: Die Antwort ist 90 Grad. Immer.SeppJ muss auch wieder zur Schule - da wären wir dann schon zu dritt!
@ Isengo: Man muss sich bei einer Frage klar und verständlich ausdrücken. Jedes Dreieck hat 3 Punkte - 3 Seiten - 3 Winkel. Deine Vorgabe beschränkte sich auf 2 Punkte mit dem Ziel 1 Winkel. Ich hatte geschrieben, es fehlt eine 3. Angabe. Die hast du jetzt endlich nachgeliefert. Der 90 Grad Winkel soll es nicht sein. Den Rest mit der Sortierung machst du bitte selbst oder kommst als vierter mit zur Schule?
Vielleicht üben wir einfach, wie man präzise eine Fragestellung formuliert - kann manchmal nützlich sein!
-
berniebutt schrieb:
@ Isengo: ... oder kommst als vierter mit zu Schule?
Geht er doch schon.
So wie die Fragestellungen sind (englisch) und sein Zeitversatz von 6 Stunden, wird es irgendwo an der Ostküste der USA sein.
-
DirkB schrieb:
Geht er doch schon.
So wie die Fragestellungen sind (englisch) und sein Zeitversatz von 6 Stunden, wird es irgendwo an der Ostküste der USA sein.
Ostküste USA ist gut - Boston?. Die haben da Elite-Schulen und Elite-Universitäten! Lernt man da in Geometrie etwas anderes als in Europa?
@ DirkB: Du kommst als fünfter selbstverständlich auch mit. Wieviele sind es noch?Thema für mich im Moment daddeldu! :p
-
DirkB schrieb:
Du kannst auch die Indizes sortieren.
Du hast ein Array in dem die Reihenfolge notiert ist.// Unsortiert: int reihenfolge[4] = {0,1,2,3} sortieren(); // ergibt z.B. reihenfolge {2,3,1,0} // Der Punkt 2 ist dann die linke untere Ecke // Ausgabe for ( i = 0 ; i < n ; i++) printf("%f\n", ptr2[reihenfolge[i]]);Durch mein Funktionendschungel blick ich gerade nicht so wirklich durch um ehrlich zu sein. Ich muss aber wohl ptr, ptr2 und order ( neues Array, noch nicht im Code ) irgendwie verknuepfen. Muss ich gleich nochmal auseinander wurschteln und schauen wo ich die Schleife reinpacke. Danke fuer den Tipp schonmal!
@ Berniebutt, sorry das meine Erklaerung nicht konkret genug war, aber deswegen so einen Wind drum machen
Hauptsache es macht dich gluecklich.Und ja ich studiere 30 Meilen entfernt von Boston an der UMass Lowell, Mathekurse hab ich aber alle in Deutschland belegt, haha.
-
After you calculate the thetas, please sort the points in increasing angle.
Dafuer muss man nicht den Winkel berechnen. Skalarprodukte reichen,
atanist im Vergleich sehr teuer.das meine Erklaerung nicht konkret genug war, aber deswegen so einen Wind drum machen
Mit einer klaren Sicht auf das Problem, erkennt man auch meist gleich die Loesung.
Vielleicht koenntest du kurz sagen, was am Ende herauskommen soll. Ich tippe mal auf Grahams Scan zur Berechnung der konvexen Huelle.
-
knivil schrieb:
Dafuer muss man nicht den Winkel berechnen. Skalarprodukte reichen, atan ist im Vergleich sehr teuer.
....
Vielleicht koenntest du kurz sagen, was am Ende herauskommen soll.Ich denke mal dass es hier nicht um die Mathematik geht sondern um "Programmieren in C".
-
Isengo schrieb:
@ Berniebutt ... ja ich studiere 30 Meilen entfernt von Boston an der UMass Lowell, Mathekurse hab ich aber alle in Deutschland belegt ...
Ich kenne von einem Besuch nur die UMass Amhorst - schöner Campus. Das MIT in Cambridge gefällt jedoch mir besser, weil nicht so auf der Wiese. Nun im Ernst: 'was hast du in Deutschland in Mathematik gelernt? An allen Unis werden die hier erforderlichen Grundkenntnisse der Geometrie doch vorausgesetzt.'
Wo genau ist dein Problem:
Mathematik?
Programmieren in C?Ich mache hier im Forum keinen Wind, sondern will nur helfen. Dazu muss ich aber verstehen, worum es genau geht. Und nun leg dich wieder hin oder fahre nach Boston, an den Atlantik, oder die Niagaras - dort kann man einen klaren Kopf kriegen.
-
knivil schrieb:
After you calculate the thetas, please sort the points in increasing angle.
Dafuer muss man nicht den Winkel berechnen. Skalarprodukte reichen,
atanist im Vergleich sehr teuer.das meine Erklaerung nicht konkret genug war, aber deswegen so einen Wind drum machen
Mit einer klaren Sicht auf das Problem, erkennt man auch meist gleich die Loesung.
Vielleicht koenntest du kurz sagen, was am Ende herauskommen soll. Ich tippe mal auf Grahams Scan zur Berechnung der konvexen Huelle.
Uns ist vorgegeben welche Funktionen wir benutzen, aber danke fuer den Hinweis.
Ja Cambridge ist nett und das MIT ist der Hammer, allerdings auch die Preise... Und mein Stipendium deckt leider nur staatliche Universitaeten
But please back 2 topic!
Eingabe der Werte erfolgt ueber eine Datei namens points.txt, Ausgabe der Werte erfolgt in der Datei wessen Name in die cmd Zeile 1 geschrieben wird ( Beispiel: ./a.out test.txt ( System: Linux ueber SSH ) ) , also argv[1].
In diese Datei wird geschrieben ein X Y und Winkelwert ( diesen nur zur Kontrolle ob auch wirklich richtig sortiert wurde... )
Ich glaube meine Funktionen muessen noch etwas uebersichtlicher werden, ich uebergebe noch zu viele Variablen, oder ? Ist es moeglich alle Funktionen von main auszufuehren , in diesem Fall hier ?
hier der fertige Code:
/***************************************************************/ /* Programmer: Micha Hobert */ /* */ /* Program 19: Quick Sort Them Thetas */ /* */ /* Approximate completion time: 7 hours */ /***************************************************************/ #include <stdio.h> #include <stdlib.h> #include <math.h> #define PI (3.141592653589793) typedef struct { double x; double y; }location; void swap ( double *a, double *b ){ double temp; temp = *a ; *a = *b; *b = temp; } void swap2 ( int *a, int *b ){ int temp; temp = *a ; *a = *b; *b = temp; } void printfirstpartofarray(FILE *name, location ptr[], double ptr2[], int n, int sort[]){ int j=0 ; while ( j <= n-1 ){ fprintf(name,"X = %f Y = %f Angle = %f \n", ptr[sort[j]].x, ptr[sort[j]].y, ptr2[j]); j++; } } void quick_sort ( double ptr2[], int low, int high, int sort[]){ int i, j , pivot; if ( high <= low) return; i = low - 1; j = high ; pivot = ptr2[high]; while (1) { do i = i + 1; while ( ( i < high ) && ( ptr2[i] < pivot)); do j = j - 1; while ( ( j >= low) && ( ptr2[j] > pivot )); if ( i >= j) break; swap ( &ptr2[i], &ptr2[j]); swap2 ( &sort[i], &sort[j] ); } swap(&ptr2[i], &ptr2[high]); swap2(&sort[i], &sort[high]); quick_sort ( ptr2, low, i-1,sort); quick_sort (ptr2, i+1, high,sort); } /**********************************************************************/ void angle ( FILE *name, location ptr[] , int n, double minx, double miny) { double buffer, result; int k = 0; double *ptr2; int sort[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; ptr2 = malloc (n * sizeof (double) ); while ( k <= n-1 ) { buffer = (ptr[k].y-miny) / (ptr[k].x-minx); result = atan ( buffer ) * 180 / PI; if ( ptr[k].y-miny == 0.0){ /* printf("The angle between Lowermost-Leftmost and point %d is 0.000000 degrees.\n\n",k);*/ ptr2[k] = 0.0; } else{ if ( ptr[k].x-minx == 0.0 ){ /* printf("The angle between Lowermost-Leftmost and point %d is 90.000000 degrees.\n\n",k);*/ ptr2[k] = 90.0; } else { /* printf ("The angle between Lowermost-Leftmost and point %d is %f degrees.\n\n ",k ,result);*/ ptr2[k] = result; } } k++; } quick_sort(ptr2,0,n-1, sort); printfirstpartofarray(name,ptr,ptr2,n,sort); } void vector (FILE *name, location ptr[] , int n ) { int r; int j; double miny; double minx; minx = ptr[0].x; miny = ptr[0].y; for (j=0; j<=n-1; j++){ if (ptr[j].y<miny){ miny=ptr[j].y; minx=ptr[j].x; for (r=0;r<=n-1;r++){ if ( ptr[r].x < minx ){ miny=ptr[r].y; minx=ptr[r].x; } } } } printf( "The Lower Most, Left Most Point is: x = %f and y = %f\n\n", minx,miny ); printf ("You can find your sorted Thetas in the File you typed in the cmd line.\n "); angle (name, ptr, n, minx, miny ); } int main (int argc, char *argv[] ) { int n; location *ptr; int i=0; FILE *name, *fin; fin = fopen ("points.txt", "r"); fscanf ( fin, "%d", &n ); name = fopen (argv[1], "w+"); fprintf (name, "%d\n", n ); ptr = malloc ( n * sizeof(location) ); while(i <= n-1 ){ fscanf(fin, "%lf%lf", &ptr[i].x,&ptr[i].y); i++; } vector (name, ptr , n ); return 0; }
-
Isengo schrieb:
... Ja Cambridge ist nett und das MIT ist der Hammer, allerdings auch die Preise... Und mein Stipendium deckt leider nur staatliche Universitaeten ...
Das MIT hätte ich mir auch nicht leisten können! Für die Preise dort bekommt man aber eine first-class education mit bester persönlicher Betreuung.
Back to topic: approximated 7 hours for a sort? Der QuickSort scheint da wohl etwas ungeeignet!
-
Completion time of building the program, not running it
