rendered paste body#include <stdio.h>#include <ncurses.h>#include <stdlib.h>#include <math.h>#define WIDTH 30#define HEIGHT 10 #define K 3#define round(x) ((x)>=0?(long)((x)+0.5):(long)((x)-0.5))#define min(X, Y) ((X) < (Y) ? (X) : (Y))int startx = 0;int starty = 0;struct list_elm { int x; int y; int len; struct list_elm* next;};struct pt { int x; int y;};struct list_elm* add_new_point(struct list_elm* head, MEVENT* event);void drop_into_array(struct list_elm* head, int points_x[], int points_y[]);void kmeans(struct pt centers[],struct list_elm* head);void kmeans_with_pts(struct pt centers[], int k, int len, int points_x[], int points_y[]);struct pt* find_centroid(int len, int points_x[], int points_y[]);void display_points(int len, int points_x[], int points_y[]);void print_menu(WINDOW *menu_win, int highlight);void random_point_assign(struct pt center[], int k, int len, int points_x[], int points_y[]);void group_points(struct pt centers[], int groupings[], int k, int len, int points_x[], int point_y[]);double rate_cluster(struct pt centers[],int groupings[], int k,int len,int points_x[],int points_y[]);void make_new_centers(struct pt centers[], int groupings[],int k, int len, int points_x[], int points_y[]);double dist(int x1, int y1, int x2, int y2);int min_pt(struct pt centers[], int x, int y, int k); // find index of closet centerdouble cdf(double x, double m, double s);int main(){ WINDOW *menu_win; int highlight = 1; int choice = 0; int c; MEVENT event; // struct list_elm* curr; struct list_elm* head = NULL; initscr(); clear(); noecho(); cbreak(); /* Line buffering disabled. pass on everything */ startx = (80 - WIDTH) / 2; starty = (24 - HEIGHT) / 2; menu_win = newwin(HEIGHT, WIDTH, starty, startx); keypad(menu_win, TRUE); mvprintw(0, 0, "Use the mouse to make points. Hit space to cluster points"); refresh(); curs_set(0); //print_menu(menu_win, highlight); wrefresh(menu_win); mousemask(ALL_MOUSE_EVENTS, NULL); while(1) { c = wgetch(menu_win); switch(c) { case KEY_MOUSE: getmouse(&event); mvprintw(24,0,"Mouse at %d %d",event.x,event.y); mvprintw(event.y,event.x,"x"); head = add_new_point(head,&event); refresh(); break; case 32: clear(); mvprintw(0, 0, "Use the mouse to make points. Hit space to cluster points"); mvprintw(24,0,"Space pressed\n"); refresh(); if (head != NULL) { struct pt centers[K]; kmeans(centers,head); head = NULL; } refresh(); break; default: break; } //print_menu(menu_win, highlight); wrefresh(menu_win); if(c == 10) /* User did a choice come out of the infinite loop */ break; } clrtoeol(); refresh(); endwin(); return 0;}void kmeans(struct pt centers[],struct list_elm* head) { int len = head->len; int points_x[len]; int points_y[len]; drop_into_array(head,points_x,points_y); head = NULL; kmeans_with_pts(centers, K, len, points_x, points_y); display_points(len,points_x,points_y); start_color(); use_default_colors(); // assume_default_colors(-1,-1); init_pair(1, COLOR_RED, COLOR_WHITE); attron(COLOR_PAIR(1)); int i=0; for (i=0; i<min(K,len);i++) { struct pt center = centers[i]; mvprintw(center.y,center.x,"o"); } attroff(COLOR_PAIR(1));}void kmeans_with_pts(struct pt centers[], int k, int len, int points_x[], int points_y[]) { int i=0; int groupings[len]; //array indexed with which cluster a point is in random_point_assign(centers,k,len,points_x,points_y); group_points(centers, groupings, k, len, points_x, points_y); while(i<30) { make_new_centers(centers,groupings,k,len,points_x,points_y); group_points(centers, groupings, k, len, points_x, points_y); i++; }}void random_point_assign(struct pt center[], int k, int len, int points_x[], int points_y[]) { int i=0; int rp; for (i=0; i<min(k,len); i++) { rp = rand()%(len-i); center[i].x = points_x[rp]; center[i].y = points_y[rp]; points_x[rp] = points_x[len-i-1]; points_y[rp] = points_y[len-i-1]; points_x[len-i-1] = center[i].x; points_y[len-i-1] = center[i].y; }}void make_new_centers(struct pt centers[], int groupings[],int k, int len, int points_x[], int points_y[]) { int i=0; int gr_len[k]; for(i=0;i<min(k,len);i++) { centers[i].x = 0; centers[i].y = 0; gr_len[i] = 0; } for(i=0;i<len;i++) { centers[groupings[i]].x += points_x[i]; centers[groupings[i]].y += points_y[i]; gr_len[groupings[i]]++; } for(i=0;i<min(k,len);i++) { centers[i].x = round(centers[i].x / gr_len[i]); centers[i].y = round(centers[i].y / gr_len[i]); }}double cdf(double x, double m, double s) { return 0.5*(1+erf((x-m)/(s*sqrt(2.0))));}double anderson_darling(double x[], int n) { return 0.0;}double rate_cluster(struct pt centers[],int groupings[], int k,int len,int points_x[],int points_y[]) { double sum = 0; int i=0; struct pt* c; for (i=0;i<len;i++) { c = &(centers[groupings[i]]); sum += dist(c->x,c->y,points_x[i],points_y[i]); } return sum;}void group_points(struct pt centers[], int groupings[], int k, int len, int points_x[], int points_y[]) { int i=0; for(i=0; i<len; i++) { groupings[i] = min_pt(centers,points_x[i],points_y[i],min(k,len)); }}int min_pt(struct pt centers[], int x, int y, int k) { int best = 0; int i=0; for (i=1; i<k; i++) { if (dist(x,y,centers[i].x,centers[i].y) < dist(x,y,centers[best].x,centers[best].y)) best = i; } return best;}double dist(int x1, int y1, int x2, int y2) { return sqrt((x2 - x1)*(x2-x1) + (y2 - y1)*(y2 - y1));}struct list_elm* add_new_point(struct list_elm* head, MEVENT* event) { struct list_elm* curr = malloc(sizeof(struct list_elm)); if (head == NULL) { curr->len = 1; } else { curr->len = head->len + 1; } curr->x = event->x; curr->y = event->y; curr->next = head; return curr;}void drop_into_array(struct list_elm* head, int points_x[], int points_y[]) { struct list_elm* curr; while (head != NULL) { points_x[head->len - 1] = head->x; points_y[head->len - 1] = head->y; curr = head->next; free(head); head = curr; }}struct pt* find_centroid(int len, int points_x[], int points_y[]) { struct pt* center = malloc(sizeof(struct pt)); int i=0; center->x=0; center->y=0; for(i=0;i<len;i++) { mvprintw(points_y[i],points_x[i],"x"); // reprint points center->x += points_x[i]; center->y += points_y[i]; } center->x = round(center->x / len); center->y = round(center->y / len); return center;}void display_points(int len, int points_x[], int points_y[]) { int i=0; for(i=0;i<len;i++) { mvprintw(points_y[i],points_x[i],"x"); // reprint points }}void print_menu(WINDOW *menu_win, int highlight){ int x, y, i; x = 2; y = 2; box(menu_win, 0, 0); wrefresh(menu_win);}