shape ops work in progress

git-svn-id: http://skia.googlecode.com/svn/trunk@7836 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/hg.htm b/experimental/Intersection/hg.htm
new file mode 100644
index 0000000..32f49a7
--- /dev/null
+++ b/experimental/Intersection/hg.htm
@@ -0,0 +1,649 @@
+<html>
+<head>
+<div style="height:0">
+
+<div id="cubic1">
+{{3.13,2.74}, {1.08,4.62}, {3.71,0.94}, {2.01,3.81}} 
+{{6.71,3.14}, {7.99,2.75}, {8.27,1.96}, {6.35,3.57}} 
+{{9.45,10.67}, {10.05,5.78}, {13.95,7.46}, {14.72,5.29}} 
+{{3.34,8.98}, {1.95,10.27}, {3.76,7.65}, {4.96,10.64}} 
+</div>
+
+</div>
+
+<script type="text/javascript">
+
+var testDivs = [
+    cubic1,
+];
+
+var scale, columns, rows, xStart, yStart;
+
+var ticks = 10;
+var at_x = 13 + 0.5;
+var at_y = 23 + 0.5;
+var decimal_places = 3;
+var tests = [];
+var testTitles = [];
+var testIndex = 0;
+var ctx;
+var minScale = 1;
+var subscale = 1;
+var curveT = -1;
+var xmin, xmax, ymin, ymax;
+
+var mouseX, mouseY;
+var mouseDown = false;
+
+var draw_deriviatives = false;
+var draw_endpoints = true;
+var draw_hodo = false;
+var draw_hodo2 = false;
+var draw_hodo_origin = true;
+var draw_midpoint = false;
+var draw_tangents = true;
+var draw_sequence = true;
+
+function parse(test, title) {
+    var curveStrs = test.split("{{");
+    if (curveStrs.length == 1)
+        curveStrs = test.split("=(");
+    var pattern = /[a-z$=]?-?\d+\.*\d*e?-?\d*/g;
+    var curves = [];
+    for (var c in curveStrs) {
+        var curveStr = curveStrs[c];
+        var points = curveStr.match(pattern);
+        var pts = [];
+        for (var wd in points) {
+            var num = parseFloat(points[wd]);
+            if (isNaN(num)) continue;
+            pts.push(num);
+        }
+        if (pts.length > 2)
+            curves.push(pts);
+    }
+    if (curves.length >= 1) {
+        tests.push(curves);
+        testTitles.push(title);
+    }
+}
+
+function init(test) {
+    var canvas = document.getElementById('canvas');
+    if (!canvas.getContext) return;
+    canvas.width = window.innerWidth - 20;
+    canvas.height = window.innerHeight - 20;
+    ctx = canvas.getContext('2d');
+    xmin = Infinity;
+    xmax = -Infinity;
+    ymin = Infinity;
+    ymax = -Infinity;
+    for (var curves in test) {
+        var curve = test[curves];
+        var last = curve.length;
+        for (var idx = 0; idx < last; idx += 2) {
+            xmin = Math.min(xmin, curve[idx]);
+            xmax = Math.max(xmax, curve[idx]);
+            ymin = Math.min(ymin, curve[idx + 1]);
+            ymax = Math.max(ymax, curve[idx + 1]);
+        }
+    }
+    xmin -= 1;
+    var testW = xmax - xmin;
+    var testH = ymax - ymin;
+    subscale = 1;
+    while (testW * subscale < 0.1 && testH * subscale < 0.1) {
+        subscale *= 10;
+    }
+    while (testW * subscale > 10 && testH * subscale > 10) {
+        subscale /= 10;
+    }
+    calcFromScale();
+}
+
+function hodograph(cubic) {
+    var hodo = [];
+    hodo[0] = 3 * (cubic[2] - cubic[0]);
+    hodo[1] = 3 * (cubic[3] - cubic[1]);
+    hodo[2] = 3 * (cubic[4] - cubic[2]);
+    hodo[3] = 3 * (cubic[5] - cubic[3]);
+    hodo[4] = 3 * (cubic[6] - cubic[4]);
+    hodo[5] = 3 * (cubic[7] - cubic[5]);
+    return hodo;
+}
+
+function hodograph2(cubic) {
+    var quad = hodograph(cubic);
+    var hodo = [];
+    hodo[0] = 2 * (quad[2] - quad[0]);
+    hodo[1] = 2 * (quad[3] - quad[1]);
+    hodo[2] = 2 * (quad[4] - quad[2]);
+    hodo[3] = 2 * (quad[5] - quad[3]);
+    return hodo;
+}
+
+function quadraticRootsReal(A, B, C, s) {
+    if (A == 0) {
+        if (B == 0) {
+            s[0] = 0;
+            return C == 0;
+        }
+        s[0] = -C / B;
+        return 1;
+    }
+    /* normal form: x^2 + px + q = 0 */
+    var p = B / (2 * A);
+    var q = C / A;
+    var p2 = p * p;
+    if (p2 < q) {
+        return 0;
+    }
+    var sqrt_D = 0;
+    if (p2 > q) {
+        sqrt_D = sqrt(p2 - q);
+    }
+    s[0] = sqrt_D - p;
+    s[1] = -sqrt_D - p;
+    return 1 + s[0] != s[1];
+}
+
+function add_valid_ts(s, realRoots, t) {
+    var foundRoots = 0;
+    for (var index = 0; index < realRoots; ++index) {
+        var tValue = s[index];
+        if (tValue >= 0 && tValue <= 1) {
+            for (var idx2 = 0; idx2 < foundRoots; ++idx2) {
+                if (t[idx2] != tValue) {
+                    t[foundRoots++] = tValue;
+                }
+            }
+        }
+    }
+    return foundRoots;
+}
+
+function quadraticRootsValidT(a, b, c, t) {
+    var s = [];
+    var realRoots = quadraticRootsReal(A, B, C, s);
+    var foundRoots = add_valid_ts(s, realRoots, t);
+    return foundRoots != 0;
+}
+
+function find_cubic_inflections(cubic, tValues)
+{
+    var Ax = src[2] - src[0];
+    var Ay = src[3] - src[1];
+    var Bx = src[4] - 2 * src[2] + src[0];
+    var By = src[5] - 2 * src[3] + src[1];
+    var Cx = src[6] + 3 * (src[2] - src[4]) - src[0];
+    var Cy = src[7] + 3 * (src[3] - src[5]) - src[1];
+    return quadraticRootsValidT(Bx * Cy - By * Cx, (Ax * Cy - Ay * Cx),
+            Ax * By - Ay * Bx, tValues);
+}
+
+function dx_at_t(cubic, t) {
+    var one_t = 1 - t;
+    var a = cubic[0];
+    var b = cubic[2];
+    var c = cubic[4];
+    var d = cubic[6];
+    return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t);
+}
+
+function dy_at_t(cubic, t) {
+    var one_t = 1 - t;
+    var a = cubic[1];
+    var b = cubic[3];
+    var c = cubic[5];
+    var d = cubic[7];
+    return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t);
+}
+
+function x_at_t(cubic, t) {
+    var one_t = 1 - t;
+    var one_t2 = one_t * one_t;
+    var a = one_t2 * one_t;
+    var b = 3 * one_t2 * t;
+    var t2 = t * t;
+    var c = 3 * one_t * t2;
+    var d = t2 * t;
+    return a * cubic[0] + b * cubic[2] + c * cubic[4] + d * cubic[6];
+}
+
+function y_at_t(cubic, t) {
+    var one_t = 1 - t;
+    var one_t2 = one_t * one_t;
+    var a = one_t2 * one_t;
+    var b = 3 * one_t2 * t;
+    var t2 = t * t;
+    var c = 3 * one_t * t2;
+    var d = t2 * t;
+    return a * cubic[1] + b * cubic[3] + c * cubic[5] + d * cubic[7];
+}
+
+function calcFromScale() {
+    xStart = Math.floor(xmin * subscale) / subscale;
+    yStart = Math.floor(ymin * subscale) / subscale;
+    var xEnd = Math.ceil(xmin * subscale) / subscale;
+    var yEnd = Math.ceil(ymin * subscale) / subscale;
+    var cCelsW = Math.floor(ctx.canvas.width / 10);
+    var cCelsH = Math.floor(ctx.canvas.height / 10);
+    var testW = xEnd - xStart;
+    var testH = yEnd - yStart; 
+    var scaleWH = 1;
+    while (cCelsW > testW * scaleWH * 10 && cCelsH > testH * scaleWH * 10) {
+        scaleWH *= 10;
+    }
+    while (cCelsW * 10 < testW * scaleWH && cCelsH * 10 < testH * scaleWH) {
+        scaleWH /= 10;
+    }
+    
+    columns = Math.ceil(xmax * subscale) - Math.floor(xmin * subscale) + 1;
+    rows = Math.ceil(ymax * subscale) - Math.floor(ymin * subscale) + 1;
+    
+    var hscale = ctx.canvas.width / columns / ticks;
+    var vscale = ctx.canvas.height / rows / ticks;
+    minScale = Math.floor(Math.min(hscale, vscale));
+    scale = minScale * subscale;
+}
+
+function drawLine(x1, y1, x2, y2) {
+    var unit = scale * ticks;
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+    ctx.beginPath();
+    ctx.moveTo(xoffset + x1 * unit, yoffset + y1 * unit);
+    ctx.lineTo(xoffset + x2 * unit, yoffset + y2 * unit);
+    ctx.stroke();
+}
+
+function drawPoint(px, py) {
+    var unit = scale * ticks;
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+    var _px = px * unit + xoffset;
+    var _py = py * unit + yoffset;
+    ctx.beginPath();
+    ctx.arc(_px, _py, 3, 0, Math.PI*2, true);
+    ctx.closePath();
+    ctx.stroke();
+}
+
+function drawPointSolid(px, py) {
+    drawPoint(px, py);
+    ctx.fillStyle = "rgba(0,0,0, 0.4)";
+    ctx.fill();
+}
+
+function drawLabel(num, px, py) {
+    ctx.beginPath();
+    ctx.arc(px, py, 8, 0, Math.PI*2, true);
+    ctx.closePath();
+    ctx.strokeStyle = "rgba(0,0,0, 0.4)";
+    ctx.lineWidth = num == 0 || num == 3 ? 2 : 1;
+    ctx.stroke();
+    ctx.fillStyle = "black";
+    ctx.font = "normal 10px Arial";
+  //  ctx.rotate(0.001);
+    ctx.fillText(num, px - 2, py + 3);
+  //  ctx.rotate(-0.001);
+}
+
+function drawLabelX(ymin, num, loc) {
+    var unit = scale * ticks;
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+    var px = loc * unit + xoffset;
+    var py = ymin * unit + yoffset  - 20;
+    drawLabel(num, px, py);
+}
+
+function drawLabelY(xmin, num, loc) {
+    var unit = scale * ticks;
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+    var px = xmin * unit + xoffset - 20;
+    var py = loc * unit + yoffset;
+    drawLabel(num, px, py);
+}
+
+function drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY) {
+    ctx.beginPath();
+    ctx.moveTo(hx, hy - 100);
+    ctx.lineTo(hx, hy);
+    ctx.strokeStyle = hMinY < 0 ? "green" : "blue";
+    ctx.stroke();
+    ctx.beginPath();
+    ctx.moveTo(hx, hy);
+    ctx.lineTo(hx, hy + 100);
+    ctx.strokeStyle = hMaxY > 0 ? "green" : "blue";
+    ctx.stroke();
+    ctx.beginPath();
+    ctx.moveTo(hx - 100, hy);
+    ctx.lineTo(hx, hy);
+    ctx.strokeStyle = hMinX < 0 ? "green" : "blue";
+    ctx.stroke();
+    ctx.beginPath();
+    ctx.moveTo(hx, hy);
+    ctx.lineTo(hx + 100, hy);
+    ctx.strokeStyle = hMaxX > 0 ? "green" : "blue";
+    ctx.stroke();
+}
+
+function logCurves(test) {
+    for (curves in test) {
+        var curve = test[curves];
+        if (curve.length != 8) {
+            continue;
+        }
+        var str = "{{";
+        for (i = 0; i < 8; i += 2) {
+            str += curve[i].toFixed(2) + "," + curve[i + 1].toFixed(2);
+            if (i < 6) {
+                str += "}, {";
+            }
+        }
+        str += "}}";
+        console.log(str);
+    }
+}
+
+function scalexy(x, y, mag) {
+    var length = Math.sqrt(x * x + y * y);
+    return mag / length;
+}
+
+function drawArrow(x, y, dx, dy) {
+    var unit = scale * ticks;
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+    var dscale = scalexy(dx, dy, 1);
+    dx *= dscale;
+    dy *= dscale;
+    ctx.beginPath();
+    ctx.moveTo(xoffset + x * unit, yoffset + y * unit);
+    x += dx;
+    y += dy;
+    ctx.lineTo(xoffset + x * unit, yoffset + y * unit);
+    dx /= 10;
+    dy /= 10;
+    ctx.lineTo(xoffset + (x - dy) * unit, yoffset + (y + dx) * unit);
+    ctx.lineTo(xoffset + (x + dx * 2) * unit, yoffset + (y + dy * 2) * unit);
+    ctx.lineTo(xoffset + (x + dy) * unit, yoffset + (y - dx) * unit);
+    ctx.lineTo(xoffset + x * unit, yoffset + y * unit);
+    ctx.strokeStyle = "rgba(0,75,0, 0.4)";
+    ctx.stroke();
+}
+
+function draw(test, title) {
+    ctx.fillStyle = "rgba(0,0,0, 0.1)";
+    ctx.font = "normal 50px Arial";
+    ctx.fillText(title, 50, 50);
+    ctx.font = "normal 10px Arial";
+    var unit = scale * ticks;
+  //  ctx.lineWidth = "1.001"; "0.999";
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+
+    for (curves in test) {
+        var curve = test[curves];
+        if (curve.length != 8) {
+            continue;
+        }
+        ctx.lineWidth = 1;
+        if (draw_tangents) {
+            ctx.strokeStyle = "rgba(0,0,255, 0.3)";
+            drawLine(curve[0], curve[1], curve[2], curve[3]);
+            drawLine(curve[2], curve[3], curve[4], curve[5]);
+            drawLine(curve[4], curve[5], curve[6], curve[7]);
+        }
+        if (draw_deriviatives) {
+            var dx = dx_at_t(curve, 0);
+            var dy = dy_at_t(curve, 0);
+            drawArrow(curve[0], curve[1], dx, dy);
+            dx = dx_at_t(curve, 1);
+            dy = dy_at_t(curve, 1);
+            drawArrow(curve[6], curve[7], dx, dy);
+            if (draw_midpoint) {
+                var midX = x_at_t(curve, 0.5);
+                var midY = y_at_t(curve, 0.5);
+                dx = dx_at_t(curve, 0.5);
+                dy = dy_at_t(curve, 0.5);
+                drawArrow(midX, midY, dx, dy);
+            }
+        }
+        ctx.beginPath();
+        ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
+        ctx.bezierCurveTo(
+            xoffset + curve[2] * unit, yoffset + curve[3] * unit,
+            xoffset + curve[4] * unit, yoffset + curve[5] * unit,
+            xoffset + curve[6] * unit, yoffset + curve[7] * unit);
+        ctx.strokeStyle = "black";
+        ctx.stroke();
+        if (draw_endpoints) {
+            drawPoint(curve[0], curve[1]);
+            drawPoint(curve[2], curve[3]);
+            drawPoint(curve[4], curve[5]);
+            drawPoint(curve[6], curve[7]);
+        }
+        if (draw_midpoint) {
+            var midX = x_at_t(curve, 0.5);
+            var midY = y_at_t(curve, 0.5);
+            drawPointSolid(midX, midY);
+        }
+        if (draw_hodo) {
+            var hodo = hodograph(curve);
+            var hMinX = Math.min(0, hodo[0], hodo[2], hodo[4]);
+            var hMinY = Math.min(0, hodo[1], hodo[3], hodo[5]);
+            var hMaxX = Math.max(0, hodo[0], hodo[2], hodo[4]);
+            var hMaxY = Math.max(0, hodo[1], hodo[3], hodo[5]);
+            var hScaleX = hMaxX - hMinX > 0 ? ctx.canvas.width / (hMaxX - hMinX) : 1;
+            var hScaleY = hMaxY - hMinY > 0 ? ctx.canvas.height / (hMaxY - hMinY) : 1;
+            var hUnit = Math.min(hScaleX, hScaleY);
+            hUnit /= 2;
+            var hx = xoffset - hMinX * hUnit;
+            var hy = yoffset - hMinY * hUnit;
+            ctx.moveTo(hx + hodo[0] * hUnit, hy + hodo[1] * hUnit);
+            ctx.quadraticCurveTo(
+                hx + hodo[2] * hUnit, hy + hodo[3] * hUnit,
+                hx + hodo[4] * hUnit, hy + hodo[5] * hUnit);
+            ctx.strokeStyle = "red";
+            ctx.stroke();
+            if (draw_hodo_origin) {
+                drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY);
+            }
+        }
+        if (draw_hodo2) {
+            var hodo = hodograph2(curve);
+            var hMinX = Math.min(0, hodo[0], hodo[2]);
+            var hMinY = Math.min(0, hodo[1], hodo[3]);
+            var hMaxX = Math.max(0, hodo[0], hodo[2]);
+            var hMaxY = Math.max(0, hodo[1], hodo[3]);
+            var hScaleX = hMaxX - hMinX > 0 ? ctx.canvas.width / (hMaxX - hMinX) : 1;
+            var hScaleY = hMaxY - hMinY > 0 ? ctx.canvas.height / (hMaxY - hMinY) : 1;
+            var hUnit = Math.min(hScaleX, hScaleY);
+            hUnit /= 2;
+            var hx = xoffset - hMinX * hUnit;
+            var hy = yoffset - hMinY * hUnit;
+            ctx.moveTo(hx + hodo[0] * hUnit, hy + hodo[1] * hUnit);
+            ctx.lineTo(hx + hodo[2] * hUnit, hy + hodo[3] * hUnit);
+            ctx.strokeStyle = "red";
+            ctx.stroke();
+            drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY);
+        }
+        if (draw_sequence) {
+            var ymin = Math.min(curve[1], curve[3], curve[5], curve[7]);
+            for (var i = 0; i < 8; i+= 2) {
+                drawLabelX(ymin, i >> 1, curve[i]);
+            }
+            var xmin = Math.min(curve[0], curve[2], curve[4], curve[6]);
+            for (var i = 1; i < 8; i+= 2) {
+                drawLabelY(xmin, i >> 1, curve[i]);
+            }
+        }
+    }
+}
+
+function drawTop() {
+    init(tests[testIndex]);
+    redraw();
+}
+
+function redraw() {
+    ctx.beginPath();
+    ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height);
+    ctx.fillStyle="white";
+    ctx.fill();
+    draw(tests[testIndex], testTitles[testIndex]);
+}
+
+function doKeyPress(evt) {
+    var char = String.fromCharCode(evt.charCode);
+    switch (char) {
+    case '2':
+        draw_hodo2 ^= true;
+        redraw();
+        break;
+    case 'd':
+        draw_deriviatives ^= true;
+        redraw();
+        break;
+    case 'e':
+        draw_endpoints ^= true;
+        redraw();
+        break;
+    case 'h':
+        draw_hodo ^= true;
+        redraw();
+        break;
+    case 'N':
+        testIndex += 9;
+    case 'n':
+        if (++testIndex >= tests.length)
+            testIndex = 0;
+        drawTop();
+        break;
+    case 'l':
+        logCurves(tests[testIndex]);
+        break;
+    case 'm':
+        draw_midpoint ^= true;
+        redraw();
+        break;
+    case 'o':
+        draw_hodo_origin ^= true;
+        redraw();
+        break;
+    case 'P':
+        testIndex -= 9;
+    case 'p':
+        if (--testIndex < 0)
+            testIndex = tests.length - 1;
+        drawTop();
+        break;
+    case 's':
+        draw_sequence ^= true;
+        redraw();
+        break;
+    case 't':
+        draw_tangents ^= true;
+        redraw();
+        break;
+    }
+}
+
+function calcXY() {
+    var e = window.event;
+	var tgt = e.target || e.srcElement;
+    var left = tgt.offsetLeft;
+    var top = tgt.offsetTop;
+    var unit = scale * ticks;
+    mouseX = (e.clientX - left - Math.ceil(at_x) + 1) / unit + xStart;
+    mouseY = (e.clientY - top - Math.ceil(at_y)) / unit + yStart;
+}
+
+var lastX, lastY;
+var activeCurve = [];
+var activePt;
+
+function handleMouseClick() {
+    calcXY();
+}
+
+function initDown() {
+    var unit = scale * ticks;
+    var xoffset = xStart * -unit + at_x;
+    var yoffset = yStart * -unit + at_y;
+    var test = tests[testIndex];
+    var bestDistance = 1000000;
+    activePt = -1;
+    for (curves in test) {
+        var testCurve = test[curves];
+        if (testCurve.length != 8) {
+            continue;
+        }
+        for (var i = 0; i < 8; i += 2) {
+            var testX = testCurve[i];
+            var testY = testCurve[i + 1];
+            var dx = testX - mouseX;
+            var dy = testY - mouseY;
+            var dist = dx * dx + dy * dy;
+            if (dist > bestDistance) {
+                continue;
+            }
+            activeCurve = testCurve;
+            activePt = i;
+            bestDistance = dist;
+        }
+    }
+    if (activePt >= 0) {
+        lastX = mouseX;
+        lastY = mouseY;
+    }
+}
+
+function handleMouseOver() {
+    if (!mouseDown) {
+        activePt = -1;
+        return;
+    }
+    calcXY();
+    if (activePt < 0) {
+        initDown();
+        return;
+    }
+    var unit = scale * ticks;
+    var deltaX = (mouseX - lastX) /* / unit */;
+    var deltaY = (mouseY - lastY) /*/ unit */;
+    lastX = mouseX;
+    lastY = mouseY;
+    activeCurve[activePt] += deltaX;
+    activeCurve[activePt + 1] += deltaY;
+    redraw();
+}
+
+function start() {
+    for (i = 0; i < testDivs.length; ++i) {
+        var title = testDivs[i].id.toString();
+        var str = testDivs[i].firstChild.data;
+        parse(str, title);
+    }
+    drawTop();
+    window.addEventListener('keypress', doKeyPress, true);
+    window.onresize = function() {
+        drawTop();
+    }
+}
+
+</script>
+</head>
+
+<body onLoad="start();">
+<canvas id="canvas" width="750" height="500"
+    onmousedown="mouseDown = true"
+    onmouseup="mouseDown = false"
+    onmousemove="handleMouseOver()"
+    onclick="handleMouseClick()"
+    ></canvas >
+</body>
+</html>