qrohlf/2D-Clipping.md

## 2D-Clipping.md

      
    Raw
  

              2D-Clipping.md
            
          
    ##Rad 2d Clipping
To try it out:
git clone https://gist.github.com/7345132.git
cd 7345132 
acom Lab3.c Drawframework.c && ./a.out better_house.xy

Then click a convex clipping window with your mouse in a clockwise direction.
Click the red square in the upper right corner to finish the polygon and clip the house.

  
## better_house.xy
25
210.000000 180.000000
210.000000 330.000000
330.000000 450.000000
450.000000 330.000000
450.000000 180.000000
405.000000 375.000000
375.000000 405.000000
375.000000 480.000000
405.000000 480.000000
285.000000 180.000000
360.000000 195.000000
285.000000 195.000000
360.000000 180.000000
300.000000 195.000000
345.000000 195.000000
345.000000 285.000000
300.000000 285.000000
375.000000 285.000000
375.000000 225.000000
435.000000 225.000000
435.000000 285.000000
270.000000 285.000000
225.000000 285.000000
225.000000 225.000000
270.000000 225.000000
7
4    1 0 4 3
3    1 3 2
4    5 8 7 6
4    22 21 24 23
4    17 20 19 18
4    9 11 10 12
4    13 16 15 14


0.500000 0.200000 0.000000
0.800000 0.200000 0.100000
0.500000 0.200000 0.000000
0.800000 0.800000 0.300000
0.800000 0.800000 0.300000
0.800000 0.200000 0.100000
1.000000 0.300000 0.500000

## D2d_matrix.c
#include <D2d_matrix.h>


/*
 * Print a 3x3 matrix to stdout
 * Tested, working
 */
int D2d_print_mat (double a[3][3]) {
    for (int i = 0; i < 3; i++) {
        printf("%10.3f %10.3f %10.3f \n", a[i][0], a[i][1], a[i][2]);
    }
    return 0;
}

/*
 * Copy the contents of b into a
 * Tested, working
 */
int D2d_copy_mat (double a[3][3], double b[3][3]) {
    for (int i = 0; i < 3; i++) {
        for(int j=0; j < 3; j++) {
            a[i][j] = b[i][j];
        }
    }
    return 0; //What are we supposed to return here?
}

/*
 * res = a.b
 * SAFE: will not modify a or b.
 * Tested, working
 */
int D2d_mat_mult (double res[3][3], double a[3][3], double b[3][3]) {
    double B[3][3];
    D2d_transpose(b, B);
    double A[3][3];
    D2d_copy_mat(A, a);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            res[i][j] = D2d_dot(A[i], B[j]);
        }
    }
    return 0; //What are we supposed to return here?
}

/*
 * Write an identity matrix to a
 * Tested, working
 */
int D2d_make_identity (double a[3][3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            a[i][j] = (i == j);
        }
    }
    return 0; //TODO: implement this function and remove this comment
}

/*
 * Generate a translation matrix.
 * a = translation*a
 * b = b*translation_inverse
 * DANGER WILL ROBINSON: THIS FUNCTION HAS NOT BEEN TESTED
 */
int D2d_translate (double a[3][3], double b[3][3], double dx, double dy) {
    double trans[3][3] = {
        {1, 0, dx},
        {0, 1, dy},
        {0, 0, 1}
    };
    double trans_inv[3][3] = {
        {1, 0, -dx},
        {0, 1, -dy},
        {0, 0, 1}
    };
    D2d_mat_mult(a, trans, a);
    D2d_mat_mult(b, b, trans_inv);
    return 0; //TODO: implement this function and remove this comment
}

int D2d_scale (double a[3][3], double b[3][3], double sx, double sy) {
    double scale[3][3] = {
        {sx, 0, 0},
        {0, sy, 0},
        {0, 0, 1}
    };
    double scale_inv[3][3] = {
        {1/sx, 0, 0},
        {0, 1/sy, 0},
        {0, 0, 1}
    };
    D2d_mat_mult(a, scale, a);
    D2d_mat_mult(b, b, scale_inv);
    return 0; //TODO: implement this function and remove this comment
}

int D2d_rotate (double a[3][3], double b[3][3], double radians) {
    double rotate[3][3] = {
        {cos(radians), -sin(radians), 0},
        {sin(radians), cos(radians), 0},
        {0, 0, 1}
    };
    double rotate_inv[3][3] = {
        {cos(radians), sin(radians), 0},
        {-sin(radians), cos(radians), 0},
        {0, 0, 1}
    };
    D2d_mat_mult(a, rotate, a);
    D2d_mat_mult(b, b, rotate_inv);
    return 0; //TODO: implement this function and remove this comment
}

// DANGER WILL ROBINSON, NOT TESTED
int D2d_negate_x (double a[3][3], double b[3][3]) {
    double negate[3][3] = {
        {-1, 0, 0},
        {0, 1, 0},
        {0, 0, 1}
    };
    D2d_mat_mult(a, negate, a);
    D2d_mat_mult(b, b, negate);
    return 0; //TODO: implement this function and remove this comment
}

// DANGER WILL ROBINSON, NOT TESTED
int D2d_negate_y (double a[3][3], double b[3][3]) {
    double negate[3][3] = {
        {1, 0, 0},
        {0, -1, 0},
        {0, 0, 1}
    };
    D2d_mat_mult(a, negate, a);
    D2d_mat_mult(b, b, negate);
    return 0; //TODO: implement this function and remove this comment
}

int D2d_mat_mult_points (double *X, double *Y,
                         double m[3][3],
                         double *x, double *y, int numpoints) {
    double coord[3] = {0, 0, 1};

    for (int i = 0; i < numpoints; i++) {
        coord[0] = x[i];
        coord[1] = y[i];
        X[i] = D2d_dot(m[0], coord);
        Y[i] = D2d_dot(m[1], coord);
    }

    return 0; //TODO: implement this function and remove this comment
}

/*
 * Transpose a into b
 */
int D2d_transpose (double a[3][3], double b[3][3]) {
    for (int i = 0; i < 3; i++) {
        for(int j=0; j < 3; j++) {
            b[i][j] = a[j][i];
        }
    }
    return 0; //What are we supposed to return here?
}

double D2d_dot (double a[3], double b[3]) {
    return a[0]*b[0]+a[1]*b[1]+a[2]*b[2];
}

## D2d_matrix.h
#ifndef D2d_matrix_stuff
#define D2d_matrix_stuff

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


/*

 ( x')          (x)
 ( y')  =   M * (y)
 ( 1 )          (1)


instead of (x',y',1) = (x,y,1) * M

*/

int D2d_print_mat (double a[3][3]) ;

int D2d_copy_mat (double a[3][3], double b[3][3]) ;
// a = b

int D2d_mat_mult (double res[3][3], double a[3][3], double b[3][3]) ;
// res = a * b
// this is SAFE, i.e. the user can make a call such as
// D2d_mat_mult(p,  p,q) or D2d_mat_mult(p,  q,p) or  D2d_mat_mult(p, p,p)

int D2d_make_identity (double a[3][3]) ;
// a = I

int D2d_translate (double a[3][3], double b[3][3], double dx, double dy) ;
// a = translation*a
// b = b*translation_inverse

int D2d_scale (double a[3][3], double b[3][3], double sx, double sy) ;
// a = scale*a
// b = b*scale_inverse

int D2d_rotate (double a[3][3], double b[3][3], double radians) ;
// a = rotate*a
// b = b*rotate_inverse

int D2d_negate_x (double a[3][3], double b[3][3]) ;
// negate the x....reflects in the y-axis
// a = reflect*a
// b = b*reflect_inverse

int D2d_negate_y (double a[3][3], double b[3][3]) ;
// negate the y....reflects in the x-axis
// a = reflect*a
// b = b*reflect_inverse

int D2d_mat_mult_points (double *X, double *Y,
                         double m[3][3],
                         double *x, double *y, int numpoints) ;
// |X0 X1 X2 ...|       |x0 x1 x2 ...|
// |Y0 Y1 Y2 ...| = m * |y0 y1 y2 ...|
// | 1  1  1 ...|       | 1  1  1 ...|

// SAFE, user may make a call like D2d_mat_mult_points (x,y, m, x,y, n) ;

int D2d_transpose (double a[3][3], double b[3][3]);

double D2d_dot (double a[3], double b[3]);
// [a, b, c] [d, e, f] -> a*d+b*c+c*f

#endif

## Drawframework.c
#include "Drawframework.h"
/*
 * constructs an object from a list of points, connections, and colors
 */
void read_object2d_from_file(FILE* f, object2d *obj) {
    // Get the points
    fscanf(f, "%d", &obj->n);
    for (int i=0; i<obj->n; i++) {
        fscanf(f, "%lf %lf", &obj->xs[i], &obj->ys[i]);
    }


    // Get the shapes
    fscanf(f, "%d", &obj->num_shapes);
    for (int i=0; i<obj->num_shapes; i++) {
        fscanf(f, "%d", &obj->shapes[i].n);
        for (int j=0; j<obj->shapes[i].n; j++) {
            fscanf(f, "%d", &obj->shapes[i].vertices[j]);
        }
    }

    // Get the colors
    for (int i=0; i<obj->num_shapes; i++) {
        fscanf(f, "%lf %lf %lf", &obj->shapes[i].R, &obj->shapes[i].G, &obj->shapes[i].B);
    }
}

void read_shape_from_file(FILE* f, shape* shape) {
    fscanf(f, "%d\n", &shape->n);
    for (int i=0; i<shape->n; i++) {
        fscanf(f, "%d", &shape->vertices[i]);
    }
}

void draw_object2d(object2d* obj) {
    for (int i=0; i<obj->num_shapes; i++) {
        draw_shape(&obj->shapes[i], obj, true);
    }
}

void draw_object2d_wireframe(object2d* obj) {
    for (int i=0; i<obj->num_shapes; i++) {
        draw_shape(&obj->shapes[i], obj, false);
    }
}

void draw_shape(shape* s, object2d* obj, int fill) {
    double x[1000];
    double y[1000];
    int point_index;
    for (int j=0; j<s->n; j++) {
        point_index = s->vertices[j];
        x[j] = obj->xs[point_index];
        y[j] = obj->ys[point_index];
    }
    G_rgb(s->R, s->G, s->B);
    if (fill) G_fill_polygon(x, y, s->n);
    else G_polygon(x, y, s->n);
}

/*
 * Return the intersection of line p1-p2
 * and line j1-j2
 */
void intersection(
    point2d p1,
    point2d p2,
    point2d j1,
    point2d j2,
    point2d* intersect) {
    printf("line 1: {%f, %f} to {%f, %f}\n", p1.x, p1.y, p2.x, p2.y);
    // Slope of line p (mp)
    double mp = (p2.y - p1.y) / (p2.x - p1.x);
    printf("Slope of line 1 is %f\n", mp);
    // Slope of line j (mj)
    double mj = (j2.y - j1.y) / (j2.x - j1.x);
    printf("Slope of line 2 is %f\n", mj);
    //p1.y = mp (p1.x) + bp
    double bp = p1.y - mp*p1.x;
    printf("Intercept of line 1 is %f\n", bp);
    //j1.y = mj (j1.x) + bj
    double bj = j1.y - mj*j1.x;
    printf("Intercept of line 2 is %f\n", bj);
    if (!isfinite(mp)) {
        //p1-p2 is a vertical line
        intersect->x = p1.x;
        intersect->y = mj * intersect->x + bj;
        return;
    }
    if (!isfinite(mj)) {
        //j1-j2 is a vertical line
        intersect->x = j1.x;
        intersect->y = mp * intersect->x + bp;
        return;
    }
    //y = mp * x + bp
    //y = mj * x + bj
    //mj*x + bj = mp*x + bp
    //mj*x - mp*x = bp - bj
    //x(mj - mp) = (bp - bj)
    intersect->x = (bp - bj)/(mj - mp);
    printf("Intersection x is %f\n", intersect->x);
    intersect->y = mp * intersect->x + bp;
    printf("Intersection y is %f\n", intersect->y);
}

void clip_object2d(object2d* obj, polygon* win) {
    for (int j=0; j<win->n; j++) {
        point2d p3 = {win->xs[j], win->ys[j]};
        point2d p4 = {win->xs[(j+1)%win->n], win->ys[(j+1)%win->n]};
        clip_line(obj, p3, p4);
    }
}

// Clip object2d fig by a single line
void clip_line(object2d* fig, point2d l1, point2d l2) {
    shape* s;
    for (int i=0; i<fig->num_shapes; i++) {
        clip_shape(&fig->shapes[i], fig, l1, l2);
    }
}

void clip_shape(shape* fig, object2d* parent, point2d l1, point2d l2) {
    shape out = {0, {}, fig->R, fig->G, fig->B};
    int i1, i2;
    for (int i=0; i<fig->n; i++) {
        //For each line in the shape...
        i1 = fig->vertices[i];
        i2 = fig->vertices[(i+1)%fig->n];
        point2d p1 = {parent->xs[i1], parent->ys[i1]};
        point2d p2 = {parent->xs[i2], parent->ys[i2]};
        if (isRight(p1, l1, l2)) {
            //If point2d p1 is inside the clipping line, add it to the output shape
            out.vertices[out.n] = i1;
            out.n++;
        }
        point2d intersect;
        intersection(p1, p2, l1, l2, &intersect);
        if (in_range(intersect.x, p1.x, p2.x) && in_range(intersect.y, p1.y, p2.y)) {

            parent->xs[parent->n] = intersect.x;
            parent->ys[parent->n] = intersect.y;
            out.vertices[out.n] = parent->n;
            parent->n++;
            out.n++;
        }
    }
    *fig = out;
}

// Use the cross product to tell if a point2d is on the right or colinear of the line bc
int isRight(point2d a, point2d b, point2d c){
     return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) <= 0;
}

/*
 * Return whether x is included in [a, b]
 */
int in_range(double x, double a, double b) {
    double range[] = {a, b};
    double lower = min(range, 2);
    double upper = max(range, 2);
    return (x <= upper && x >= lower);
}

/*
 * Return the smallest element of an array of doubles containing n elements.
 * n must be >0.
 */
double min(double* arr, int n) {
    double min = arr[0];
    for(int i=0; i<n; i++) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

/*
 * Return the largest element of an array of doubles containing n elements.
 * n must be >0.
 */
double max(double* arr, int n) {
    double max = arr[0];
    for(int i=0; i<n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

## Drawframework.h
#ifndef DRAWFRAMEWORK_H
#define DRAWFRAMEWORK_H
#include <FPT.h>
#define true 1
#define false 0

/*
 * shape definition. Needs to be wrapped in a 2dObject or 3dObject to work.
 */
typedef struct {
    int n;                  //Number of points in the shape
    int vertices[20];     //List of points to connect in the parent 2dObject to make the shape
    double R;
    double G;
    double B;
} shape;

/*
 * polygon definition. Standalone way to represent a single 2d polygon
 */
 typedef struct {
    int n;                  //Number of points in the shape
    double xs[10000];
    double ys[10000];
    double R;
    double G;
    double B;
} polygon;

/*
 * 2d object definition. Maxes out at 1000 points/100 shapes.
 */
typedef struct  {
    int num_shapes;
    int n;                  //Number of points in the object
    double xs[10000];
    double ys[10000];
    shape shapes[10000];
} object2d;

/*
 * 2d point definition. Useful for comparisons and return values.
 */
typedef struct {
    double x;
    double y;
} point2d;

void read_object2d_from_file(FILE* f, object2d *obj);
void read_shape_from_file(FILE* f, shape* shape);
void draw_object2d(object2d* obj);
void draw_object2d_wireframe(object2d* obj);
void clip_object2d(object2d* obj, polygon* win);
void clip_line(object2d* fig, point2d l1, point2d l2);
void clip_shape(shape* fig, object2d* parent, point2d l1, point2d l2);
int isRight(point2d a, point2d b, point2d c);
void draw_shape(shape* s, object2d* obj, int fill);
int in_range(double x, double a, double b);
double min(double* arr, int n);
double max(double* arr, int n);

#endif

## Lab3.c
#include <FPT.h>
#include "drawframework.h"
#define true 1
#define false 0
#define CANVAS_X 600
#define CANVAS_Y 600

void click_polygon(polygon* fig) {
    G_rgb(.5, 0, 0);
    G_fill_rectangle(580, 580, 600, 600);
    G_rgb(0.8, 0.8, 0.8);
    int i=0;
    double p[] = {0, 0};
    while(true) {
        G_wait_click(p);
        if (p[0] > 580 && p[1] > 580) {
            break;
        }
        G_fill_circle(p[0], p[1], 2);
        fig->xs[i] = p[0];
        fig->ys[i] = p[1];
        printf("Clicked %5.0f, %5.0f\n", p[0], p[1]);
        if (i>0) G_line(fig->xs[i], fig->ys[i], fig->xs[i-1], fig->ys[i-1]);
        i++;
    }

    G_line(fig->xs[i-1], fig->ys[i-1], fig->xs[0], fig->ys[0]);
    printf("Done clicking polygon\n");
    fig->n = i;
}

int main(int argc, char const *argv[]) {
    G_init_graphics(CANVAS_X, CANVAS_Y);
    FILE* f = fopen(argv[1], "r");
    object2d fig;
    polygon win;
    read_object2d_from_file(f, &fig);
    draw_object2d(&fig);
    click_polygon(&win);
    clip_object2d(&fig, &win);
    G_rgb(1, 1, 1);
    G_clear();
    draw_object2d(&fig);
    G_rgb(.8, .8, .8);
    G_polygon(win.xs, win.ys, win.n);
    G_wait_key();
    return 0;
}
	25
	210.000000 180.000000
	210.000000 330.000000
	330.000000 450.000000
	450.000000 330.000000
	450.000000 180.000000
	405.000000 375.000000
	375.000000 405.000000
	375.000000 480.000000
	405.000000 480.000000
	285.000000 180.000000
	360.000000 195.000000
	285.000000 195.000000
	360.000000 180.000000
	300.000000 195.000000
	345.000000 195.000000
	345.000000 285.000000
	300.000000 285.000000
	375.000000 285.000000
	375.000000 225.000000
	435.000000 225.000000
	435.000000 285.000000
	270.000000 285.000000
	225.000000 285.000000
	225.000000 225.000000
	270.000000 225.000000
	7
	4 1 0 4 3
	3 1 3 2
	4 5 8 7 6
	4 22 21 24 23
	4 17 20 19 18
	4 9 11 10 12
	4 13 16 15 14


	0.500000 0.200000 0.000000
	0.800000 0.200000 0.100000
	0.500000 0.200000 0.000000
	0.800000 0.800000 0.300000
	0.800000 0.800000 0.300000
	0.800000 0.200000 0.100000
	1.000000 0.300000 0.500000
	#include <D2d_matrix.h>


	/*
	* Print a 3x3 matrix to stdout
	* Tested, working
	*/
	int D2d_print_mat (double a[3][3]) {
	for (int i = 0; i < 3; i++) {
	printf("%10.3f %10.3f %10.3f \n", a[i][0], a[i][1], a[i][2]);
	}
	return 0;
	}

	/*
	* Copy the contents of b into a
	* Tested, working
	*/
	int D2d_copy_mat (double a[3][3], double b[3][3]) {
	for (int i = 0; i < 3; i++) {
	for(int j=0; j < 3; j++) {
	a[i][j] = b[i][j];
	}
	}
	return 0; //What are we supposed to return here?
	}

	/*
	* res = a.b
	* SAFE: will not modify a or b.
	* Tested, working
	*/
	int D2d_mat_mult (double res[3][3], double a[3][3], double b[3][3]) {
	double B[3][3];
	D2d_transpose(b, B);
	double A[3][3];
	D2d_copy_mat(A, a);
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	res[i][j] = D2d_dot(A[i], B[j]);
	}
	}
	return 0; //What are we supposed to return here?
	}

	/*
	* Write an identity matrix to a
	* Tested, working
	*/
	int D2d_make_identity (double a[3][3]) {
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	a[i][j] = (i == j);
	}
	}
	return 0; //TODO: implement this function and remove this comment
	}

	/*
	* Generate a translation matrix.
	* a = translation*a
	* b = b*translation_inverse
	* DANGER WILL ROBINSON: THIS FUNCTION HAS NOT BEEN TESTED
	*/
	int D2d_translate (double a[3][3], double b[3][3], double dx, double dy) {
	double trans[3][3] = {
	{1, 0, dx},
	{0, 1, dy},
	{0, 0, 1}
	};
	double trans_inv[3][3] = {
	{1, 0, -dx},
	{0, 1, -dy},
	{0, 0, 1}
	};
	D2d_mat_mult(a, trans, a);
	D2d_mat_mult(b, b, trans_inv);
	return 0; //TODO: implement this function and remove this comment
	}

	int D2d_scale (double a[3][3], double b[3][3], double sx, double sy) {
	double scale[3][3] = {
	{sx, 0, 0},
	{0, sy, 0},
	{0, 0, 1}
	};
	double scale_inv[3][3] = {
	{1/sx, 0, 0},
	{0, 1/sy, 0},
	{0, 0, 1}
	};
	D2d_mat_mult(a, scale, a);
	D2d_mat_mult(b, b, scale_inv);
	return 0; //TODO: implement this function and remove this comment
	}

	int D2d_rotate (double a[3][3], double b[3][3], double radians) {
	double rotate[3][3] = {
	{cos(radians), -sin(radians), 0},
	{sin(radians), cos(radians), 0},
	{0, 0, 1}
	};
	double rotate_inv[3][3] = {
	{cos(radians), sin(radians), 0},
	{-sin(radians), cos(radians), 0},
	{0, 0, 1}
	};
	D2d_mat_mult(a, rotate, a);
	D2d_mat_mult(b, b, rotate_inv);
	return 0; //TODO: implement this function and remove this comment
	}

	// DANGER WILL ROBINSON, NOT TESTED
	int D2d_negate_x (double a[3][3], double b[3][3]) {
	double negate[3][3] = {
	{-1, 0, 0},
	{0, 1, 0},
	{0, 0, 1}
	};
	D2d_mat_mult(a, negate, a);
	D2d_mat_mult(b, b, negate);
	return 0; //TODO: implement this function and remove this comment
	}

	// DANGER WILL ROBINSON, NOT TESTED
	int D2d_negate_y (double a[3][3], double b[3][3]) {
	double negate[3][3] = {
	{1, 0, 0},
	{0, -1, 0},
	{0, 0, 1}
	};
	D2d_mat_mult(a, negate, a);
	D2d_mat_mult(b, b, negate);
	return 0; //TODO: implement this function and remove this comment
	}

	int D2d_mat_mult_points (double X, double Y,
	double m[3][3],
	double x, double y, int numpoints) {
	double coord[3] = {0, 0, 1};

	for (int i = 0; i < numpoints; i++) {
	coord[0] = x[i];
	coord[1] = y[i];
	X[i] = D2d_dot(m[0], coord);
	Y[i] = D2d_dot(m[1], coord);
	}

	return 0; //TODO: implement this function and remove this comment
	}

	/*
	* Transpose a into b
	*/
	int D2d_transpose (double a[3][3], double b[3][3]) {
	for (int i = 0; i < 3; i++) {
	for(int j=0; j < 3; j++) {
	b[i][j] = a[j][i];
	}
	}
	return 0; //What are we supposed to return here?
	}

	double D2d_dot (double a[3], double b[3]) {
	return a[0]b[0]+a[1]b[1]+a[2]*b[2];
	}
	#ifndef D2d_matrix_stuff
	#define D2d_matrix_stuff

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


	/*

	( x') (x)
	( y') = M * (y)
	( 1 ) (1)


	instead of (x',y',1) = (x,y,1) * M

	*/

	int D2d_print_mat (double a[3][3]) ;

	int D2d_copy_mat (double a[3][3], double b[3][3]) ;
	// a = b

	int D2d_mat_mult (double res[3][3], double a[3][3], double b[3][3]) ;
	// res = a * b
	// this is SAFE, i.e. the user can make a call such as
	// D2d_mat_mult(p, p,q) or D2d_mat_mult(p, q,p) or D2d_mat_mult(p, p,p)

	int D2d_make_identity (double a[3][3]) ;
	// a = I

	int D2d_translate (double a[3][3], double b[3][3], double dx, double dy) ;
	// a = translation*a
	// b = b*translation_inverse

	int D2d_scale (double a[3][3], double b[3][3], double sx, double sy) ;
	// a = scale*a
	// b = b*scale_inverse

	int D2d_rotate (double a[3][3], double b[3][3], double radians) ;
	// a = rotate*a
	// b = b*rotate_inverse

	int D2d_negate_x (double a[3][3], double b[3][3]) ;
	// negate the x....reflects in the y-axis
	// a = reflect*a
	// b = b*reflect_inverse

	int D2d_negate_y (double a[3][3], double b[3][3]) ;
	// negate the y....reflects in the x-axis
	// a = reflect*a
	// b = b*reflect_inverse

	int D2d_mat_mult_points (double X, double Y,
	double m[3][3],
	double x, double y, int numpoints) ;
	// \|X0 X1 X2 ...\| \|x0 x1 x2 ...\|
	// \|Y0 Y1 Y2 ...\| = m * \|y0 y1 y2 ...\|
	// \| 1 1 1 ...\| \| 1 1 1 ...\|

	// SAFE, user may make a call like D2d_mat_mult_points (x,y, m, x,y, n) ;

	int D2d_transpose (double a[3][3], double b[3][3]);

	double D2d_dot (double a[3], double b[3]);
	// [a, b, c] [d, e, f] -> ad+bc+c*f

	#endif
	#include "Drawframework.h"
	/*
	* constructs an object from a list of points, connections, and colors
	*/
	void read_object2d_from_file(FILE* f, object2d *obj) {
	// Get the points
	fscanf(f, "%d", &obj->n);
	for (int i=0; i<obj->n; i++) {
	fscanf(f, "%lf %lf", &obj->xs[i], &obj->ys[i]);
	}


	// Get the shapes
	fscanf(f, "%d", &obj->num_shapes);
	for (int i=0; i<obj->num_shapes; i++) {
	fscanf(f, "%d", &obj->shapes[i].n);
	for (int j=0; j<obj->shapes[i].n; j++) {
	fscanf(f, "%d", &obj->shapes[i].vertices[j]);
	}
	}

	// Get the colors
	for (int i=0; i<obj->num_shapes; i++) {
	fscanf(f, "%lf %lf %lf", &obj->shapes[i].R, &obj->shapes[i].G, &obj->shapes[i].B);
	}
	}

	void read_shape_from_file(FILE* f, shape* shape) {
	fscanf(f, "%d\n", &shape->n);
	for (int i=0; i<shape->n; i++) {
	fscanf(f, "%d", &shape->vertices[i]);
	}
	}

	void draw_object2d(object2d* obj) {
	for (int i=0; i<obj->num_shapes; i++) {
	draw_shape(&obj->shapes[i], obj, true);
	}
	}

	void draw_object2d_wireframe(object2d* obj) {
	for (int i=0; i<obj->num_shapes; i++) {
	draw_shape(&obj->shapes[i], obj, false);
	}
	}

	void draw_shape(shape* s, object2d* obj, int fill) {
	double x[1000];
	double y[1000];
	int point_index;
	for (int j=0; j<s->n; j++) {
	point_index = s->vertices[j];
	x[j] = obj->xs[point_index];
	y[j] = obj->ys[point_index];
	}
	G_rgb(s->R, s->G, s->B);
	if (fill) G_fill_polygon(x, y, s->n);
	else G_polygon(x, y, s->n);
	}

	/*
	* Return the intersection of line p1-p2
	* and line j1-j2
	*/
	void intersection(
	point2d p1,
	point2d p2,
	point2d j1,
	point2d j2,
	point2d* intersect) {
	printf("line 1: {%f, %f} to {%f, %f}\n", p1.x, p1.y, p2.x, p2.y);
	// Slope of line p (mp)
	double mp = (p2.y - p1.y) / (p2.x - p1.x);
	printf("Slope of line 1 is %f\n", mp);
	// Slope of line j (mj)
	double mj = (j2.y - j1.y) / (j2.x - j1.x);
	printf("Slope of line 2 is %f\n", mj);
	//p1.y = mp (p1.x) + bp
	double bp = p1.y - mp*p1.x;
	printf("Intercept of line 1 is %f\n", bp);
	//j1.y = mj (j1.x) + bj
	double bj = j1.y - mj*j1.x;
	printf("Intercept of line 2 is %f\n", bj);
	if (!isfinite(mp)) {
	//p1-p2 is a vertical line
	intersect->x = p1.x;
	intersect->y = mj * intersect->x + bj;
	return;
	}
	if (!isfinite(mj)) {
	//j1-j2 is a vertical line
	intersect->x = j1.x;
	intersect->y = mp * intersect->x + bp;
	return;
	}
	//y = mp * x + bp
	//y = mj * x + bj
	//mjx + bj = mpx + bp
	//mjx - mpx = bp - bj
	//x(mj - mp) = (bp - bj)
	intersect->x = (bp - bj)/(mj - mp);
	printf("Intersection x is %f\n", intersect->x);
	intersect->y = mp * intersect->x + bp;
	printf("Intersection y is %f\n", intersect->y);
	}

	void clip_object2d(object2d* obj, polygon* win) {
	for (int j=0; j<win->n; j++) {
	point2d p3 = {win->xs[j], win->ys[j]};
	point2d p4 = {win->xs[(j+1)%win->n], win->ys[(j+1)%win->n]};
	clip_line(obj, p3, p4);
	}
	}

	// Clip object2d fig by a single line
	void clip_line(object2d* fig, point2d l1, point2d l2) {
	shape* s;
	for (int i=0; i<fig->num_shapes; i++) {
	clip_shape(&fig->shapes[i], fig, l1, l2);
	}
	}

	void clip_shape(shape* fig, object2d* parent, point2d l1, point2d l2) {
	shape out = {0, {}, fig->R, fig->G, fig->B};
	int i1, i2;
	for (int i=0; i<fig->n; i++) {
	//For each line in the shape...
	i1 = fig->vertices[i];
	i2 = fig->vertices[(i+1)%fig->n];
	point2d p1 = {parent->xs[i1], parent->ys[i1]};
	point2d p2 = {parent->xs[i2], parent->ys[i2]};
	if (isRight(p1, l1, l2)) {
	//If point2d p1 is inside the clipping line, add it to the output shape
	out.vertices[out.n] = i1;
	out.n++;
	}
	point2d intersect;
	intersection(p1, p2, l1, l2, &intersect);
	if (in_range(intersect.x, p1.x, p2.x) && in_range(intersect.y, p1.y, p2.y)) {

	parent->xs[parent->n] = intersect.x;
	parent->ys[parent->n] = intersect.y;
	out.vertices[out.n] = parent->n;
	parent->n++;
	out.n++;
	}
	}
	*fig = out;
	}

	// Use the cross product to tell if a point2d is on the right or colinear of the line bc
	int isRight(point2d a, point2d b, point2d c){
	return ((b.x - a.x)(c.y - a.y) - (b.y - a.y)(c.x - a.x)) <= 0;
	}

	/*
	* Return whether x is included in [a, b]
	*/
	int in_range(double x, double a, double b) {
	double range[] = {a, b};
	double lower = min(range, 2);
	double upper = max(range, 2);
	return (x <= upper && x >= lower);
	}

	/*
	* Return the smallest element of an array of doubles containing n elements.
	* n must be >0.
	*/
	double min(double* arr, int n) {
	double min = arr[0];
	for(int i=0; i<n; i++) {
	if (arr[i] < min) min = arr[i];
	}
	return min;
	}

	/*
	* Return the largest element of an array of doubles containing n elements.
	* n must be >0.
	*/
	double max(double* arr, int n) {
	double max = arr[0];
	for(int i=0; i<n; i++) {
	if (arr[i] > max) max = arr[i];
	}
	return max;
	}
	#ifndef DRAWFRAMEWORK_H
	#define DRAWFRAMEWORK_H
	#include <FPT.h>
	#define true 1
	#define false 0

	/*
	* shape definition. Needs to be wrapped in a 2dObject or 3dObject to work.
	*/
	typedef struct {
	int n; //Number of points in the shape
	int vertices[20]; //List of points to connect in the parent 2dObject to make the shape
	double R;
	double G;
	double B;
	} shape;

	/*
	* polygon definition. Standalone way to represent a single 2d polygon
	*/
	typedef struct {
	int n; //Number of points in the shape
	double xs[10000];
	double ys[10000];
	double R;
	double G;
	double B;
	} polygon;

	/*
	* 2d object definition. Maxes out at 1000 points/100 shapes.
	*/
	typedef struct {
	int num_shapes;
	int n; //Number of points in the object
	double xs[10000];
	double ys[10000];
	shape shapes[10000];
	} object2d;

	/*
	* 2d point definition. Useful for comparisons and return values.
	*/
	typedef struct {
	double x;
	double y;
	} point2d;

	void read_object2d_from_file(FILE* f, object2d *obj);
	void read_shape_from_file(FILE* f, shape* shape);
	void draw_object2d(object2d* obj);
	void draw_object2d_wireframe(object2d* obj);
	void clip_object2d(object2d* obj, polygon* win);
	void clip_line(object2d* fig, point2d l1, point2d l2);
	void clip_shape(shape* fig, object2d* parent, point2d l1, point2d l2);
	int isRight(point2d a, point2d b, point2d c);
	void draw_shape(shape* s, object2d* obj, int fill);
	int in_range(double x, double a, double b);
	double min(double* arr, int n);
	double max(double* arr, int n);

	#endif