diff options
-rw-r--r-- | include/common/geom.h | 54 | ||||
-rw-r--r-- | include/common/matrix.h | 51 | ||||
-rw-r--r-- | include/morpher/matrix.h | 41 | ||||
-rw-r--r-- | src/common/geom.c | 19 | ||||
-rw-r--r-- | src/common/matrix.c | 63 | ||||
-rw-r--r-- | src/morpher/matrix.c | 16 | ||||
-rw-r--r-- | test/common/matrix.c | 21 | ||||
-rw-r--r-- | test/morpher/matrix.c | 19 |
8 files changed, 149 insertions, 135 deletions
diff --git a/include/common/geom.h b/include/common/geom.h index a843c76..b3564a5 100644 --- a/include/common/geom.h +++ b/include/common/geom.h | |||
@@ -38,6 +38,46 @@ typedef struct { | |||
38 | CartesianVector origin, target; | 38 | CartesianVector origin, target; |
39 | } CartesianMapping; | 39 | } CartesianMapping; |
40 | 40 | ||
41 | |||
42 | /** | ||
43 | * Function: m | ||
44 | * Shorthand for an identity mapping. | ||
45 | * | ||
46 | * Parameters: | ||
47 | * x - the x-coordinate | ||
48 | * y - the y-coordinate | ||
49 | * | ||
50 | * Returns: | ||
51 | * A cartesian identity mapping | ||
52 | */ | ||
53 | CartesianMapping m(int x, int y); | ||
54 | |||
55 | /** | ||
56 | * Function: v | ||
57 | * Shorthand for a vector. | ||
58 | * | ||
59 | * Parameters: | ||
60 | * x - the x-coordinate | ||
61 | * y - the y-coordinate | ||
62 | * | ||
63 | * Returns: | ||
64 | * An integer vector | ||
65 | */ | ||
66 | CartesianVector v(int x, int y); | ||
67 | |||
68 | /** | ||
69 | * Function: mappings_equals | ||
70 | * Compares two cartesian mappings. | ||
71 | * | ||
72 | * Parameters: | ||
73 | * m1 - the first mapping | ||
74 | * m2 - the second mapping | ||
75 | * | ||
76 | * Returns: | ||
77 | * T(m1 is equal to m2) | ||
78 | */ | ||
79 | bool mappings_equals(CartesianMapping m1, CartesianMapping m2); | ||
80 | |||
41 | /** | 81 | /** |
42 | * Function: vector_equals | 82 | * Function: vector_equals |
43 | * Compares two cartesian vectors. | 83 | * Compares two cartesian vectors. |
@@ -51,4 +91,18 @@ typedef struct { | |||
51 | */ | 91 | */ |
52 | bool vector_equals(CartesianVector v1, CartesianVector v2); | 92 | bool vector_equals(CartesianVector v1, CartesianVector v2); |
53 | 93 | ||
94 | /** | ||
95 | * Function: triangle_area | ||
96 | * Computes the area of a triangle. | ||
97 | * | ||
98 | * Parameters: | ||
99 | * v1 - first vertex | ||
100 | * v2 - second vertex | ||
101 | * v3 - third vertex | ||
102 | * | ||
103 | * Returns: | ||
104 | * The area of the triangle spawned by the three supplied vertices | ||
105 | */ | ||
106 | IntVector triangle_area(CartesianVector v1, CartesianVector v2, CartesianVector v3); | ||
107 | |||
54 | #endif | 108 | #endif |
diff --git a/include/common/matrix.h b/include/common/matrix.h deleted file mode 100644 index fe4a12a..0000000 --- a/include/common/matrix.h +++ /dev/null | |||
@@ -1,51 +0,0 @@ | |||
1 | #ifndef UPEM_MORPHING_MATRIX | ||
2 | #define UPEM_MORPHING_MATRIX | ||
3 | |||
4 | /** | ||
5 | * File: matrix.h | ||
6 | * Matrices representation and useful operations. | ||
7 | * | ||
8 | * See also: | ||
9 | * The film | ||
10 | */ | ||
11 | |||
12 | #include "geom.h" | ||
13 | |||
14 | /** | ||
15 | * Struct: IntSquareMatrix | ||
16 | * Represents a square integer matrix. | ||
17 | * | ||
18 | * Fields: | ||
19 | * **elements - NULL-terminated array of element pointers | ||
20 | * dim - dimension | ||
21 | */ | ||
22 | typedef struct { | ||
23 | IntVector **elements; | ||
24 | IntVector dim; | ||
25 | } IntSquareMatrix; | ||
26 | |||
27 | /** | ||
28 | * Function: matrix_int_det | ||
29 | * Computes and returns the determinant of a square integer matrix. | ||
30 | * | ||
31 | * Parameters: | ||
32 | * *matrix - pointer to input matrix | ||
33 | * | ||
34 | * Returns: | ||
35 | * The integer determinant | ||
36 | */ | ||
37 | IntVector matrix_int_det(IntSquareMatrix *matrix); | ||
38 | |||
39 | /** | ||
40 | * Function: matrix_reshape | ||
41 | * Reshapes a flat vector into a bi-dimensional row pointer array. | ||
42 | * | ||
43 | * Parameters: | ||
44 | * **bi_dim - pointer to the result row array | ||
45 | * *flat - flat vector | ||
46 | * width - number of elements per row | ||
47 | * height - number of rows | ||
48 | */ | ||
49 | void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height); | ||
50 | |||
51 | #endif | ||
diff --git a/include/morpher/matrix.h b/include/morpher/matrix.h new file mode 100644 index 0000000..8118727 --- /dev/null +++ b/include/morpher/matrix.h | |||
@@ -0,0 +1,41 @@ | |||
1 | #ifndef UPEM_MORPHING_MATRIX | ||
2 | #define UPEM_MORPHING_MATRIX | ||
3 | |||
4 | /** | ||
5 | * File: matrix.h | ||
6 | * Determinant operations. | ||
7 | * | ||
8 | * See also: | ||
9 | * The film | ||
10 | */ | ||
11 | |||
12 | #include "common/geom.h" | ||
13 | |||
14 | /** | ||
15 | * Function: matrix_int_det2 | ||
16 | * Computes and returns the determinant of a square integer matrix of size 2. | ||
17 | * | ||
18 | * Parameters: | ||
19 | * uij - element at the i-th row and j-th column, counting from 1 | ||
20 | * | ||
21 | * Returns: | ||
22 | * The integer determinant | ||
23 | */ | ||
24 | IntVector matrix_int_det2(IntVector u11, IntVector u12, | ||
25 | IntVector u21, IntVector u22); | ||
26 | |||
27 | /** | ||
28 | * Function: matrix_int_det3 | ||
29 | * Computes and returns the determinant of a square integer matrix of size 3. | ||
30 | * | ||
31 | * Parameters: | ||
32 | * uij - element at the i-th row and j-th column, counting from 1 | ||
33 | * | ||
34 | * Returns: | ||
35 | * The integer determinant | ||
36 | */ | ||
37 | IntVector matrix_int_det3(IntVector u11, IntVector u12, IntVector u13, | ||
38 | IntVector u21, IntVector u22, IntVector u23, | ||
39 | IntVector u31, IntVector u32, IntVector u33); | ||
40 | |||
41 | #endif | ||
diff --git a/src/common/geom.c b/src/common/geom.c index 7abb422..219270f 100644 --- a/src/common/geom.c +++ b/src/common/geom.c | |||
@@ -1,5 +1,24 @@ | |||
1 | #include "common/geom.h" | 1 | #include "common/geom.h" |
2 | #include "morpher/matrix.h" | ||
3 | |||
4 | CartesianMapping m(int x, int y) { | ||
5 | return (CartesianMapping) {{x, y}, | ||
6 | {x, y}}; | ||
7 | } | ||
8 | |||
9 | CartesianVector v(int x, int y) { | ||
10 | return (CartesianVector) {x, y}; | ||
11 | } | ||
12 | |||
13 | bool mappings_equals(CartesianMapping m1, CartesianMapping m2) { | ||
14 | return vector_equals(m1.origin, m2.origin) && vector_equals(m1.target, m2.target); | ||
15 | } | ||
2 | 16 | ||
3 | bool vector_equals(CartesianVector v1, CartesianVector v2) { | 17 | bool vector_equals(CartesianVector v1, CartesianVector v2) { |
4 | return v1.x == v2.x && v1.y == v2.y; | 18 | return v1.x == v2.x && v1.y == v2.y; |
5 | } | 19 | } |
20 | |||
21 | IntVector triangle_area(CartesianVector v1, CartesianVector v2, CartesianVector v3) { | ||
22 | return matrix_int_det2(v1.x - v3.x, v2.x - v3.x, | ||
23 | v1.y - v3.y, v2.y - v3.y); | ||
24 | } | ||
diff --git a/src/common/matrix.c b/src/common/matrix.c deleted file mode 100644 index 60f9afb..0000000 --- a/src/common/matrix.c +++ /dev/null | |||
@@ -1,63 +0,0 @@ | |||
1 | #include "common/matrix.h" | ||
2 | #include <assert.h> | ||
3 | #include <memory.h> | ||
4 | #include <stdlib.h> | ||
5 | #include "common/mem.h" | ||
6 | |||
7 | static inline IntSquareMatrix *matrix_without_row(IntSquareMatrix *target, IntSquareMatrix *origin, | ||
8 | IntVector omitted_row) { | ||
9 | int origin_row, target_row; | ||
10 | |||
11 | for (origin_row = 0, target_row = 0; origin_row < origin->dim; ++origin_row) | ||
12 | if (origin_row != omitted_row) | ||
13 | target->elements[target_row++] = origin->elements[origin_row]; | ||
14 | |||
15 | return target; | ||
16 | } | ||
17 | |||
18 | static inline IntVector det_dev_sign(IntVector row, IntVector col) { | ||
19 | assert(row > 0 && col > 0); | ||
20 | return ((row + col) % 2 == 0) ? 1 : -1; | ||
21 | } | ||
22 | |||
23 | static inline IntVector det_reduce(IntSquareMatrix *matrix) { | ||
24 | IntSquareMatrix sub_matrix; | ||
25 | int row; | ||
26 | IntVector det = 0; | ||
27 | |||
28 | assert(matrix->dim > 2); | ||
29 | |||
30 | sub_matrix.dim = matrix->dim - 1; | ||
31 | sub_matrix.elements = malloc_or_die(sub_matrix.dim * sizeof(IntVector *)); | ||
32 | |||
33 | for (row = 0; row < matrix->dim; ++row) | ||
34 | det += matrix->elements[row][matrix->dim - 1] | ||
35 | * det_dev_sign(row + 1, matrix->dim) | ||
36 | * matrix_int_det(matrix_without_row(&sub_matrix, matrix, row)); | ||
37 | |||
38 | |||
39 | free(sub_matrix.elements); | ||
40 | return det; | ||
41 | } | ||
42 | |||
43 | IntVector matrix_int_det(IntSquareMatrix *matrix) { | ||
44 | assert(matrix->dim > 0); | ||
45 | switch (matrix->dim) { | ||
46 | case 1: | ||
47 | return matrix->elements[0][0]; | ||
48 | |||
49 | case 2: | ||
50 | return matrix->elements[0][0] * matrix->elements[1][1] - matrix->elements[0][1] * matrix->elements[1][0]; | ||
51 | |||
52 | default: | ||
53 | return det_reduce(matrix); | ||
54 | } | ||
55 | } | ||
56 | |||
57 | void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height) { |