Koordinaten Sortieren

[dogma]

Hallo leute,

als blutiger c++ anfänger bin ich mit meiner aktuellen aufgabe noch etwas überfordert, und wollte fragen, ob jemand zu dem thema tipps oder vorschläge zum lösungsweg hätte.

die aufgabenstellung an sich sit simpel. ich bekomme 4 punkte im 2D koordinatensystem. Meine aufgabe ist es nun ein programm zu schreiben, mit dem diese punkte in einer bestimmten reihenfolge ausgegeben werden können, egal in welcher ausgangsreihenfolge sie erscheinen. und zwar mit dem punkt der vom betrachtenden auch oben links ist.

Mein bisheriger ansatz:

(ich verwende die entwicklungsumgebung QT. in QPointF ist der variablentyp qreal definiert)

#include <QtCore/QCoreApplication>

#include <iostream>

#include <QPointF>

using namespace std;


void sortx (qreal& x1, qreal& x2, qreal& x3, qreal& x4)

{

qreal max=x1;

if(max<x2)

{max=x2;}

if(max<x3)

{max=x3;}


qreal min=x1;

if(min>x2)

{min=x2;}

if(min>x3)

{min=x3;}


x1=min;

x2=max;

x3=max;

x4=min;

}


void sorty (qreal& y1, qreal& y2, qreal& y3, qreal& y4)

{

qreal max=y1;

if(max<y2)

{max=y2;}

if(max<y3)

{max=y3;}


qreal min=y1;

if(min>y2)

{min=y2;}

if(min>y3)

{min=y3;}


y1=max;

y2=max;

y3=min;

y4=min;

}


int main(int argc, char *argv[])

{

    QCoreApplication a(argc, argv);


    qreal b,c,d,e,f,g,h,i;

    char L;


    cout<<"4 Punkte eingeben:\n"; cout<<"\n";

    cout<<"koordinate x1 eingeben:\n"; cin>>b;

    cout<<"koordinate y1 eingeben:\n"; cin>>c;

    cout<<"koordinate x2 eingeben:\n"; cin>>d;

    cout<<"koordinate y2 eingeben:\n"; cin>>e;

    cout<<"koordinate x3 eingeben:\n"; cin>>f;

    cout<<"koordinate y3 eingeben:\n"; cin>>g;

    cout<<"koordinate x4 eingeben:\n"; cin>>h;

    cout<<"koordinate y4 eingeben:\n"; cin>>i;

    cout<<"Flugrichtung eingeben (n,s,o, oder w):\n";

    label: cin>>L;


    sortx(b,d,f,h);

    sorty(c,e,g,i);


    QPointF p1 (b,c);

    QPointF p2 (d,e);

    QPointF p3 (f,g);

    QPointF p4 (h,i);


    if (L=='n')

    {

    cout<<"P1=("<<p1.x()<<","<<p1.y()<<")\n";

    cout<<"P2=("<<p2.x()<<","<<p2.y()<<")\n";

    cout<<"P3=("<<p3.x()<<","<<p3.y()<<")\n";

    cout<<"P4=("<<p4.x()<<","<<p4.y()<<")\n";

    cout<<"\n"<<"Andere Richtung:\n";

    goto label;

    }


    if (L=='s')

    {

    cout<<"P1=("<<p3.x()<<","<<p3.y()<<")\n";

    cout<<"P2=("<<p4.x()<<","<<p4.y()<<")\n";

    cout<<"P3=("<<p1.x()<<","<<p1.y()<<")\n";

    cout<<"P4=("<<p2.x()<<","<<p2.y()<<")\n";

    cout<<"\n"<<"Andere Richtung:\n";

    goto label;

    }


    if (L=='o')

    {

    cout<<"P1=("<<p2.x()<<","<<p2.y()<<")\n";

    cout<<"P2=("<<p3.x()<<","<<p3.y()<<")\n";

    cout<<"P3=("<<p4.x()<<","<<p4.y()<<")\n";

    cout<<"P4=("<<p1.x()<<","<<p1.y()<<")\n";

    cout<<"\n"<<"Andere Richtung:\n";

    goto label;

    }


    if (L=='w')

    {

    cout<<"P1=("<<p4.x()<<","<<p4.y()<<")\n";

    cout<<"P2=("<<p1.x()<<","<<p1.y()<<")\n";

    cout<<"P3=("<<p2.x()<<","<<p2.y()<<")\n";

    cout<<"P4=("<<p3.x()<<","<<p3.y()<<")\n";

    cout<<"\n"<<"Andere Richtung:\n";

    goto label;

    }


    else

    {

        cout<<"Ungültige Richtung\n"<<"Nochmal eingeben\n";

        goto label;

    }


    return a.exec();

}[/PHP]

dieser ansatz funktioniert tadellos, wenn es sich um ein rechteckiges konstrukt handelt, bei dem die seiten parallel zu den achsen des koordinatensystems angenommen werden.

hier beginnt mein problem:

der sortieralgorithmus soll für beliebige vierecke realisiert werden, d.h. es muss sich nicht einmal um ein rechteck handeln, noch um sonst irgendeine feste geometrische form, und hierbei versagt obiger ansatz.

leider habe ich keine idee wie man das realisieren könnte, ausser z.b. mit dem winkel zur y-achse für jede seite. mir ist allerdings nicht klar, wie ich das realisieren kann, so dass man die punkte wirklich in beliebiger reihenfolge eingeben kann.

kann einer mein problem nachvollziehen und hat vielleicht einen lösungsvorschlag?

gruß

[Klotzkopp]

"Von oben links" reicht nicht für eine Sortierung.

Wenn du zwei Punkte (a, und (c,d) hast, wann genau muss dann der erste vor den zweiten sortiert werden? Du musst das für den allgemeinen Fall beantworten können, wenn du sortieren willst.

Es ist nicht so, dass es da eine bestimmte Lösung gibt. Es gibt unendlich viele Möglichkeiten, hier eine Ordnungsrelation festzulegen. Aber du musst eine festlegen, sonst kannst du nicht sortieren.

[dogma]

Ich arbeite derzeit an einer lösung, bei der ich das gesamte viereck in den positiven quadranten des koordinatensystems verschiebe und dann anhand des winkels zwischen der y-achse und der ursprungsgeraden durch meine jeweiligen punkte sortiere.

den kleinsten winkel bekomme ich so immer problemlos raus, aber den größten nicht... ich finde meinen fehler einfach nicht.

#include <QtCore/QCoreApplication>

#include <iostream>

#include <math.h>

#include <stdlib.h>

#define pi 3.1415927

using namespace std;


void push(int& x1, int& y1, int& x2, int& y2, int& x3, int& y3, int& x4, int& y4)

{

int minx=x1;

if(minx>x2)

{minx=x2;}

if(minx>x3)

{minx=x3;}

if(minx>x4)

{minx=x4;}


int push_x;


if(minx<=0)

{

push_x = abs(minx) + 1;

}

else

    push_x=0;


x1=x1+push_x;

x2=x2+push_x;

x3=x3+push_x;

x4=x4+push_x;


int miny=y1;

if(miny>y2)

{miny=y2;}

if(miny>y3)

{miny=y3;}

if(miny>y4)

{miny=y4;}


int push_y;


if (miny<=0)

{

push_y = abs(miny) + 1;

}

else

    push_y=0;


y1=y1+push_y;

y2=y2+push_y;

y3=y3+push_y;

y4=y4+push_y;

}


void scan_p1 (int& x1, int& y1, int& x2, int& y2, int& x3, int& y3, int& x4, int& y4)

{

    double alpha,beta,gamma,delta;

    push(x1,y1,x2,y2,x3,y3,x4,y4);

    double faktor = 180/pi;


    alpha = atan2(x1,y1) * faktor;

    beta = atan2(x2,y2) * faktor;

    gamma = atan2(x4,y4) * faktor;

    delta = atan2(x3,y3) * faktor;


    double min=alpha;

    if(min>beta)

    {min=beta; x1=x2; y1=y2;}

    if(min>gamma)

    {min=gamma; x1=x4, y1=y4;}

    if(min>delta)

    {min=delta; x1=x3; y1=y3;}

}


void scan_p3 (int& x1, int& y1, int& x2, int& y2, int& x3, int& y3, int& x4, int& y4)

{

    double alpha,beta,gamma,delta;

    double faktor = 180/pi;


    alpha = atan2(y1,x1) * faktor;

    beta = atan2(y2,x2) * faktor;

    gamma = atan2(y4,x4) * faktor;

    delta = atan2(y3,x3) * faktor;


    double min=alpha;

    if(min>beta)

    {min=beta; x1=x2; y1=y2;}

    if(min>gamma)

    {min=gamma; x1=x4, y1=y4;}

    if(min>delta)

    {min=delta; x1=x3; y1=y3;}

}


int main(int argc, char *argv[])

{

    QCoreApplication a(argc, argv);


    int b,c,d,e,f,g,h,i;


    cout<<"4 Punkte eingeben:\n"; cout<<"\n";

    cout<<"koordinate x1 eingeben:\n"; cin>>b;

    cout<<"koordinate y1 eingeben:\n"; cin>>c;

    cout<<"koordinate x2 eingeben:\n"; cin>>d;

    cout<<"koordinate y2 eingeben:\n"; cin>>e;

    cout<<"koordinate x3 eingeben:\n"; cin>>f;

    cout<<"koordinate y3 eingeben:\n"; cin>>g;

    cout<<"koordinate x4 eingeben:\n"; cin>>h;

    cout<<"koordinate y4 eingeben:\n"; cin>>i;


    scan_p1(b,c,d,e,f,g,h,i);

    cout<<"P1=("<<b<<","<<c<<")\n";

    //cout<<"P2=("<<d<<","<<e<<")\n";

    scan_p3(b,c,d,e,f,g,h,i);

    cout<<"P3=("<<f<<","<<g<<")\n";

    //cout<<"P4=("<<h<<","<<i<<")\n";


    return a.exec();

}[/PHP]

[Pointerman]

Moin!

Wahrscheinlich koennte Dir besser geholfen werden, wenn Du statt jede Menge Code zu posten noch einmal genau und verstaendlich erklaeren wuerdest nach welchen Kriterien die Punkte sortiert werden sollen. Deinem Ausgangspost kann ich das so nicht entnehmen und ich denke, dass Klotzkopps Frage auch in diese Richtung ging.

[dogma]

also, dann nochmal zur erklärung:

4 punkte sollen zu einem viereck verbunden werden. ausser dass es in diesem viereck keine innenwinkel geben darf die größer sind als 180° gibt es bei diesem viereck keine restriktionen, dass heisst, es können gleichermaßen rechtecke, wie auch rauten, trapeze, oder sonst irgendwelche beliebigen vierecke sein, die auch unsymmetrisch sein können. diese punkte werden beliebiger reihenfolge eingegeben. ausgegeben werden sollen sie aber so, dass mit dem punkt angefangen wird der aus subjektiver sicht oben links ist. ausgehend davon sollen die punkte im urzeigersinn der reihe nach ausgegeben werden, d.h. von oben links, nach unten links.

mein ansatz:

da die 4 punkte koordinaten in allen 4 quadranten des 2-dimensionalen karthesischen koordinatensystems haben können schiebe ich erst einmal alle punkte in den ausschließlich positiven quadranten und zwar so, dass es weder einen x-wert, noch einen y-wert geben kann, der gleich null ist.

anschließend bestimme ich mit hilfe des atan2 die winkel zwischen der y-achse und den ursprungsgeraden durch jeden der 4 punkte. anhand der größe der winkel kann ich dann bestimmen, wo sich jeder punkt befindet.

warum es bisher nicht geklappt hat:

ich habe zunächst versucht die winkel mit hilfe des minimal-, bzw. maximalkriteriums zu ordnen, was allerdings nicht geklappt hat. weil es so immer winkel gab, die nicht zugeordnet werden konnten, weil sie weder ein maximum, noch ein minimum waren.

warum es jetzt klappt:

da nur 4 werte sortiert werden müssen, habe ich eine simple version des bubble sort algorithmus verwendet, die die winkel der größe nach sortiert, und dabei auch immer die zugehörigen koordinaten mitsortiert. auf diese art bekomme ich den kleinsten winkel, und den dazugehörigen ersten punkt, den größten winkel und den dazugehörigen dritten punkt, sowie die beiden anderen winkel, die die punkte 2 und 4 beschreiben. da der fall in dem der winkel zum 2. punkt größer ist als der winkel zum 4. punkt genauso legitim ist wie der fall in dem der winkel zum 4. punkt größer ist als der winkel zum 2. punkt überprüfe ich einfach die x-werte der beiden punkte. ist der x-wert des 4. punktes größer als der des 2. werden die punkte 2 und 4 einfach vertauscht, ohne dass die winkel vertauscht werden.

anschließend wird das viereck wieder in seine ursprüngliche form zurück verschoben und die werte ausgegeben. nun funktioniert es.

bei interesse kann ich auch den code posten.