4. Polygon, geometrischer Algorithmus

Polygon, geometrischer Algorithmus

  • S

    Hallo liebe Leute,

    ich habe grade ein grosses Problem, ich sitze inner Uni im C-Praktikum und schaffe folgende Aufgabe nicht:
    "Schreiben Sie ein Programm, das eine Menge von Punkten einliest, daraus den einfachen geschlossenen Pfad in Form eines Polygons konstruiert und dessen E
    Eckpunkte in der richtige Reihenfolge wieder ausgibt."

    Das einzige was ich bisher hinbekommen habe, ist die Struktur:

    #include "stdafx.h" 

#define Nmax 50 
struct point 
{ 
int x, y; 

char c; 
}; 

struct line 
{ 
struct point p1, p2; 
}; 
struct point polygon [Nmax];

    Als Hilfe haben wir folgende Funktion bekommen:

    float floattheta(point p1, point p2){ 
   int dx, dy, ax, ay; 
   float t; 
   dx = p2.x - p1.x; ax = abs(dx); 
   dy = p2.y - p1.y; ay = abs(dy); 
   t = (ax+ay == 0) ? 0 : (float) dy / (ax+ay); 
   if (dx < 0) t = 2-t; else if (dy < 0) t = 4+t; 
   return t*90.0; 
}

    Allerdings weiss ich nicht, was die Funktion abs() genau machen soll.

    Fuer jegliche Hilfe waere ich dankbar!

    0
  • C

    Gegenfrage: Was genau verstehst du (bzw. dein Dozent) unter "richtige Reihenfolge"?

    0
  • S

    wir sollen bei der kleinsten y koordinate anfangen. sind mehrere y koordinaten gleich, sollen wir die kleinste x koordinate als ersten punkt nehmen. und dann in dieser reihenfolge anschliessend wieder ausgeben.

    0
  • _

    Du könntest den Mittelpunkt aller Punkte berechnen, dann die Punkte nach Winkel sortiert ausgeben.

    0
  • S

    dafuer brauche ich aber theta() nicht oder?

    0
  • _

    Sabine83 schrieb:

    dafuer brauche ich aber theta() nicht oder?

    Du misst einfach für jeden Punkt die Distanz in x und y zum Mittelpunkt aller Punkte. Mit atan2(dy, dx) kannst du dann jeweils den Winkel berechnen.

    0
  • S

    leider kann ich das nicht in c code uebersetzen

    0
  • C

    atan2() bestimmt den Winkel, in dem der übergebene Punkt zum Ursprung liegt. Ich habe mir deine theta()-Funktion nicht genau angesehen, aber ich würde mal sagen, daß sie vergleichbare Werte* liefern dürfte.

    Das heißt, du benötigst nur noch einen Sortieralgorithmus, den du über deine Punktliste laufen lässt - und verwendest "theta(p[i],center)<theta(p[j],center)" als Vergleichkriterium für die Sortierung.

    * das sind keine Winkelangaben, aber für deine Zwecke reicht auch aus, wenn du daran feststellen kannst, welcher Winkel größer ist.

    0
  • _

    Sabine83 schrieb:

    leider kann ich das nicht in c code uebersetzen

    Du solltest dich mal mit for-loops und qsort() befassen (falls du das noch nicht kennst). Infos dazu gibt's übarall im Internet.

    0
  • B

    @sabine: bevor hier alle anfangen die reihenfolge der punkte zu ermitteln, bekommst du die denn überhaupt hin:

    Schreiben Sie ein Programm, das eine Menge von Punkten einliest, daraus den einfachen geschlossenen Pfad in Form eines Polygons konstruiert

    0
Anmelden zum Antworten