Algorithms 01

leftright.c

#include <stdio.h>

typedef struct {
  float x, y;
} vec2;

float vec2_cross(vec2 a, vec2 b) {
	return a.x * b.y - a.y * b.x;
}

vec2 vec2_sub(vec2 a, vec2 b) {
	vec2 r;
	r.x = a.x - b.x;
	r.y = a.y - b.y;
	return r;
}

int left_or_right(float cp) {
	if (cp > 0) return 1;
	else if (cp < 0) return -1;
	else return 0;
}

#define CAP 1024

typedef struct {
	vec2 vs[CAP];
	int len;
} vec2_arr;

void vec2_arr_add(vec2_arr *va, vec2 v) {
	va->vs[va->len] = v;
	va->len++;
}

void vec2_arr_print(vec2_arr *va) {
	int i;
	for (i = 0; i < va->len; i++) {
		printf("%f %f\n", va->vs[i].x, va->vs[i].y);
	}
}

void assign_left_right(vec2_arr *ps, vec2 a, vec2 b, vec2_arr *sl, vec2_arr *sr, vec2_arr *sc) {
	int i, lrc;
	vec2 bma = vec2_sub(b, a);
	vec2 p, pma;
	float cp;
	for (i = 0; i < ps->len; i++) {
		p = ps->vs[i];
		pma = vec2_sub(p, a);
		cp = vec2_cross(p, b);
		if (cp < 0) vec2_arr_add(sr, p);
		else if (cp > 0) vec2_arr_add(sl, p);
		else vec2_arr_add(sc, p);
	}
}

vec2 vec2_make(float x, float y) {
	vec2 r;
	r.x = x;
	r.y = y;
	return r;
}

int main(int argc, const char **argv) {
	vec2_arr ps, sl, sr, sc;
	vec2 a, b;
	ps.len = sl.len = sr.len = sc.len = 0;
	vec2_arr_add(&ps, vec2_make(-10, 20));
	vec2_arr_add(&ps, vec2_make(10, 20));
	vec2_arr_add(&ps, vec2_make(10, -20));
	vec2_arr_add(&ps, vec2_make(20, -5));
	int i, j;
	for (i = 0; i < ps.len; i++) {
		for (j = 0; j < ps.len; j++) {
			if (i == j) continue;
			a = ps.vs[i];
			b = ps.vs[j];
			sl.len = sr.len = sc.len = 0;
			assign_left_right(&ps, a, b, &sl, &sr, &sc);
			if (sl.len == 0 && sc.len == 2) {
				puts("found!");
				printf("%f %f\n", a.x, a.y);
				printf("%f %f\n", b.x, b.y);
				return 0;
			}
		}
	}
}