Prüfen ob Punkt auf Gerade liegt

[Belur]

Hey,

ich sitze zur Zeit an einer Aufgabe. Ich soll eine Menge von Punkten einlesen und daraus dann einen "einfach geschlossenen Pfad" konstruieren.

Danach soll ich die Eckpunkte dieses Polygons ausgeben.
Ich habe also folgendes struct:

struct point
{
    int x, y;
    float angle;
    char c;
};

Zu Anfang wähle ich einen Ankerpunkt (den Punkt mit dem niedrigsten y-Wert). Dann berechne ich mit einer theta-Funktion, den Winkel von jedem Punkt zum Ankerpunkt und sortiere anschließend das Array, dass mein Polygon repräsentiert.

float theta(struct point p1, struct 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;
}

Das funktioniert auch wunderbar. Nun zum eigentlich Problem.
Es kann ja Punkte geben, die keine Eckpunkte sind. Die Punkte will ich nicht ausgeben. (A ist in den Beispielen immer mein Ankerpunkt)
zB:


Ich habe mir also zuerst gedacht ich gucke mir immer 3 Punkte an und vergleiche die Steigungen. Ich würde mir also zuerst die Steigung der Geraden ab und dann die Steigung der Geraden bc angucken. Wenn 2 "nebeneinander liegende" Geraden die gleiche Steigung haben, kann der Punkt in der Mitte praktisch kein Eckpunkt sein.

Problem ist, es gibt leider auch Polygone wie dieses:

Ich kann die Steigung nicht berechnen, weil ich sonst durch 0 teilen würde.


Dann dachte ich auch ich könnte vllt über die Winkel gehen. Dh wenn 3. Punkte den gleichen Winkel haben, können nur 2 davon Eckpunkte sein. zB:


Das würde zwar, für den 1. und den 3. Fall klappen, aber im 2. Fall sieht man ja, dass es durchaus 3 Punkte geben kann die auf einer Geraden liegen, wo alle 3 unterschiedliche Winkel haben.

Leider komme ich also nicht wirklich weiter und würde mich über Hilfe freuen.

Grüße

[qqdev]

Geradengleichung aufstellen und schauen ob der Punkt auf Geraden liegt. Wenn das nicht geht, wegen der Berechnung der Steigung (Teilen durch 0), dann schaust du, ob der 3. Punkt den gleichen x-Wert hat wie einer der beiden anderen Punkte.

[Belur]

Danke habs hinbekommen