Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <html>
- <head>
- <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
- </head>
- <body>
- <div>Javascript implementation of: <a href="http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html">http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html</a></div>
- <canvas width="640" height="420" style="border:1px solid black;"></canvas>
- <script type="text/javascript"><!--
- function Point(x, y) {
- return {x:x, y:y};
- }
- function triarea2(a, b, c) {
- var ax = b.x - a.x;
- var ay = b.y - a.y;
- var bx = c.x - a.x;
- var by = c.y - a.y;
- return bx * ay - ax * by;
- }
- function vdistsqr(a, b) {
- var x = b.x - a.x, y = b.y - a.y;
- return Math.sqrt(x * x + y * y);
- }
- function vequal(a, b) {
- return vdistsqr(a, b) < (0.001 * 0.001);
- }
- function Channel() {
- this.portals = [];
- };
- Channel.prototype.push = function(p1, p2) {
- if (p2 === undefined) p2 = p1;
- this.portals.push({left : p1, right: p2});
- };
- Channel.prototype.stringPull = function() {
- var portals = this.portals;
- var pts = [];
- // Init scan state
- var portalApex, portalLeft, portalRight;
- var apexIndex = 0, leftIndex = 0, rightIndex = 0;
- portalApex = portals[0].left;
- portalLeft = portals[0].left;
- portalRight = portals[0].right;
- // Add start point.
- pts.push(portalApex);
- for (var i = 1; i < portals.length; i++) {
- var left = portals[i].left;
- var right = portals[i].right;
- // Update right vertex.
- if (triarea2(portalApex, portalRight, right) <= 0.0) {
- if (vequal(portalApex, portalRight) || triarea2(portalApex, portalLeft, right) > 0.0) {
- // Tighten the funnel.
- portalRight = right;
- rightIndex = i;
- } else {
- // Right over left, insert left to path and restart scan from portal left point.
- pts.push(portalLeft);
- // Make current left the new apex.
- portalApex = portalLeft;
- apexIndex = leftIndex;
- // Reset portal
- portalLeft = portalApex;
- portalRight = portalApex;
- leftIndex = apexIndex;
- rightIndex = apexIndex;
- // Restart scan
- i = apexIndex;
- continue;
- }
- }
- // Update left vertex.
- if (triarea2(portalApex, portalLeft, left) >= 0.0) {
- if (vequal(portalApex, portalLeft) || triarea2(portalApex, portalRight, left) < 0.0) {
- // Tighten the funnel.
- portalLeft = left;
- leftIndex = i;
- } else {
- // Left over right, insert right to path and restart scan from portal right point.
- pts.push(portalRight);
- // Make current right the new apex.
- portalApex = portalRight;
- apexIndex = rightIndex;
- // Reset portal
- portalLeft = portalApex;
- portalRight = portalApex;
- leftIndex = apexIndex;
- rightIndex = apexIndex;
- // Restart scan
- i = apexIndex;
- continue;
- }
- }
- }
- if ((pts.length == 0) || (!vequal(pts[pts.length - 1], portals[portals.length - 1].left))) {
- // Append last point to path.
- pts.push(portals[portals.length - 1].left);
- }
- this.path = pts;
- return pts;
- };
- Channel.prototype.draw = function(ctx, pd, pm) {
- //ctx.beginPath();
- ctx.translate(pd.x, pd.y);
- //ctx.scale(mx, my);
- function line(p1, p2) {
- ctx.moveTo(p1.x * pm.x, p1.y * pm.y);
- ctx.lineTo(p2.x * pm.x, p2.y * pm.y);
- }
- function lines(vv, z) {
- if (z === undefined) {
- for (var n = 1; n < vv.length; n++) {
- line(vv[n - 1], vv[n]);
- }
- } else {
- for (var n = 1; n < vv.length; n++) {
- line(vv[n - 1][z], vv[n][z]);
- }
- }
- }
- ctx.globalAlpha = 1.0;
- var portals = this.portals;
- $(['left', 'right']).each(function(k, v) {
- ctx.strokeStyle = 'black';
- ctx.lineWidth = 2;
- ctx.lineCap = 'round';
- ctx.strokeStyle = k ? 'black' : 'blue';
- ctx.beginPath();
- lines(portals, v);
- ctx.closePath();
- ctx.stroke();
- });
- ctx.strokeStyle = 'red';
- ctx.globalAlpha = 0.6;
- ctx.lineWidth = 4;
- ctx.lineCap = 'round';
- ctx.beginPath();
- lines(this.path);
- ctx.closePath();
- ctx.stroke();
- //ctx.closePath();
- };
- var channel = new Channel();
- channel.push(Point( 1, 0));
- channel.push(Point( 0, 4), Point( 4, 3));
- channel.push(Point( 4, 7), Point( 4, 3));
- channel.push(Point(16, 0), Point(10, 1));
- channel.push(Point(16, 0), Point( 9, -5));
- channel.push(Point(12, -11));
- channel.stringPull();
- channel.draw($('canvas').get(0).getContext('2d'), Point(160, 250), Point(20, 20));
- --></script>
- </body>
- </html>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement