Berechnen von Winkeln zwischen 2 Punkten...

[Isengo]

Hallo,
ich habe mein Programm Lower Most, Left Most erweitert. Nun habe ich das Problem das der Compiler mir keine Fehlermeldung rausgibt, aber das Programm sich anscheinend aufhaengt, warum auch immer !

Das Ziel des Programms ist es den Winkel zwischen den am weitesten links unten liegenden Punkt und den anderen Punkten zu berechnen.

Habe dafuer die atan () Funktion benutzt die ich mit -lm beim compilieren mit einfuege.

Vielleicht koennt ihr mir weiterhelfen...

/***************************************************************/ 
/* Programmer: Micha Hobert                                    */ 
/*                                                             */ 
/* Program 14: Lowermost and Leftmost                          */ 
/*                                                             */ 
/* Approximate completion time:   5 hours                      */ 
/***************************************************************/ 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

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 ) {

    buffer = (ptr[k+1].x-minx) / (ptr[k+1].y-miny);
    result = atan ( buffer );
    k++;
    printf ( "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;
	}
      }
    }
  }

  printf( "The Lower Most, Left Most Point is: x = %f  and y = %f\n\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]

Habe eben nochmal 2-3 Fehler gefunden, jetzt scheint es zu laufen, bis auf EINEN kleinen Fehler, und zwar macht der Buffer mir Probleme wenn ich den Radius von Punkt selber berechnen moechte, also das ist ja dann 90 Grad. Das passiert auch wenn ich einen Punkt habe der ueber meinem Lower Most left Most liegt ...

/***************************************************************/ 
/* Programmer: Micha Hobert                                    */ 
/*                                                             */ 
/* Program 14: Lowermost and Leftmost                          */ 
/*                                                             */ 
/* Approximate completion time:   5 hours                      */ 
/***************************************************************/ 

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

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 ) { 
	buffer = (ptr[k].y - miny) / (ptr[k].x - minx);
	result = atan ( buffer ) ; 
    k++;
	if ( buffer == 0 ){
	printf ( "The tangent between Lowermost-Leftmost and point %d is 90 radian.\n\n ",k ); /* Irgendwas fehlt mir hier, im Buffer steht irgendwas von 1.#IND00 */
	}
	else
	printf ( "The tangent between Lowermost-Leftmost and point %d is  %f radian.\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\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; 

}

[DirkB]

Die Funktion atan2() ist für solche Sachen deutlich besser geeignet.

Da spielt es auch keine Rolle wenn ptr[k].x == minx ist. Dann teilst du durch 0 und buffer wird unendlich, was das 1.#IND00 dann auch bedeutet.

[DirkB]

Isengo schrieb:

90 radian

Hast du wieder die Nacht durchgemacht?

"90 degree" oder "pi/2 rad"

[berniebutt]

Rein geometrisch betrachtet gibt es zwischen 2 Punkten (x,y) keinen Winkel. Für einen Winkel muss noch eine 3. Angabe her. Welche?

[seldon]

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.

[Isengo]

DirkB schrieb:

Die Funktion atan2() ist für solche Sachen deutlich besser geeignet.

Da spielt es auch keine Rolle wenn ptr[k].x == minx ist. Dann teilst du durch 0 und buffer wird unendlich, was das 1.#IND00 dann 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; 

}

[DirkB]

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-minx gegen 0.0 geht.

Wenn buffer == 0.0 ist wird meist ptr[k].y-min 0.0 sein und somit ergibt das 0°.

[Isengo]

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; 

}

[Belli]

Isengo schrieb:

@ Berniebutt, naja wenn ich 2 Punkte habe kann ich doch ein Dreick zeichnen

Hut ab, ich brauch dafür 3 Punkte.

[berniebutt]

@ Belli

Ganz einfache Geometrie:
2 Punkte --> Zweick
3 Punkte --> Dreick
Zweick = Dreick

Was 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!

[Isengo]

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.

[SeppJ]

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.

[Isengo]

-.-

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.

[DirkB]

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]]);

[berniebutt]

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!

[DirkB]

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.

[berniebutt]

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

[Isengo]

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.

[knivil]

After you calculate the thetas, please sort the points in increasing angle.

Dafuer muss man nicht den Winkel berechnen. Skalarprodukte reichen, atan ist 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.