SHARE
TWEET

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

a guest Feb 17th, 2011 1,090 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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>
RAW Paste Data
Top