• API
• FAQ
• Tools
• Archive
daily pastebin goal
37%
SHARE
TWEET

# Javascript implementation of &quot;Digesting Duck :: Simple Stupid Funnel Algorithm &quot;

a guest Feb 17th, 2011 1,224 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. <html>
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.
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top