Aufgabe

Vicious Falcon

Wenn die Punkte

D        C

A        B

erst einmal auf diese Form gebracht wurden (oder eine Andere, deine Entscheidung), dann braucht man nicht unbedingt die Winkel zu bestimmen.
Im oben genannten Beispiel:
dxAD, dxBC, dyAB und dyCD (die jeweilige Verschiebung) bestimmen.
Alles null: Rechteck/Quadrat, CD und AD vergleichen, gleich?Quadrat, sonst Rechteck.
dxAD==dxBC und dyCD==0 und dyAB==0 -> Parallelogramm.
dxAD==-dxCB und dyCD==0 und dyAB==0 -> gleichschenkliges Trapez u.s.w.

Edit: Das gilt natürlich nur für Figuren ohne Rotation.

Michael E.

Vicious Falcon schrieb:

erst einmal auf diese Form gebracht wurden (oder eine Andere, deine Entscheidung), dann braucht man nicht unbedingt die Winkel zu bestimmen.

Dann musst du aber erst mal nen Basiswechsel durchführen, was aufwendiger als ein simples Skalarprodukt ist.

Michael E. schrieb:

Dann musst du aber erst mal nen Basiswechsel durchführen, was aufwendiger als ein simples Skalarprodukt ist.

Das ist FH erstes Semester, die sind gerade 6-8 Wochen dabei.

Aus der Aufgabenstellung kann man schon sehen das die Quadrate, und Rechteckeke alle schön parallel zu den Achsen liegen. Ebenso für 2 Seiten des Parallelogramms und die Diagonalen der Raute.
Hier geht es erstmal nicht um Mathe sondern ums Programmieren. Von daher sollte das mit den gegebenen Koordinaten ausreichen.
Wenn der Satz des Pythagoras zur Anwendung kommt ist das ausreichend.

Wer das Skalarprodukt kennt soll das machen.

Werner Salomon

na endlich mal wieder ein interessante Aufgabe; Schade, dass der Thread in das C-Forum gewandert ist.

Wenn man das Problem etwas verallgemeinert, muss man nach Eigenschaften eines Vierecks suchen, die voneinander völlig unabhängig sind und von der jede einzeln einem Viereck zuzuordnen sind. Letztlich kommt man zu einer Klassifikation von Vierecken auch bekannt unter der Bezeichnung 'Haus der Vierecke'.

Der einzige mir bekannte Satz dieser Eigenschaften ist (ich habe jede Eigenschaft mit einem Großuchstaben bezeichnet):
(H) eine Diagonale des Vierecks wird durch die andere halbiert
(I) das Viereck hat einen Inkreis
(P) mindestens ein Paar gegenüberliegender Seiten ist parallel
(U) das Viereck hat einen Umkreis

Wie man erkennt, ob ein Viereck eine Eigenschaft hat, sollte bei (P) und (H) kein Problem sein. Für In- und Umkreis schaue man hier
(I) Tangentenviereck
(U) Sehnenviereck

Ein Quadrat ist ein (HIPU) - es besitzt alle vier Eigenschaften - ein Rechteck ist ein (HPU), es hat keinen Inkreis, eine Raute wäre ein (HPI), ein Parallelogramm ein (HP) und ein Trapez schlicht ein (P).

Dann schreibe man vier Funktionen, die diese Eigenschaften feststellen und fasse alles zusammen

char* typ_von_viereck( Viereck* v )
{
    char* text[] = {
        "allgemeines Viereck",  // ....
        "schiefer Drache",      // H...
        "Tangentenviereck",     // .I..
        "Drache",               // HI..
        "Trapez",               // ..P.
        "Parallelogramm",       // H.P.
        "Trapez mit Inkreis",   // .IP.
        "Raute",                // HIP.
        "Sehnenviereck",        // ...U
        "schiefer Drache mit Umkreis", // H..U
        "Sehnentangentenviereck", // .I.U
        "rechtohriger Drache",  // HI.U
        "gleichschenkliges Trapez", // ..PU
        "Rechteck",             // H.PU
        "gleichschenkliges Trapez mit Inkreis", // .IPU
        "Quadrat"               // HIPU
    };
    return text[
            ((eine_diagonalen_halbiert_die_andere( v  )?    1: 0) << 0) // H
        +   ((hat_inkreis( v )?                             1: 0) << 1) // I
        +   ((ein_seitenpaar_ist_parallel( v )?             1: 0) << 2) // P
        +   ((hat_umkreis( v )?                             1: 0) << 3) // U
    ];
}

Das ganze integriert man in ein Programm, dessen Konversation mit dem Benutzer dann vielleicht so aussehen könnte:

geben Sie bitte ein Viereck ein (Ende mit 'q')
Format: (2;1) (8;3) (7;6) (1;4)

> (2;1) (5;2) (4;5) (1;4)
Das Viereck ist ein Quadrat

> (2;1) (8;3) (7;6) (1;4)
Das Viereck ist ein Rechteck

> (2;1) (11;4) (7;6) (1;4)
Das Viereck ist ein Trapez

> (8;4) (6;7) (2;4) (2;-2)
Das Viereck ist ein allgemeines Viereck

> (8;4) (6;7) (2;4) (3;-2)
Das Viereck ist ein schiefer Drache

> (-1;0) (11;4) (7;6) (1;4)
Das Viereck ist ein gleichschenkliges Trapez

> q

Gruß
Werner

@Edit: Inkreis schreibt man natürlich mit einem 'n'.

Vicious Falcon

Mich würde echt mal interessieren, wie der TE (Sputnik1983) das Problem gelöst hat. Werner Salomon hat die Lösung schlechthin gegeben und sich damit viel Arbeit gemacht. Ein kurzes Feedback fänd' ich nur fair.

also ich habe es nun nach werners lösung versucht doch auch da komm ich nicht weiter.ich weiss nicht woher ich wissen soll wie ich jetzt z.b sagen wir wir haetten die punkte(1,3),(3,1),(4,2),(5,3) woher weiss ich wie lang dann die seiten sind????
wenn ich ja die seiten wuesste wuerde es ja mit den vergleichen die werner geschrieben hat gehen.aber wie?ich stehe da leider auf dem schlauch.
ist es nicht möglich ein beispielcode hier einzustellen damit ich das auch verstehe?

fals nicht thx für eure mühen

Werner Salomon

sputnik1983 schrieb:

also ich habe es nun nach werners lösung versucht doch auch da komm ich nicht weiter.ich weiss nicht woher ich wissen soll wie ich jetzt z.b sagen wir wir haetten die punkte(1,3),(3,1),(4,2),(5,3) woher weiss ich wie lang dann die seiten sind????

kennst Du den Satz des Phytagoras?

sputnik1983 schrieb:

wenn ich ja die seiten wuesste wuerde es ja mit den vergleichen die werner geschrieben hat gehen.aber wie?

Wenn Du die Längen der Seiten berechnest, so nützt Dir das in keinem der vier Fälle.

Um die Parallelität zweier Seiten festzustellen, kannst Du die beiden Seitenvektoren auf Kollinearität prüfen (Funktion: ein_seitenpaar_ist_parallel()). Die Kollinearität kann man z.B. mit dem Kreuzprodukt ermitteln; dies ist im Fall zweier kollinearer Vektoren =0.

Um festzustellen ob eine Diaogonale die andere halbiert, genügt eine Kollinearitätsprüfung einer Diagonalen und des Vektors, der von einer Ecke der Diagonalen zur Mitte der anderen Diagonalen verläuft (Funktion: eine_diagonalen_halbiert_die_andere()).

sputnik1983 schrieb:

ich stehe da leider auf dem schlauch.
ist es nicht möglich ein beispielcode hier einzustellen damit ich das auch verstehe?

Beispielcode habe ich nur in C++; wobei ich nicht glaube, dass Du den verstehen kannst ohne die mathematischen Grundlagen verstanden zu haben.

Gruß
Werner

Werner Salomon

Werner Salomon schrieb:

Wenn Du die Längen der Seiten berechnest, so nützt Dir das in keinem der vier Fälle.

Das stimmt nicht (war gestern schon spät). Bei der Prüfung auf Inkreis benötigt man die Längen. Ein Viereck hat genau dann einen Inkreis, wenn die Summen der Längen der gegenüberliegenden Seiten gleich sind.

Daniel1985

Werner Salomon schrieb:

Beispielcode habe ich nur in C++;

besteht noch die möglichkeit noch sich den code snippsel in c++ mal anzuschauen??

Werner Salomon

Daniel1985 schrieb:

besteht noch die möglichkeit noch sich den code snippsel in c++ mal anzuschauen??

Hallo Daniel1985,

willkommen im C++-Forum,
wie bist Du denn auf diesen alten Thread gestoßen?

Ich habe den Code noch gefunden, Du brauchst dazu noch die boost.lib für die Vektor-Klasse, die ich da verwende. Man könnte aber auch ohne auskommen. Hier der Hauptteil:

#include "vector2.h"

#include <algorithm> // std::max
#include <cmath> // std::abs
#include <iostream>
#include <string>

template< char C >
std::istream& Char( std::istream& in )
{
    char c;
    if( in >> c && c != C )
        in.setstate( std::ios_base::failbit );
    return in;
}

// --   Vektor Einlesen
template< typename T >
std::istream& operator>>( std::istream& in, basic_vector< T >& v )
{
    T x, y;
    if( in >> Char<'('> >> x >> Char<';'> >> y >> Char<')'> )
        v = basic_vector< T >( x, y );
    return in;
}

typedef basic_vector< double > Koordinate;

namespace
{
    const double EPS = 1.E-8;
    const double PI = std::acos( -1.0 );
}

bool gleich( double a, double b )
{
    return std::abs( a - b ) < EPS;
}
bool kollinear( Koordinate a, const Koordinate& b )
{
    // --   das Kreuzprodukt sollte ==0 sein
    return std::abs( a % b ) < EPS;
}
double winkel( Koordinate a, const Koordinate& b )
{
    return std::atan2( a % b, a * b );
}

class Viereck
{
public:
    Viereck() {}

    friend bool eine_diagonalen_halbiert_die_andere( const Viereck& v  )
    {
        // oder anders ausgedrückt: liegt der Mittelpunkt einer Diagonalen
        //  auf der anderen, so wird erstere halbiert
        return kollinear( (v.m_ecke[1] + v.m_ecke[3])/2 - v.m_ecke[0], v.e() )
            || kollinear( (v.m_ecke[2] + v.m_ecke[0])/2 - v.m_ecke[1], v.f() );
    }
    friend bool hat_innkreis( const Viereck& v )
    {
        // ein Viereck hat einen Inkreis, wenn die Summen der gegenüberliegenden
        //  Seitenpaare gleich sind
        return gleich( abs( v.a() ) + abs( v.c() ), abs( v.b() ) + abs( v.d() ) );
    }
    friend bool seitenpaar_parallel( const Viereck& v )
    {
        // eine Seitenpaar ist parallel, wenn die Seitenvektoren
        //  kollinear sind.
        return kollinear( v.a(), v.c() ) || kollinear( v.b(), v.d() );
    }
    friend bool hat_umkreis( const Viereck& v )
    {
        // ein Viereck hat einen Umkreis, wenn die Summe zweier gegenüberliegenden
        //  Winkel ==180 Grad beträgt.
        return gleich( winkel( v.a(), -v.d() ) + winkel( v.c(), -v.b() ), PI /*180 Grad*/ );
    }

    friend std::istream& operator>>( std::istream& in, Viereck& v )
    {
        return in >> v.m_ecke[0] >> v.m_ecke[1] >> v.m_ecke[2] >> v.m_ecke[3];
    }

private:
    Koordinate a() const { return m_ecke[1] - m_ecke[0]; }
    Koordinate b() const { return m_ecke[2] - m_ecke[1]; }
    Koordinate c() const { return m_ecke[3] - m_ecke[2]; }
    Koordinate d() const { return m_ecke[0] - m_ecke[3]; }
    Koordinate e() const { return m_ecke[2] - m_ecke[0]; }
    Koordinate f() const { return m_ecke[3] - m_ecke[1]; }

    Koordinate m_ecke[4];
};

std::string typ_von( const Viereck& v )
{
    const char* text[] = {
        "allgemeines Viereck",  // ....
        "schiefer Drache",      // H...
        "Tangentenviereck",     // .I..
        "Drache",               // HI..
        "Trapez",               // ..P.
        "Parallelogramm",       // H.P.
        "Trapez mit Innkreis",  // .IP.
        "Raute",                // HIP.
        "Sehnenviereck",        // ...U
        "schiefer Drache mit Umkreis", // H..U
        "Sehnentangentenviereck", // .I.U
        "rechtohriger Drache",  // HI.U
        "symmetrisches Trapez", // ..PU
        "Rechteck",             // H.PU
        "symmetrisches Trapez mit Innkreis", // .IPU
        "Quadrat"               // HIPU
    };
    return text[
            ((eine_diagonalen_halbiert_die_andere( v  )?    1: 0) << 0) // H
        +   ((hat_innkreis( v )?                            1: 0) << 1) // I
        +   ((seitenpaar_parallel( v )?                     1: 0) << 2) // P
        +   ((hat_umkreis( v )?                             1: 0) << 3) // U
    ];
}

int main()
{
    using namespace std;
    cout << "geben Sie bitte ein Viereck ein (Ende mit 'q')" << endl;
    cout << "Format: (2;1) (8;3) (7;6) (1;4)" << endl;
    for( Viereck v; cout << "\n> ", cin >> v; )
        cout << "Das Viereck ist ein " << typ_von( v ) << endl;
    return 0;
}

.. und die Vektor-Klasse (siehe auch hier)
Die Datei "vector2.h":

#ifndef SAM_VECTOR2_H_
#define SAM_VECTOR2_H_
#include <boost/operators.hpp>

#include <iosfwd>
#include <cmath>

template< typename T >
class basic_vector : 
            boost::additive< basic_vector< T >,
            boost::multiplicative2< basic_vector< T >, T
            > >
{
public:
    typedef T value_type;

    basic_vector()
        : m_x(0), m_y(0)
    {}

    basic_vector( value_type x, value_type y )
        : m_x( x ), m_y( y )
    {}

    basic_vector& operator+=( const basic_vector& b )
    {
        m_x += b.m_x;
        m_y += b.m_y;
        return *this;
    }
    basic_vector& operator-=( const basic_vector& b )
    {
        m_x -= b.m_x;
        m_y -= b.m_y;
        return *this;
    }

    value_type operator*( const basic_vector& b ) const
    {   // Skalarprodukt
        return m_x * b.m_x + m_y * b.m_y;
    }

    basic_vector& operator*=( value_type f )
    {
        m_x *= f;
        m_y *= f;
        return *this;
    }

    basic_vector& operator/=( value_type f )
    {
        // Bem.: die Multiplikation mit dem Kehrwert von 'f' ist signifikant schneller als 
        //      die Division der drei Koordinaten durch 'f'
        return *this *= value_type(1) / f;
    }

    value_type operator%( const basic_vector& b ) const
    {   // Kreuzprodukt in 2D -> Skalar
        return m_x * b.m_y - m_y * b.m_x;
    }

    friend value_type abs( const basic_vector& v )
    {
        using namespace std;
        return sqrt( v.m_x * v.m_x + v.m_y * v.m_y );
    }

    basic_vector operator-() const
    {
        return basic_vector( -m_x, -m_y );
    }

private:
    value_type  m_x;   
    value_type  m_y;   
};

:xmas2: Werner