Konvexe Rumpflänge in C

Question

Ich mache ein Programm zur Berechnung der konvexen Rumpflänge von 2D-Punkten.

Am Eingang gibt es eine Reihe von Punkten n und dann die Koordinaten jedes Punktes.

zum Beispiel:

6 
-8 -3 
-6 1 
-5 -2 
-3 1 
-3 4 
2 18 

und Ausgang ist einfach die Länge der konvexen Hülle.

mein Code sieht wie folgt aus bisher:

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

typedef struct point 
{ 
    double x; 
    double y; 
}POINT,VECTOR; 

POINT b[1000]; 
VECTOR normal; 
int n; 

int upper_lower(int i, VECTOR ab, double c) { 
    double x, y,result; 
    y = b[i].y; 
    x = normal.x*b[i].x; 
    result = -(x + c)/normal.y; 
    if (y>result) return 1; 
    if (y == result) return 0; 
    else 
     return -1; 


} 

int ccw(VECTOR v,VECTOR v2) 
{ 
    double cp; 

    cp = v2.x*v.y - v2.y*v.x; 

if (cp == abs(cp)) return 1; 
else 
    return -1; 


} 

double vector_length(VECTOR v) 
{ 
    return sqrt(pow(v.x, 2) + pow(v.y, 2)); 

} 

int cmp_points(const void *p1, const void *p2) 
{ 
    const POINT *pt1 = p1; 
    const POINT *pt2 = p2; 

// do primary compare on x 
if (pt1->x > pt2->x) 
    return 1; 
if (pt1->x < pt2->x) 
    return -1; 

// pt1->x == pt2->x - do secondary compare on y... 
if (pt1->y > pt2->y) 
    return 1; 
if (pt1->y < pt2->y) 
    return -1; 

// pt1 == pt2 
return 0; 
} 

int main() 
{ 
    int i,poloha,upper[1000],lower[1000],h=0,d=0; 
    scanf("%d", &n); 
    if (n <= 0 && n > 1000) return 0; 
    for (i = 0; i < n; i++) 
    { 
     scanf("%lf %lf", &b[i].x, &b[i].y); 
    } 
    qsort(b, n, sizeof(POINT), cmp_points); 

//split in half 
VECTOR ab; 
double c; 
ab.x = b[n - 1].x - b[0].x; 
ab.y = b[n - 1].y - b[0].y; 
normal.x = -ab.y; 
normal.y = ab.x; 
c = -normal.x*b[0].x - (normal.y*b[0].y); 
for (i = 0; i < n; i++) 
{ 
    poloha = upper_lower(i,ab,c); 
    if (poloha == 1) upper[h++] = i; 
    if (poloha == -1) lower[d++]=i; 
    if (poloha == 0) 
    { 
     upper[h++] = i; 
     lower[d++] = i; 
    } 

} 
int j = 0; 
double v, length = 0; 
VECTOR v1, v2, v3,v4; 
v3.x = 0; v3.y = 0; 
//lower part 
for (i = 0; ; i++) 
{ 
    int in = 0; 
    if (lower[i + 2] < 0) 
    { 
     v1.x = b[lower[i + 1]].x - b[lower[0]].x; 
     v1.y = b[lower[i + 1]].y - b[lower[0]].y; 

     v2.x = b[lower[i]].x - b[lower[i + 1]].x; 
     v2.y = b[lower[i]].y - b[lower[i + 1]].y; 

     lenght += vector_length(v1); 
     length += vector_length(v2); 
     break; 
    } 
    v1.x = b[lower[i + 1]].x - b[lower[i]].x; 
    v1.y = b[lower[i + 1]].y - b[lower[i]].y; 

    v2.x = b[lower[i + 2]].x - b[lower[i]].x; 
    v2.y = b[lower[i + 2]].y - b[lower[i]].y; 
    in = ccw(v1, v2); 
    if (in == 1) 
    { 
     length += vector_length(v1); 
     v3 = v2; 
     v4 = v1; 
    } 
    if (in == -1) 
    { 
     length -= vector_length(v4); 
     if (v3.x != 0 && v3.y != 0) 
     { 
      length += vector_length(v3); 
      v3.x = 0; v3.y = 0; 
     } 
     else 
     { 
      length += vector_length(v2); 

     } 


    } 
} 

printf("%.3lf", length); 

return 0; 
} 

das Problem, dass im letzten Teil, wo ich versuche, die Länge zu berechnen ... Ich weiß nur nicht, wie it..no Rolle, zu beenden, was Ich versuche es funktioniert nie so wie ich es möchte. Könnt ihr mir einen Rat geben?

Answer 1

Ich kann keine Standard-Antwort sehen, also hier der Algorithmus:

einen Punkt etwa Wolke in der Mitte des Punktes wählen. Dann sortiere die Punkte radial nach dem Winkel von der Mitte. Der oberste Punkt muss sich in der konvexen Hülle befinden, also definieren Sie ihn als einen Winkel von 0.0 und als erster in der Liste.

Jetzt gehen Sie aber. Setzen Sie Punkt 2 in die "vorläufige" Rumpfliste. Dann überprüfen Sie Punkt 3. Wenn der Winkel P1-P2-P3 konkav ist (relativ zum Mittelpunkt), entfernen Sie P2 aus der Liste, wenn es konvex ist, behalten Sie es bei. Fahren Sie so fort, indem Sie Punkte zurückverfolgen und entfernen, wenn sie konkav werden. Sie brauchen nur zwei Punkte in Ihrer "vorläufigen" Liste, sobald Sie drei haben, werden sie definitiv.

Sie stoppen, wenn Sie den vollen Kreis gehen und zurück zu P1.