凸包のC言語実装

参考文献

しっかり学ぶ数理最適化　モデルからアルゴリズムまで
梅谷俊治・著
発行 2020/10/23

参考ページ

準備

オンラインコンパイラを使用します。

ソースコード

sample.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20

typedef struct {
    double x, y;
} Point;

Point points[N];

int cross_product(Point a, Point b, Point c) {
    double y1 = b.y - a.y;
    double y2 = c.y - a.y;
    double x1 = b.x - a.x;
    double x2 = c.x - a.x;
    return y2 * x1 - y1 * x2;
}

void convex_hull() {
    int start = 0, current_point, next_point, i;
    for (i = 1; i < N; i++) {
        if (points[i].y < points[start].y) {
            start = i;
        }
    }

    current_point = start;
    do {
        printf("(%f, %f)\n", points[current_point].x, points[current_point].y);
        next_point = (current_point + 1) % N;
        for (i = 0; i < N; i++) {
            if (cross_product(points[current_point], points[next_point], points[i]) > 0) {
                next_point = i;
            }
        }
        current_point = next_point;
    } while (current_point != start);
}

int main() {
    srand(time(0));
    for (int i = 0; i < N; i++) {
        points[i].x = (double)rand() / RAND_MAX;
        points[i].y = (double)rand() / RAND_MAX;
    }
    convex_hull();
    return 0;
}