experimental/Intersection/hg.htm - skia - Git at Google

 <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>
	<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+\.\de?-?\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>