Intersection work in progress
Review URL: https://codereview.appspot.com/5576043
git-svn-id: http://skia.googlecode.com/svn/trunk@3087 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicParameterizationCode.cpp b/experimental/Intersection/CubicParameterizationCode.cpp
index 9e7a3f6..d799b15 100644
--- a/experimental/Intersection/CubicParameterizationCode.cpp
+++ b/experimental/Intersection/CubicParameterizationCode.cpp
@@ -4,7 +4,7 @@
* Resultant[a*t^3 + b*t^2 + c*t + d - x, e*t^3 + f*t^2 + g*t + h - y, t]
*/
-const char result[] =
+const char result1[] =
"-d^3 e^3 + c d^2 e^2 f - b d^2 e f^2 + a d^2 f^3 - c^2 d e^2 g + "
" 2 b d^2 e^2 g + b c d e f g - 3 a d^2 e f g - a c d f^2 g - "
" b^2 d e g^2 + 2 a c d e g^2 + a b d f g^2 - a^2 d g^3 + c^3 e^2 h - "
@@ -31,7 +31,48 @@
" 3 a^2 d e y^2 + a b^2 f y^2 - 2 a^2 c f y^2 - a^2 b g y^2 + "
" 3 a^3 h y^2 + 3 a^2 e x y^2 - a^3 y^3";
-const size_t len = sizeof(result) - 1;
+const size_t len1 = sizeof(result1) - 1;
+
+/* Given:
+ * Expand[
+ * Det[{{a, b, c, (d - x), 0, 0},
+ * {0, a, b, c, (d - x), 0},
+ * {0, 0, a, b, c, (d - x)},
+ * {e, f, g, (h - y), 0, 0},
+ * {0, e, f, g, (h - y), 0},
+ * {0, 0, e, f, g, (h - y)}}]]
+ */
+ // result1 and result2 are the same. 102 factors:
+const char result2[] =
+"-d^3 e^3 + c d^2 e^2 f - b d^2 e f^2 + a d^2 f^3 - c^2 d e^2 g + "
+" 2 b d^2 e^2 g + b c d e f g - 3 a d^2 e f g - a c d f^2 g - "
+" b^2 d e g^2 + 2 a c d e g^2 + a b d f g^2 - a^2 d g^3 + c^3 e^2 h - "
+" 3 b c d e^2 h + 3 a d^2 e^2 h - b c^2 e f h + 2 b^2 d e f h + "
+" a c d e f h + a c^2 f^2 h - 2 a b d f^2 h + b^2 c e g h - "
+" 2 a c^2 e g h - a b d e g h - a b c f g h + 3 a^2 d f g h + "
+" a^2 c g^2 h - b^3 e h^2 + 3 a b c e h^2 - 3 a^2 d e h^2 + "
+" a b^2 f h^2 - 2 a^2 c f h^2 - a^2 b g h^2 + a^3 h^3 + 3 d^2 e^3 x - "
+" 2 c d e^2 f x + 2 b d e f^2 x - 2 a d f^3 x + c^2 e^2 g x - "
+" 4 b d e^2 g x - b c e f g x + 6 a d e f g x + a c f^2 g x + "
+" b^2 e g^2 x - 2 a c e g^2 x - a b f g^2 x + a^2 g^3 x + "
+" 3 b c e^2 h x - 6 a d e^2 h x - 2 b^2 e f h x - a c e f h x + "
+" 2 a b f^2 h x + a b e g h x - 3 a^2 f g h x + 3 a^2 e h^2 x - "
+" 3 d e^3 x^2 + c e^2 f x^2 - b e f^2 x^2 + a f^3 x^2 + "
+" 2 b e^2 g x^2 - 3 a e f g x^2 + 3 a e^2 h x^2 + e^3 x^3 - "
+" c^3 e^2 y + 3 b c d e^2 y - 3 a d^2 e^2 y + b c^2 e f y - "
+" 2 b^2 d e f y - a c d e f y - a c^2 f^2 y + 2 a b d f^2 y - "
+" b^2 c e g y + 2 a c^2 e g y + a b d e g y + a b c f g y - "
+" 3 a^2 d f g y - a^2 c g^2 y + 2 b^3 e h y - 6 a b c e h y + "
+" 6 a^2 d e h y - 2 a b^2 f h y + 4 a^2 c f h y + 2 a^2 b g h y - "
+" 3 a^3 h^2 y - 3 b c e^2 x y + 6 a d e^2 x y + 2 b^2 e f x y + "
+" a c e f x y - 2 a b f^2 x y - a b e g x y + 3 a^2 f g x y - "
+" 6 a^2 e h x y - 3 a e^2 x^2 y - b^3 e y^2 + 3 a b c e y^2 - "
+" 3 a^2 d e y^2 + a b^2 f y^2 - 2 a^2 c f y^2 - a^2 b g y^2 + "
+" 3 a^3 h y^2 + 3 a^2 e x y^2 - a^3 y^3";
+
+
+const size_t len2 = sizeof(result2) - 1;
+
const int factors = 8;
struct coeff {
@@ -56,91 +97,93 @@
typedef std::vector<coeff> coeffs;
typedef std::vector<coeffs> n_coeffs;
-static char skipSpace(size_t& index) {
+static char skipSpace(const char* str, size_t& index) {
do {
++index;
- } while (result[index] == ' ');
- return result[index];
+ } while (str[index] == ' ');
+ return str[index];
}
-static char backSkipSpace(size_t& end) {
- while (result[end - 1] == ' ') {
+static char backSkipSpace(const char* str, size_t& end) {
+ while (str[end - 1] == ' ') {
--end;
}
- return result[end - 1];
+ return str[end - 1];
}
-static void match(coeffs& co, const char pattern[]) {
+static void match(const char* str, size_t len, coeffs& co, const char pattern[]) {
size_t patternLen = strlen(pattern);
size_t index = 0;
while (index < len) {
- char ch = result[index];
+ char ch = str[index];
if (ch != '-' && ch != '+') {
printf("missing sign\n");
}
size_t end = index + 1;
- while (result[end] != '+' && result[end] != '-' && ++end < len) {
+ while (str[end] != '+' && str[end] != '-' && ++end < len) {
;
}
- backSkipSpace(end);
+ backSkipSpace(str, end);
size_t idx = index;
index = end;
- skipSpace(index);
- if (!strncmp(&result[end - patternLen], pattern, patternLen) == 0) {
+ skipSpace(str, index);
+ if (!strncmp(&str[end - patternLen], pattern, patternLen) == 0) {
continue;
}
size_t endCoeff = end - patternLen;
- char last = backSkipSpace(endCoeff);
+ char last = backSkipSpace(str, endCoeff);
if (last == '2' || last == '3') {
- last = result[endCoeff - 3]; // skip ^2
+ last = str[endCoeff - 3]; // skip ^2
}
if (last == 'x' || last == 'y') {
continue;
}
coeff c;
- c.s = result[idx] == '-' ? -1 : 1;
+ c.s = str[idx] == '-' ? -1 : 1;
bzero(c.n, sizeof(c.n));
- ch = skipSpace(idx);
+ ch = skipSpace(str, idx);
if (ch >= '2' && ch <= '6') {
c.s *= ch - '0';
- ch = skipSpace(idx);
+ ch = skipSpace(str, idx);
}
while (idx < endCoeff) {
- char x = result[idx];
+ char x = str[idx];
if (x < 'a' || x > 'a' + factors) {
printf("expected factor\n");
}
idx++;
int pow = 1;
- if (result[idx] == '^') {
+ if (str[idx] == '^') {
idx++;
- char exp = result[idx];
+ char exp = str[idx];
if (exp < '2' || exp > '3') {
printf("expected exponent\n");
}
pow = exp - '0';
}
- skipSpace(idx);
+ skipSpace(str, idx);
c.n[x - 'a'] = pow;
}
co.push_back(c);
}
}
-void cubecode_test();
+void cubecode_test(int test);
-void cubecode_test() {
+void cubecode_test(int test) {
+ const char* str = test ? result2 : result1;
+ size_t len = strlen(str);
n_coeffs c(coeff_count);
- match(c[xxx_coeff], "x^3"); // 1 factor
- match(c[xxy_coeff], "x^2 y"); // 1 factor
- match(c[xyy_coeff], "x y^2"); // 1 factor
- match(c[yyy_coeff], "y^3"); // 1 factor
- match(c[xx_coeff], "x^2"); // 7 factors
- match(c[xy_coeff], "x y"); // 8 factors
- match(c[yy_coeff], "y^2"); // 7 factors
- match(c[x_coeff], "x"); // 21 factors
- match(c[y_coeff], "y"); // 21 factors
- match(c[c_coeff], ""); // 34 factors
+ match(str, len, c[xxx_coeff], "x^3"); // 1 factor
+ match(str, len, c[xxy_coeff], "x^2 y"); // 1 factor
+ match(str, len, c[xyy_coeff], "x y^2"); // 1 factor
+ match(str, len, c[yyy_coeff], "y^3"); // 1 factor
+ match(str, len, c[xx_coeff], "x^2"); // 7 factors
+ match(str, len, c[xy_coeff], "x y"); // 8 factors
+ match(str, len, c[yy_coeff], "y^2"); // 7 factors
+ match(str, len, c[x_coeff], "x"); // 21 factors
+ match(str, len, c[y_coeff], "y"); // 21 factors
+ match(str, len, c[c_coeff], ""); // 34 factors : total 102
#define COMPUTE_MOST_FREQUENT_EXPRESSION_TRIPLETS 0
#define WRITE_AS_NONOPTIMIZED_C_CODE 0
#if COMPUTE_MOST_FREQUENT_EXPRESSION_TRIPLETS