Advertisement
Guest User

Javascript implementation of "Digesting Duck :: Simple Stupid Funnel Algorithm "

a guest
Feb 17th, 2011
2,203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 4.38 KB | None | 0 0
  1. <html>
  2. <head>
  3. <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
  4. </head>
  5. <body>
  6.  
  7. <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>
  8.  
  9. <canvas width="640" height="420" style="border:1px solid black;"></canvas>
  10.  
  11. <script type="text/javascript"><!--
  12. function Point(x, y) {
  13.     return {x:x, y:y};
  14. }
  15.  
  16. function triarea2(a, b, c) {
  17.     var ax = b.x - a.x;
  18.     var ay = b.y - a.y;
  19.     var bx = c.x - a.x;
  20.     var by = c.y - a.y;
  21.     return bx * ay - ax * by;
  22. }
  23.  
  24. function vdistsqr(a, b) {
  25.     var x = b.x - a.x, y = b.y - a.y;
  26.     return Math.sqrt(x * x + y * y);
  27. }
  28.  
  29. function vequal(a, b) {
  30.     return vdistsqr(a, b) < (0.001 * 0.001);
  31. }
  32.  
  33. function Channel() {
  34.     this.portals = [];
  35. };
  36.  
  37. Channel.prototype.push = function(p1, p2) {
  38.     if (p2 === undefined) p2 = p1;
  39.     this.portals.push({left : p1, right: p2});
  40. };
  41.  
  42. Channel.prototype.stringPull = function() {
  43.     var portals = this.portals;
  44.     var pts = [];
  45.     // Init scan state
  46.     var portalApex, portalLeft, portalRight;
  47.     var apexIndex = 0, leftIndex = 0, rightIndex = 0;
  48.    
  49.     portalApex  = portals[0].left;
  50.     portalLeft  = portals[0].left;
  51.     portalRight = portals[0].right;
  52.  
  53.     // Add start point.
  54.     pts.push(portalApex);
  55.    
  56.     for (var i = 1; i < portals.length; i++) {
  57.         var left  = portals[i].left;
  58.         var right = portals[i].right;
  59.  
  60.         // Update right vertex.
  61.         if (triarea2(portalApex, portalRight, right) <= 0.0) {
  62.             if (vequal(portalApex, portalRight) || triarea2(portalApex, portalLeft, right) > 0.0) {
  63.                 // Tighten the funnel.
  64.                 portalRight = right;
  65.                 rightIndex = i;
  66.             } else {
  67.                 // Right over left, insert left to path and restart scan from portal left point.
  68.                 pts.push(portalLeft);
  69.                 // Make current left the new apex.
  70.                 portalApex = portalLeft;
  71.                 apexIndex = leftIndex;
  72.                 // Reset portal
  73.                 portalLeft = portalApex;
  74.                 portalRight = portalApex;
  75.                 leftIndex = apexIndex;
  76.                 rightIndex = apexIndex;
  77.                 // Restart scan
  78.                 i = apexIndex;
  79.                 continue;
  80.             }
  81.         }
  82.  
  83.         // Update left vertex.
  84.         if (triarea2(portalApex, portalLeft, left) >= 0.0) {
  85.             if (vequal(portalApex, portalLeft) || triarea2(portalApex, portalRight, left) < 0.0) {
  86.                 // Tighten the funnel.
  87.                 portalLeft = left;
  88.                 leftIndex = i;
  89.             } else {
  90.                 // Left over right, insert right to path and restart scan from portal right point.
  91.                 pts.push(portalRight);
  92.                 // Make current right the new apex.
  93.                 portalApex = portalRight;
  94.                 apexIndex = rightIndex;
  95.                 // Reset portal
  96.                 portalLeft = portalApex;
  97.                 portalRight = portalApex;
  98.                 leftIndex = apexIndex;
  99.                 rightIndex = apexIndex;
  100.                 // Restart scan
  101.                 i = apexIndex;
  102.                 continue;
  103.             }
  104.         }
  105.     }
  106.    
  107.     if ((pts.length == 0) || (!vequal(pts[pts.length - 1], portals[portals.length - 1].left))) {
  108.         // Append last point to path.
  109.         pts.push(portals[portals.length - 1].left);
  110.     }
  111.    
  112.     this.path = pts;
  113.     return pts;
  114. };
  115.  
  116. Channel.prototype.draw = function(ctx, pd, pm) {
  117.     //ctx.beginPath();
  118.  
  119.     ctx.translate(pd.x, pd.y);
  120.     //ctx.scale(mx, my);
  121.    
  122.     function line(p1, p2) {
  123.         ctx.moveTo(p1.x * pm.x, p1.y * pm.y);
  124.         ctx.lineTo(p2.x * pm.x, p2.y * pm.y);
  125.     }
  126.    
  127.     function lines(vv, z) {
  128.         if (z === undefined) {
  129.             for (var n = 1; n < vv.length; n++) {
  130.                 line(vv[n - 1], vv[n]);
  131.             }
  132.         } else {
  133.             for (var n = 1; n < vv.length; n++) {
  134.                 line(vv[n - 1][z], vv[n][z]);
  135.             }
  136.         }
  137.     }
  138.  
  139.     ctx.globalAlpha = 1.0;
  140.     var portals = this.portals;
  141.     $(['left', 'right']).each(function(k, v) {
  142.         ctx.strokeStyle = 'black';
  143.         ctx.lineWidth = 2;
  144.         ctx.lineCap = 'round';
  145.         ctx.strokeStyle = k ? 'black' : 'blue';
  146.         ctx.beginPath();
  147.         lines(portals, v);
  148.         ctx.closePath();
  149.         ctx.stroke();
  150.     });
  151.  
  152.     ctx.strokeStyle = 'red';
  153.     ctx.globalAlpha = 0.6;
  154.     ctx.lineWidth = 4;
  155.     ctx.lineCap = 'round';
  156.     ctx.beginPath();
  157.     lines(this.path);
  158.     ctx.closePath();
  159.     ctx.stroke();
  160.  
  161.     //ctx.closePath();
  162. };
  163.  
  164. var channel = new Channel();
  165. channel.push(Point( 1,   0));
  166. channel.push(Point( 0,   4),   Point( 4,  3));
  167. channel.push(Point( 4,   7),   Point( 4,  3));
  168. channel.push(Point(16,   0),   Point(10,  1));
  169. channel.push(Point(16,   0),   Point( 9, -5));
  170. channel.push(Point(12, -11));
  171. channel.stringPull();
  172. channel.draw($('canvas').get(0).getContext('2d'), Point(160, 250), Point(20, 20));
  173.  
  174. --></script>
  175.  
  176. </body>
  177. </html>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement