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:
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.
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:
[Only registered and activated users can see links. Click Here To Register...]
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:
[Only registered and activated users can see links. Click Here To Register...]
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:
[Only registered and activated users can see links. Click Here To Register...]
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
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:
Code:
struct point
{
int x, y;
float angle;
char c;
};
Code:
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;
}
Es kann ja Punkte geben, die keine Eckpunkte sind. Die Punkte will ich nicht ausgeben. (A ist in den Beispielen immer mein Ankerpunkt)
zB:
[Only registered and activated users can see links. Click Here To Register...]
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:
[Only registered and activated users can see links. Click Here To Register...]
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:
[Only registered and activated users can see links. Click Here To Register...]
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