Rosetta Code

Convex hull: Difference between revisions

Page Discussion

Convex hull (view source)

Revision as of 11:51, 30 December 2020

225 bytes removed ,  3 years ago
C code replaced by more accurate translation
m (→‎plot: c)
(C code replaced by more accurate translation)
Line 107:
=={{header|C}}==
{{trans|C++}}
<lang C>#include <stdboolassert.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 compcomparePoints(const void *lhs, const void *rhs) {
const Point* lp = *((const Point *)lhs);
const Point* rp = *((const Point *)rhs);
if (lp.->x < rp.->x) return -1;
if (rp.x < lp.x) 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 freeNodefatal(Nodeconst char*ptr message) {
if fprintf(ptrstderr, =="%s\n", NULLmessage) {;
returnexit(1);
}
 
freeNode(ptr->next);
ptr->next = NULL;
free(ptr);
}
 
void* xmalloc(size_t n) {
Node* pushBack(Node *ptr, Point data) {
Node void*tmp ptr = ptrmalloc(n);
if (ptr == NULL)
 
if fatal(ptr"Out ==of NULLmemory") {;
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 void*tmp ptr = ptrrealloc(p, n);
if (ptr == NULL)
 
if fatal(ptr"Out ==of NULLmemory") {;
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 printprintPoints(Nodeconst Point*ptr points, int len) {
printf("[");
if (ptrlen !=> NULL0) {
printf("(%d,const %d)",Point* ptr->data.x, ptr->data.y)= points;
ptrconst Point* end = ptr->nextpoints + len;
printf("(%d, %d)", ptr->x, ptr->y);
}
while (ptr != NULL) {++ptr;
printf(",for (%d, %d)",; ptr->data.x, < end; ++ptr->data.y);
ptr = printf(", (%d, %d)", ptr->x, ptr->nexty);
}
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 (hLensize >= 2) {&& !ccw(&hull[size - 2], &hull[size - 1], &p[i]))
hptr = h--size;
whileif (hptr->next->nextsize !== NULLcapacity) {
capacity hptr *= hptr->next2;
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);
 
hhull[size++] = pushBack(h, p[i]);
hLen++;
}
 
/* upper hull */
int t = size + 1;
for (i = len - 1; i >= 0; i--) {
while (hLensize >= t && !ccw(&hull[size - 2)], {&hull[size - 1], &p[i]))
hptr = h--size;
whileif (hptr->next->nextsize !== NULLcapacity) {
capacity hptr *= hptr->next2;
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);
 
hhull[size++] = pushBack(h, p[i]);
hLen++;
}
--size;
 
popBackassert(hsize >= 0);
hull = xrealloc(hull, size * sizeof(Point));
return h;
*hsize = size;
return hull;
}
 
int main() {
Point points[] = {
Line 253 ⟶ 216:
{-3, -9}, { 0, 11}, {-9, -3}, {-4, -2}, {12, 10}
};
int hsize;
 
Node Point* hull = convexHull(points, sizeof(points) / sizeof(Point), points&hsize);
printf("Convex\nConvex Hull: ");
printprintPoints(hull, hsize);
printf("\n");
free(hull);
 
freeNode(hull);
hull = NULL;
 
return 0;
}</lang>
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/258640"