experimental/Intersection/hg.htm

<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>