ROB 599: Programming for Robotics: Homework 1

Problem 1: collision

In this problem you will write a program to detect collision between polygons.

Your program will read in a file polygons.csv that will look something like this:

x y rot n_points x0 x1 x2 x3 y0 y1 y2 y3
0 0 0   4        0  0  1  1  0  1  1  0
1 0 0   4        0  0  1  1  0  1  1  0

Notice that a “comma separated values” or “csv” often doesn’t have any commas at all! Really it would more generally be called a “delimiter separated values” file. Here we are using arbitrary amounts of white space to separate the values.

The first line is a key that your program can ignore, and then each of the next two lines describes a polygon. The first three columns give both the polygon’s global location and also the rotation in degrees. Remember that in applying this transformation, rotation happens first and then translation. Besides, n_points, each of these values may be a floating point number.

If any of the numbers in the file are invalid, your program must print an error message to stderr and exit/return with a status code of 1.

Following this you read in the number of points used by the polygon. For simplicity we will assume the number of points cannot exceed 16, and your program should output an error if there are greater than 16 points. The points of the polygon, with (0, 0) representing the polygon’s point of rotation, are then listed. The points are given in a certain order, called a winding order. In the example above, the points are given in clockwise order around the square. This winding order will be important for some of the algorithms we use. Counter-clockwise winding order also works.

Your program will either output collision! or no collision

Polygon collision algorithm

We will implement a simple algorithm based on the cross product:

Apply global translations and rotations to all points
for each line l1 in polygon 1 {
    for each line l2 in polygon 2 {
        // do l1 and l2 intersect?
        for each line l in [l1, l2] {
            for each point p in the other line {
                compute the cross product between l and p
            }
            If the two cross products have opposite sign, or one of them is zero
                then they were on opposite sides of/touching the line l that extends to infinity
        }
        If both cross product checks above indicated opposite signs,
            then the actual lines (not extending to infinity) intersect,
            EXCEPT when both checks (for lines l1 and l2) have at least one zero cross product
    }
}

Neither a point nor a line are actually vectors, so both need to be converted to vectors in order to calculate the cross product. Draw it out on paper! That is what I had to do for it to make sense.

However, this algorithm has a failure mode when one polygon completely contains the other. So we need to check if either polygon contains the other. This is easy because we only have to check one point of that polygon, because this case is where either every single point is contained, or none of them are.

for each polygon pg in [polygon 1, polygon 2] {
    // compute if pg contains a point p of the other polygon
    for each line l in pg {
        compute the cross product between l and p
    }
    // the sign of each cross product indicates the side the point lies on.
    // the lines in the polygon must have a consistent winding order (clockwise or counter)
    // for the signs to consistently indicate inside or outside of the polygon.
    if all the cross products have the same sign, then the polygon contains point p
}

Most of the automatic tests use a clockwise winding order.

Even if the polygons only intersect at a point, we still consider this a collision.

Structures

You may find it useful in your program to use a structure to represent the polygons. The general syntax for a structure is:

struct object {
    int int_value;
    double double_array[16];
    // repeat for as many different elements as you like
};

void test(void) {
    struct object my_object = {0}; // notation for setting value to all zeros
    my_object.int_value = 10;
}

However, it is generally more convenient to use a type definition to avoid having to type struct object as the type every single time. Then the same code could look like:

typedef struct object {
    int int_value;
    double double_array[16];
} object_t;

void test(void) {
    object_t my_object = {0}; // notation for setting value to all zeros
    my_object.int_value = 10;
}

It is a convention that new types like this end in a _t to signify that they are types and not variables.

Reading from files

When you open a file, you get a FILE * value that holds a position in that file. Every different read function will move you forwards through the file, so characters/words/lines will not repeat. Whenever you are reading from a file, you should always be careful to check if your input is valid/expected, and report an error if it is not.

If you want to read a file character by character, use the fgetc function.

If you want to read an entire line of a file, you may find it helpful to use the fgets function.

If you want to read different kinds of values separated by white space (spaces, new lines, tabs, etc…), use fscanf. Just like the printf function, fscanf uses a format string to describe the number and types of inputs to read from a file. Generally for integers you use %d (meaning decimal) and for doubles you use %lf (meaning long floating point number). Calling fscanf returns the number of numbers successfully read from the file. You should check that this number is the same as the number you asked for so that you can properly handle invalid input. Notice that since you want fscanf to put a value into certain variables, the variable needs to be prefixed with an &. We will get more into what the means later.

For a file my_file.txt with the following:

10, 1.0, 2.0
10,
1.0,
2.0
FILE *f = fopen("my_file.txt", "r");
if (!f) {
    // for certain system functions, perror  (print error) will print an explanation.
    // When the file is missing, this prints to stderr:
    // "Could not open my_file.txt: No such file or directory"
    perror("Could not open my_file.txt");
    exit(1);
}

printf("character 0: %c\n", fgetc(f)); // 1
printf("character 1: %c\n", fgetc(f)); // 0
printf("character 2: %c\n", fgetc(f)); // ,

// we can also check for the EOF (end of file) value from fgetc
for (int i = 3; i < 6; i++) {
    int c = fgetc(f);
    if (c == EOF) {
        fprintf(stderr, "unexpected EOF while reading file\n");
        exit(1);
    }

    printf("character %d: %c\n", i, c); // ' ', 1, .
}

char rest_of_line[128];

// use sizeof to not have to repeat 128
if (!fgets(rest_of_line, sizeof(rest_of_line), f)) {
    fprintf(stderr, "failed to read rest of first line\n");
    exit(1);
}
printf("Remainder of that line was: %s\n", rest_of_line); // "0, 2.0"

// fscanf does not care that the rest of the values are on different lines
object_t obj = {0};
int args_read = fscanf(f, "%d, %lf, %lf", &obj.int_value,
                       &obj.double_array[0], &obj.double_array[1]);
if (args_read != 3) {
    fprintf(stderr, "could not read all three values!\n");
    exit(1);
}

The format with fscanf does have to match exactly:

10 1.0 2.0
int args_read = fscanf(f, "%d, %lf, %lf", &obj.int_value,
                       &obj.double_array[0], &obj.double_array[1]);
// args_read will be 1 because it can't find the comma requested in the fscanf format string

Problem 2: cryptogram

In this problem you will write a program to “encrypt” and “decrypt” strings of text using a “password”. In general, cryptograms are simple ciphers that can often be broken by hand with enough example text, so don’t use this for any real security!

The cryptogram will be based on letter rotation, with the password indicating how far each letter of the plain text should be rotated. The letter ‘a’ rotates by 0, ‘b’ by 1, ‘c’ by 2, and so forth. For example, ‘z’ rotated by ‘b’ (1) would become ‘a’ again, since in rotation, ‘z’ is followed by ‘a’ again.

For example, if the password is “abc” and the plain text is “aaaaaa”, then the encrypted text is “abcabc”, with each letter of the password effecting one letter of plain text. The password is just repeated as long as necessary to encrypt all the text.

Only letters should be encrypted, and they should maintain their case. So password “abc” would encrypt ‘Hello World!’ as ‘Hfnlp Yosnd!’.

Passwords are not case-sensitive, and characters in the password that are not letters are ignored/skipped. A blank password leaves the plain text unchanged.

./cryptogram
usage: ./cryptogram <encrypt|decrypt> <password> <text>
./cryptogram encrypt abc 'Hello World!'
Hfnlp Yosnd!
./cryptogram encrypt ABC 'Hello World!'
Hfnlp Yosnd!
./cryptogram encrypt 'A!~b~!C' 'Hello World!'
Hfnlp Yosnd!
./cryptogram decrypt abc 'Hfnlp Yosnd!'
Hello World!
./cryptogram encrypt '' 'Hello World!'
Hello World!
./cryptogram enscrypt abc hello
expected command encrypt or decrypt. got 'enscrypt'