Convex hull: Difference between revisions

Content added Content deleted

Inline

@@ Line 107: / Line 107: @@
 =={{header|C}}==
 {{trans|C++}}
-<lang C>#include <stdbool.h>
+<lang C>#include <assert.h>
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 typedef struct tPoint {
     int x, y;
 } Point;
-typedef struct tNode {
-    Point data;
-    struct tNode *next;
-} Node;
 bool ccw(const Point *a, const Point *b, const Point *c) {
     return (b->x - a->x) * (c->y - a->y)
          > (b->y - a->y) * (c->x - a->x);
 }
-int comp(const void *lhs, const void *rhs) {
+int comparePoints(const void *lhs, const void *rhs) {
-    Point lp = *((Point *)lhs);
+    const Point* lp = (const Point *)lhs;
-    Point rp = *((Point *)rhs);
+    const Point* rp = (const Point *)rhs;
-    if (lp.x < rp.x) return -1;
+    if (lp->x < rp->x)
-    if (rp.x < lp.x) return 1;
+        return -1;
+    if (rp->x < lp->x)
+        return 1;
+    if (lp->y < rp->y)
+        return -1;
+    if (rp->y < lp->y)
+        return 1;
     return 0;
 }
-void freeNode(Node *ptr) {
+void fatal(const char* message) {
-    if (ptr == NULL) {
+    fprintf(stderr, "%s\n", message);
-        return;
+    exit(1);
-    }
-    freeNode(ptr->next);
-    ptr->next = NULL;
-    free(ptr);
 }
+void* xmalloc(size_t n) {
-Node* pushBack(Node *ptr, Point data) {
-    Node *tmp = ptr;
+    void* ptr = malloc(n);
+    if (ptr == NULL)
-    if (ptr == NULL) {
+        fatal("Out of memory");
-        ptr = (Node*)malloc(sizeof(Node));
-        ptr->data = data;
-        ptr->next = NULL;
-        return ptr;
-    }
-    while (tmp->next != NULL) {
-        tmp = tmp->next;
-    }
-    tmp->next = (Node*)malloc(sizeof(Node));
-    tmp->next->data = data;
-    tmp->next->next = NULL;
     return ptr;
 }
+void* xrealloc(void* p, size_t n) {
-Node* popBack(Node *ptr) {
-    Node *tmp = ptr;
+    void* ptr = realloc(p, n);
+    if (ptr == NULL)
-    if (ptr == NULL) {
+        fatal("Out of memory");
-        return NULL;
-    }
-    if (ptr->next == NULL) {
-        free(ptr);
-        return NULL;
-    }
-    while (tmp->next->next != NULL) {
-        tmp = tmp->next;
-    }
-    free(tmp->next);
-    tmp->next = NULL;
     return ptr;
 }
-void print(Node *ptr) {
+void printPoints(const Point* points, int len) {
     printf("[");
-    if (ptr != NULL) {
+    if (len > 0) {
-        printf("(%d, %d)", ptr->data.x, ptr->data.y);
+        const Point* ptr = points;
-        ptr = ptr->next;
+        const Point* end = points + len;
+        printf("(%d, %d)", ptr->x, ptr->y);
-    }
-    while (ptr != NULL) {
+        ++ptr;
-        printf(", (%d, %d)", ptr->data.x, ptr->data.y);
+        for (; ptr < end; ++ptr)
-        ptr = ptr->next;
+            printf(", (%d, %d)", ptr->x, ptr->y);
     }
     printf("]");
 }
+Point* convexHull(Point p[], int len, int* hsize) {
+    if (len == 0) {
+        *hsize = 0;
+        return NULL;
+    }
+    int i, size = 0, capacity = 4;
-Node* convexHull(int len, Point p[]) {
+    Point* hull = xmalloc(capacity * sizeof(Point));
-    Node *h = NULL;
-    Node *hptr = NULL;
-    size_t hLen = 0;
-    int i;
-    qsort(p, len, sizeof(Point), comp);
+    qsort(p, len, sizeof(Point), comparePoints);
     /* lower hull */
     for (i = 0; i < len; ++i) {
-        while (hLen >= 2) {
+        while (size >= 2 && !ccw(&hull[size - 2], &hull[size - 1], &p[i]))
-            hptr = h;
+            --size;
-            while (hptr->next->next != NULL) {
+        if (size == capacity) {
-                hptr = hptr->next;
+            capacity *= 2;
+            hull = xrealloc(hull, capacity * sizeof(Point));
-            }
-            if (ccw(&hptr->data, &hptr->next->data, &p[i])) {
-                break;
-            }
-            h = popBack(h);
-            hLen--;
         }
+        assert(size >= 0 && size < capacity);
-        h = pushBack(h, p[i]);
+        hull[size++] = p[i];
-        hLen++;
     }
     /* upper hull */
+    int t = size + 1;
     for (i = len - 1; i >= 0; i--) {
-        while (hLen >= 2) {
+        while (size >= t && !ccw(&hull[size - 2], &hull[size - 1], &p[i]))
-            hptr = h;
+            --size;
-            while (hptr->next->next != NULL) {
+        if (size == capacity) {
-                hptr = hptr->next;
+            capacity *= 2;
+            hull = xrealloc(hull, capacity * sizeof(Point));
-            }
-            if (ccw(&hptr->data, &hptr->next->data, &p[i])) {
-                break;
-            }
-            h = popBack(h);
-            hLen--;
         }
+        assert(size >= 0 && size < capacity);
-        h = pushBack(h, p[i]);
+        hull[size++] = p[i];
-        hLen++;
     }
+    --size;
-    popBack(h);
+    assert(size >= 0);
+    hull = xrealloc(hull, size * sizeof(Point));
-    return h;
+    *hsize = size;
+    return hull;
 }
 int main() {
     Point points[] = {
@@ Line 253: / Line 216: @@
         {-3, -9}, { 0, 11}, {-9, -3}, {-4, -2}, {12, 10}
     };
+    int hsize;
-    Node *hull = convexHull(sizeof(points) / sizeof(Point), points);
+    Point* hull = convexHull(points, sizeof(points)/sizeof(Point), &hsize);
-    printf("Convex Hull: ");
+    printf("\nConvex Hull: ");
-    print(hull);
+    printPoints(hull, hsize);
     printf("\n");
+    free(hull);
-    freeNode(hull);
-    hull = NULL;
     return 0;
 }</lang>