1 /** 2 * This file is part of JSXGraph. 3 * It is taken from the $n algorithm and is under the "New BSD License" (see below) 4 * 5 * * The $N Multistroke Recognizer (JavaScript version) 6 * 7 * Jacob O. Wobbrock 8 * The Information School 9 * University of Washington 10 * Mary Gates Hall, Box 352840 11 * Seattle, WA 98195-2840 12 * wobbrock@u.washington.edu 13 * 14 * Lisa Anthony 15 * Lockheed Martin 16 * Advanced Technology Laboratories 17 * 3 Executive Campus, Suite 600 18 * Cherry Hill, NJ 08002 19 * lanthony@atl.lmco.com 20 * 21 * 22 * This software is distributed under the "New BSD License" agreement: 23 * 24 * Copyright (c) 2007-2010, Jacob O. Wobbrock and Lisa Anthony 25 * All rights reserved. 26 * 27 * Redistribution and use in source and binary forms, with or without 28 * modification, are permitted provided that the following conditions are met: 29 * * Redistributions of source code must retain the above copyright 30 * notice, this list of conditions and the following disclaimer. 31 * * Redistributions in binary form must reproduce the above copyright 32 * notice, this list of conditions and the following disclaimer in the 33 * documentation and/or other materials provided with the distribution. 34 * * Neither the name of the University of Washington or Lockheed Martin, 35 * nor the names of its contributors may be used to endorse or promote 36 * products derived from this software without specific prior written 37 * permission. 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 40 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 41 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Jacob O. Wobbrock OR Lisa Anthony 43 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 44 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 45 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 47 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 48 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 49 * SUCH DAMAGE. 50 * 51 */ 52 53 // 54 // Point class 55 // 56 function Point(x, y) // constructor 57 { 58 this.X = x; 59 this.Y = y; 60 } 61 // 62 // Rectangle class 63 // 64 function Rectangle(x, y, width, height) // constructor 65 { 66 this.X = x; 67 this.Y = y; 68 this.Width = width; 69 this.Height = height; 70 } 71 // 72 // Template class: a unistroke template 73 // 74 function Template(name, useLimitedRotationInvariance, points) // constructor 75 { 76 this.Name = name; 77 this.Points = Resample(points, NumPoints); 78 var radians = IndicativeAngle(this.Points); 79 this.Points = RotateBy(this.Points, -radians); 80 this.Points = ScaleDimTo(this.Points, SquareSize, OneDThreshold); 81 if (useLimitedRotationInvariance) this.Points = RotateBy(this.Points, +radians); 82 this.Points = TranslateTo(this.Points, Origin); 83 this.StartUnitVector = CalcStartUnitVector(this.Points, StartAngleIndex); 84 } 85 // 86 // Multistroke class: a container for unistroke templates 87 // 88 function Multistroke(name, useLimitedRotationInvariance, strokes) // constructor 89 { 90 this.Name = name; 91 this.NumStrokes = strokes.length; // number of individual strokes 92 93 var order = new Array(); // array of integer indices 94 for (var i = 0; i < strokes.length; i++) 95 order[i] = i; // initialize 96 97 var orders = new Array(); // array of integer arrays 98 HeapPermute(strokes.length, order, /*out*/ orders); 99 100 this.Templates = new Array(); 101 var unistrokes = MakeUnistrokes(strokes, orders); // returns array of point arrays 102 for (var j = 0; j < unistrokes.length; j++) 103 this.Templates[j] = new Template(name, useLimitedRotationInvariance, unistrokes[j]); 104 } 105 // 106 // Result class 107 // 108 function Result(name, score) // constructor 109 { 110 this.Name = name; 111 this.Score = score; 112 } 113 // 114 // NDollarRecognizer class constants 115 // 116 var NumMultistrokes = 16; 117 var NumPoints = 96; 118 var SquareSize = 250.0; 119 var OneDThreshold = 0.25; // customize to desired gesture set (usually 0.20-0.35) 120 var Origin = new Point(0,0); 121 var Diagonal = Math.sqrt(SquareSize * SquareSize + SquareSize * SquareSize); 122 var HalfDiagonal = 0.5 * Diagonal; 123 var AngleRange = Deg2Rad(45.0); 124 var AnglePrecision = Deg2Rad(2.0); 125 var Phi = 0.5 * (-1.0 + Math.sqrt(5.0)); // Golden Ratio 126 var StartAngleIndex = (NumPoints / 8); // eighth of gesture length 127 var AngleSimilarityThreshold = Deg2Rad(30.0); 128 // 129 // NDollarRecognizer class 130 // 131 function NDollarRecognizer(useLimitedRotationInvariance) // constructor 132 { 133 // 134 // one predefined multistroke for each gesture type 135 // 136 this.Multistrokes = new Array(); 137 138 this.Multistrokes[0] = new Multistroke("line", false, new Array(new Array(new Point(1,100),new Point(100,100)))); 139 140 /*points_opt_circle = new Array(); 141 for (i=0;i<30;i++){ 142 points_opt_circle[i] = new Point(Math.round(100+Math.cos(i*12/360*Math.PI)*50),Math.round(100+Math.sin(i*12/360*Math.PI)*50)); 143 }*/ 144 145 146 //this.Multistrokes[1] = new Multistroke("circle", false, new Array(points_opt_circle)); 147 this.Multistrokes[1] = new Multistroke("circle", false, new Array(new Array(new Point(97,175),new Point(97,152),new Point(97,151),new Point(97,149),new Point(97,147),new Point(97,146),new Point(97,144),new Point(97,143),new Point(97,141),new Point(97,140),new Point(97,139),new Point(97,138),new Point(97,137),new Point(98,135),new Point(98,132),new Point(99,131),new Point(100,129),new Point(101,127),new Point(103,123),new Point(105,120),new Point(107,118),new Point(108,116),new Point(109,115),new Point(110,114),new Point(110,113),new Point(112,111),new Point(113,111),new Point(115,108),new Point(117,106),new Point(119,104),new Point(121,103),new Point(121,102),new Point(123,101),new Point(125,99),new Point(129,96),new Point(133,94),new Point(138,92),new Point(141,91),new Point(143,90),new Point(144,89),new Point(146,89),new Point(149,88),new Point(154,87),new Point(159,84),new Point(163,84),new Point(166,84),new Point(167,84),new Point(168,84),new Point(171,84),new Point(173,83),new Point(176,83),new Point(179,83),new Point(181,83),new Point(184,83),new Point(186,83),new Point(188,83),new Point(191,83),new Point(193,83),new Point(197,83),new Point(203,83),new Point(204,83),new Point(205,83),new Point(206,83),new Point(207,83),new Point(208,83),new Point(211,83),new Point(214,83),new Point(217,83),new Point(219,84),new Point(220,84),new Point(221,84),new Point(223,86),new Point(225,87),new Point(228,89),new Point(229,90),new Point(231,93),new Point(233,94),new Point(234,95),new Point(236,96),new Point(237,98),new Point(239,99),new Point(241,101),new Point(243,104),new Point(245,105),new Point(246,108),new Point(248,110),new Point(250,113),new Point(253,118),new Point(256,122),new Point(257,125),new Point(257,127),new Point(258,130),new Point(260,133),new Point(261,135),new Point(262,138),new Point(264,140),new Point(264,141),new Point(265,143),new Point(265,145),new Point(266,148),new Point(267,152),new Point(267,159),new Point(268,165),new Point(269,167),new Point(269,168),new Point(269,169),new Point(269,171),new Point(269,172),new Point(269,177),new Point(269,179),new Point(269,180),new Point(269,183),new Point(269,186),new Point(269,188),new Point(269,192),new Point(269,195),new Point(269,197),new Point(269,199),new Point(269,200),new Point(269,202),new Point(269,205),new Point(269,210),new Point(269,215),new Point(269,216),new Point(269,219),new Point(269,220),new Point(268,224),new Point(267,225),new Point(266,226),new Point(265,228),new Point(263,230),new Point(262,230),new Point(261,231),new Point(260,233),new Point(256,235),new Point(254,236),new Point(252,236),new Point(248,238),new Point(243,240),new Point(240,240),new Point(233,244),new Point(226,246),new Point(226,247),new Point(223,247),new Point(221,247),new Point(219,247),new Point(209,247),new Point(207,248),new Point(206,248),new Point(201,248),new Point(196,250),new Point(189,250),new Point(175,250),new Point(173,250),new Point(171,250),new Point(169,250),new Point(164,250),new Point(156,250),new Point(153,250),new Point(152,250),new Point(150,250),new Point(148,250),new Point(145,250),new Point(142,250),new Point(141,250),new Point(140,250),new Point(137,248),new Point(136,247),new Point(134,245),new Point(133,245),new Point(130,242),new Point(129,240),new Point(128,240),new Point(127,239),new Point(126,238),new Point(124,236),new Point(123,234),new Point(123,233),new Point(122,232),new Point(121,230),new Point(120,227),new Point(120,225),new Point(119,223),new Point(118,221),new Point(118,219),new Point(117,216),new Point(116,214),new Point(115,212),new Point(114,209),new Point(112,207),new Point(112,206),new Point(112,201),new Point(111,199),new Point(111,197),new Point(110,193),new Point(103,168),new Point(103,166),new Point(103,164),new Point(103,163),new Point(102,163),new Point(102,161),new Point(101,160),new Point(101,159),new Point(101,158),new Point(101,157),new Point(100,157)))); 148 149 //this.Multistrokes[2] = new Multistroke("square", false, new Array(new Array (new Point(110,110),new Point(160,160),new Point(210,210),new Point(160,260),new Point(110,310),new Point(60,260),new Point(10,210),new Point(60,160)))); 150 this.Multistrokes[2] = new Multistroke("square", false, new Array(new Array (new Point(96,69),new Point(96,70),new Point(96,81),new Point(96,84),new Point(96,89),new Point(96,93),new Point(96,97),new Point(96,102),new Point(96,105),new Point(96,108),new Point(96,112),new Point(96,116),new Point(96,122),new Point(95,130),new Point(95,136),new Point(95,138),new Point(95,141),new Point(95,143),new Point(95,144),new Point(95,146),new Point(95,147),new Point(94,147),new Point(94,148),new Point(94,149),new Point(94,151),new Point(93,154),new Point(92,155),new Point(92,156),new Point(92,159),new Point(91,163),new Point(90,168),new Point(90,175),new Point(90,178),new Point(90,180),new Point(90,182),new Point(90,183),new Point(90,184),new Point(90,187),new Point(90,191),new Point(90,194),new Point(90,197),new Point(90,198),new Point(90,200),new Point(90,202),new Point(90,203),new Point(90,205),new Point(90,206),new Point(90,207),new Point(90,208),new Point(90,209),new Point(91,210),new Point(95,210),new Point(97,210),new Point(99,210),new Point(100,210),new Point(101,210),new Point(103,210),new Point(104,210),new Point(105,210),new Point(107,210),new Point(110,210),new Point(112,210),new Point(115,210),new Point(117,210),new Point(118,210),new Point(120,210),new Point(122,210),new Point(123,210),new Point(126,210),new Point(129,210),new Point(132,210),new Point(134,210),new Point(135,210),new Point(137,210),new Point(139,210),new Point(142,210),new Point(145,210),new Point(147,210),new Point(150,210),new Point(152,210),new Point(153,210),new Point(155,210),new Point(157,210),new Point(159,210),new Point(161,210),new Point(164,210),new Point(167,210),new Point(168,210),new Point(170,210),new Point(174,210),new Point(177,210),new Point(181,210),new Point(183,210),new Point(186,210),new Point(188,210),new Point(191,210),new Point(194,210),new Point(196,210),new Point(197,210),new Point(200,210),new Point(202,210),new Point(205,210),new Point(208,210),new Point(210,210),new Point(211,210),new Point(212,210),new Point(214,210),new Point(216,210),new Point(217,210),new Point(218,210),new Point(219,210),new Point(221,210),new Point(223,210),new Point(224,210),new Point(229,210),new Point(231,210),new Point(233,210),new Point(235,210),new Point(239,210),new Point(241,210),new Point(242,210),new Point(243,210),new Point(244,210),new Point(245,210),new Point(247,210),new Point(251,210),new Point(254,210),new Point(256,210),new Point(258,210),new Point(259,210),new Point(260,210),new Point(261,210),new Point(261,206),new Point(261,196),new Point(261,189),new Point(261,188),new Point(261,187),new Point(261,185),new Point(261,183),new Point(261,180),new Point(261,177),new Point(261,176),new Point(261,172),new Point(261,168),new Point(261,163),new Point(261,160),new Point(261,156),new Point(261,153),new Point(261,152),new Point(261,150),new Point(261,147),new Point(261,144),new Point(261,141),new Point(261,137),new Point(261,135),new Point(261,133),new Point(261,130),new Point(261,128),new Point(261,125),new Point(261,116),new Point(261,113),new Point(261,110),new Point(261,107),new Point(261,104),new Point(261,102),new Point(261,98),new Point(260,93),new Point(260,91),new Point(260,89),new Point(260,88),new Point(260,87),new Point(260,86),new Point(260,84),new Point(260,83),new Point(260,80),new Point(260,79),new Point(260,78),new Point(260,76),new Point(260,74),new Point(260,71),new Point(260,70),new Point(260,69),new Point(260,68),new Point(260,66),new Point(260,63),new Point(260,62),new Point(260,61),new Point(260,60),new Point(259,60),new Point(258,60),new Point(257,60),new Point(255,60),new Point(254,60),new Point(253,60),new Point(251,60),new Point(242,60),new Point(234,60),new Point(230,60),new Point(229,60),new Point(227,60),new Point(220,60),new Point(212,60),new Point(202,60),new Point(195,60),new Point(190,60),new Point(187,60),new Point(185,60),new Point(181,60),new Point(174,60),new Point(167,60),new Point(162,60),new Point(125,62),new Point(118,64),new Point(110,68),new Point(96,70),new Point(94,70),new Point(93,70),new Point(91,70),new Point(89,70),new Point(88,71),new Point(87,71),new Point(86,71),new Point(85,71)))); 151 152 this.Multistrokes[3] = new Multistroke("circle", false, new Array(new Array (new Point(26,226),new Point(26,225),new Point(34,215),new Point(41,207),new Point(49,197),new Point(55,192),new Point(71,177),new Point(89,162),new Point(98,152),new Point(114,140),new Point(120,135),new Point(126,129),new Point(132,126),new Point(137,121),new Point(144,115),new Point(150,111),new Point(157,107),new Point(166,102),new Point(176,97),new Point(182,95),new Point(191,89),new Point(202,84),new Point(215,81),new Point(225,77),new Point(232,74),new Point(239,72),new Point(246,71),new Point(253,70),new Point(263,69),new Point(270,69),new Point(279,69),new Point(293,69),new Point(306,69),new Point(317,69),new Point(331,69),new Point(344,69),new Point(354,69),new Point(368,69),new Point(374,70),new Point(381,73),new Point(384,73),new Point(386,74),new Point(388,75),new Point(389,75),new Point(390,75),new Point(390,77),new Point(390,78),new Point(390,79),new Point(391,80),new Point(393,80),new Point(397,81),new Point(410,87),new Point(417,90),new Point(424,92),new Point(429,94),new Point(436,97),new Point(439,100),new Point(442,100),new Point(444,102),new Point(447,104),new Point(447,105),new Point(448,106),new Point(449,107),new Point(449,108),new Point(450,110),new Point(451,114),new Point(452,115),new Point(453,117),new Point(453,118),new Point(453,119),new Point(454,120),new Point(455,120),new Point(455,121),new Point(455,122)))); 153 this.Multistrokes[4] = new Multistroke("triangle", false, new Array(new Array (new Point(66,236),new Point(66,235),new Point(84,214),new Point(87,210),new Point(94,201),new Point(106,183),new Point(114,175),new Point(119,168),new Point(126,162),new Point(130,156),new Point(135,148),new Point(138,145),new Point(144,137),new Point(150,129),new Point(155,123),new Point(161,117),new Point(166,112),new Point(172,103),new Point(176,94),new Point(183,88),new Point(189,80),new Point(195,74),new Point(203,69),new Point(207,62),new Point(214,55),new Point(217,48),new Point(218,46),new Point(218,45),new Point(219,45),new Point(220,45),new Point(221,45),new Point(225,47),new Point(227,50),new Point(231,57),new Point(235,63),new Point(239,68),new Point(247,80),new Point(250,87),new Point(253,92),new Point(257,99),new Point(262,111),new Point(267,120),new Point(272,128),new Point(282,141),new Point(287,148),new Point(293,160),new Point(296,165),new Point(302,174),new Point(306,181),new Point(311,191),new Point(314,197),new Point(320,209),new Point(323,215),new Point(328,223),new Point(329,227),new Point(335,236),new Point(339,241),new Point(347,255),new Point(352,262),new Point(356,271),new Point(358,274),new Point(359,275),new Point(359,276),new Point(360,276),new Point(358,276),new Point(355,276),new Point(348,276),new Point(332,273),new Point(321,272),new Point(317,272),new Point(313,272),new Point(311,271),new Point(309,270),new Point(301,269),new Point(286,264),new Point(279,263),new Point(265,262),new Point(246,261),new Point(236,261),new Point(222,261),new Point(214,260),new Point(207,259),new Point(197,258),new Point(193,258),new Point(185,256),new Point(175,255),new Point(169,255),new Point(159,254),new Point(155,254),new Point(148,254),new Point(145,254),new Point(139,253),new Point(128,253),new Point(116,253),new Point(113,253),new Point(109,253),new Point(108,253),new Point(107,253),new Point(105,253),new Point(100,252),new Point(97,251),new Point(93,251),new Point(90,249),new Point(85,248),new Point(83,247),new Point(79,245),new Point(77,245),new Point(76,245),new Point(74,245),new Point(60,242),new Point(60,241),new Point(60,240)))); 154 this.Multistrokes[5] = new Multistroke("triangle", false, new Array(new Array (new Point(107,39),new Point(107,45),new Point(100,87),new Point(97,105),new Point(97,109),new Point(96,114),new Point(95,122),new Point(95,131),new Point(95,137),new Point(95,143),new Point(94,147),new Point(94,155),new Point(93,164),new Point(93,172),new Point(91,178),new Point(91,183),new Point(91,184),new Point(91,185),new Point(92,185),new Point(115,185),new Point(120,185),new Point(126,185),new Point(130,185),new Point(134,185),new Point(140,185),new Point(147,185),new Point(161,185),new Point(165,185),new Point(168,185),new Point(173,185),new Point(180,187),new Point(188,187),new Point(193,187),new Point(201,188),new Point(205,189),new Point(208,189),new Point(213,191),new Point(222,193),new Point(225,193),new Point(227,193),new Point(233,193),new Point(236,193),new Point(241,193),new Point(243,193),new Point(248,193),new Point(249,193),new Point(250,193),new Point(249,193),new Point(248,192),new Point(243,188),new Point(240,186),new Point(236,183),new Point(229,176),new Point(222,170),new Point(210,158),new Point(207,156),new Point(206,156),new Point(205,155),new Point(202,152),new Point(194,149),new Point(181,139),new Point(141,108),new Point(135,98),new Point(132,94),new Point(131,92),new Point(129,90),new Point(127,88),new Point(121,81),new Point(119,78),new Point(116,72),new Point(115,69),new Point(110,62),new Point(109,61),new Point(108,58),new Point(106,57),new Point(106,56),new Point(106,55),new Point(105,54),new Point(104,54),new Point(104,53),new Point(104,52)))); 155 this.Multistrokes[6] = new Multistroke("triangle", false, new Array(new Array (new Point(335,111),new Point(347,96),new Point(357,86),new Point(360,82),new Point(362,79),new Point(365,75),new Point(368,72),new Point(370,69),new Point(371,67),new Point(373,64),new Point(375,61),new Point(378,58),new Point(378,57),new Point(379,55),new Point(380,53),new Point(381,52),new Point(383,51),new Point(384,51),new Point(385,51),new Point(386,52),new Point(388,53),new Point(391,55),new Point(394,58),new Point(397,60),new Point(400,64),new Point(402,66),new Point(405,70),new Point(407,74),new Point(411,79),new Point(414,85),new Point(416,89),new Point(418,94),new Point(419,98),new Point(422,104),new Point(423,109),new Point(426,114),new Point(428,121),new Point(429,125),new Point(431,131),new Point(432,135),new Point(433,138),new Point(435,143),new Point(436,147),new Point(438,151),new Point(439,156),new Point(442,160),new Point(442,166),new Point(443,170),new Point(444,174),new Point(445,177),new Point(446,180),new Point(447,182),new Point(448,184),new Point(448,185),new Point(449,187),new Point(450,188),new Point(450,190),new Point(451,192),new Point(452,193),new Point(453,194),new Point(452,194),new Point(449,195),new Point(447,194),new Point(444,194),new Point(442,194),new Point(438,194),new Point(432,193),new Point(425,192),new Point(419,192),new Point(415,191),new Point(408,191),new Point(382,189),new Point(373,189),new Point(367,189),new Point(363,188),new Point(358,188),new Point(355,188),new Point(350,188),new Point(347,188),new Point(344,188),new Point(341,188),new Point(337,188),new Point(335,188),new Point(332,187),new Point(328,187),new Point(326,187),new Point(322,187),new Point(317,186),new Point(315,186),new Point(309,185),new Point(304,185),new Point(300,184),new Point(296,183),new Point(294,183),new Point(294,182),new Point(293,180),new Point(294,179),new Point(295,175),new Point(297,172),new Point(299,169),new Point(302,164),new Point(304,161),new Point(306,158),new Point(309,154),new Point(310,152),new Point(312,150),new Point(313,150),new Point(314,148),new Point(316,146),new Point(317,144),new Point(319,143),new Point(320,141),new Point(322,139),new Point(323,137),new Point(325,135),new Point(327,134),new Point(328,132),new Point(330,130),new Point(331,129),new Point(332,128),new Point(332,126),new Point(333,125),new Point(335,123),new Point(336,122),new Point(338,120),new Point(339,119),new Point(341,118),new Point(342,117),new Point(343,114),new Point(344,113),new Point(345,113),new Point(346,112),new Point(346,110),new Point(347,109),new Point(348,108),new Point(349,107),new Point(350,106),new Point(350,105),new Point(351,104),new Point(352,104),new Point(352,103),new Point(354,102),new Point(355,101),new Point(355,100),new Point(355,99),new Point(356,98),new Point(357,98),new Point(358,97),new Point(359,96),new Point(360,96)))); 156 //2 Gesture for circle with midpoint and point on circle 157 this.Multistrokes[7] = new Multistroke("circle2points", false, new Array(new Array (new Point(199,203),new Point(199,202),new Point(199,198),new Point(199,195),new Point(199,193),new Point(199,190),new Point(199,183),new Point(199,180),new Point(199,179),new Point(199,178),new Point(199,175),new Point(199,174),new Point(199,169),new Point(199,164),new Point(199,160),new Point(199,158),new Point(199,156),new Point(199,155),new Point(199,153),new Point(199,150),new Point(199,145),new Point(199,144),new Point(199,142),new Point(199,140),new Point(199,134),new Point(198,130),new Point(198,126),new Point(197,123),new Point(196,121),new Point(196,119),new Point(196,116),new Point(195,115),new Point(195,113),new Point(195,112),new Point(195,111),new Point(195,110),new Point(195,109),new Point(194,107),new Point(194,106),new Point(194,105),new Point(194,104),new Point(193,104),new Point(192,102),new Point(192,101),new Point(192,100),new Point(192,99),new Point(191,99),new Point(190,99),new Point(187,99),new Point(186,99),new Point(184,99),new Point(182,99),new Point(181,99),new Point(179,99),new Point(177,99),new Point(173,99),new Point(168,99),new Point(164,100),new Point(160,101),new Point(158,103),new Point(155,104),new Point(113,124),new Point(111,125),new Point(111,126),new Point(109,128),new Point(107,129),new Point(107,130),new Point(106,131),new Point(105,132),new Point(104,132),new Point(103,133),new Point(102,134),new Point(101,135),new Point(101,136),new Point(99,137),new Point(99,138),new Point(97,139),new Point(96,140),new Point(95,140),new Point(95,141)))); 158 this.Multistrokes[8] = new Multistroke("circle2points", false, new Array(new Array (new Point(226,248),new Point(226,247),new Point(226,240),new Point(226,234),new Point(226,227),new Point(226,224),new Point(226,220),new Point(226,214),new Point(226,209),new Point(226,197),new Point(227,190),new Point(227,185),new Point(227,181),new Point(227,175),new Point(227,164),new Point(227,162),new Point(227,160),new Point(227,156),new Point(227,152),new Point(227,141),new Point(227,138),new Point(228,136),new Point(228,134),new Point(228,130),new Point(229,117),new Point(229,113),new Point(229,111),new Point(229,108),new Point(229,106),new Point(229,105),new Point(229,102),new Point(229,96),new Point(229,94),new Point(229,92),new Point(229,90),new Point(229,89),new Point(233,88),new Point(235,88),new Point(239,88),new Point(241,87),new Point(244,87),new Point(248,87),new Point(249,87),new Point(251,87),new Point(256,87),new Point(257,87),new Point(259,87),new Point(262,87),new Point(267,87),new Point(270,87),new Point(273,87),new Point(281,91),new Point(289,94),new Point(291,94),new Point(296,98),new Point(298,99),new Point(302,102),new Point(307,105),new Point(315,110),new Point(320,113),new Point(325,118),new Point(326,121),new Point(326,124),new Point(328,126),new Point(328,127),new Point(329,128),new Point(330,129),new Point(330,130)))); 159 // Gesture for remove 160 this.Multistrokes[9] = new Multistroke("removelast", false, new Array(new Array (new Point(310,85),new Point(310,86),new Point(317,97),new Point(334,115),new Point(356,133),new Point(360,138),new Point(366,143),new Point(374,150),new Point(378,155),new Point(386,162),new Point(392,168),new Point(396,172),new Point(397,173),new Point(402,176),new Point(406,183),new Point(408,185),new Point(407,185),new Point(402,184),new Point(395,181),new Point(378,178),new Point(371,174),new Point(366,172),new Point(355,168),new Point(338,163),new Point(335,162),new Point(333,161),new Point(329,161),new Point(325,161),new Point(323,161),new Point(321,161),new Point(318,161),new Point(312,161),new Point(309,161),new Point(308,161),new Point(307,161),new Point(305,161),new Point(305,160),new Point(305,157),new Point(309,152),new Point(318,146),new Point(330,130),new Point(340,120),new Point(356,110),new Point(372,100),new Point(384,86),new Point(394,79),new Point(401,74),new Point(403,72),new Point(404,72),new Point(405,72)))); 161 // gesture for midpoint 162 this.Multistrokes[10] = new Multistroke("midpoint", false, new Array(new Array (new Point(88,230),new Point(89,230),new Point(90,230),new Point(93,230),new Point(93,230),new Point(95,230),new Point(98,230),new Point(100,230),new Point(102,230),new Point(103,231),new Point(105,231),new Point(107,231),new Point(108,231),new Point(110,231),new Point(111,231),new Point(114,231),new Point(117,231),new Point(121,231),new Point(123,231),new Point(126,232),new Point(129,232),new Point(133,232),new Point(136,232),new Point(139,232),new Point(145,232),new Point(150,232),new Point(156,232),new Point(159,232),new Point(161,233),new Point(165,234),new Point(168,234),new Point(171,234),new Point(174,234),new Point(179,234),new Point(184,234),new Point(189,234),new Point(194,234),new Point(198,234),new Point(201,234),new Point(204,233),new Point(210,233),new Point(213,233),new Point(219,232),new Point(226,231),new Point(232,231),new Point(237,231),new Point(245,231),new Point(252,231),new Point(256,231),new Point(261,231),new Point(265,231),new Point(271,231),new Point(276,231),new Point(281,231),new Point(285,231),new Point(287,233),new Point(291,236),new Point(293,239),new Point(295,243),new Point(295,247),new Point(296,250),new Point(296,254),new Point(295,257),new Point(294,259),new Point(291,261),new Point(288,262),new Point(282,262),new Point(273,262),new Point(256,255),new Point(255,249),new Point(253,244),new Point(253,239),new Point(257,233),new Point(262,228),new Point(270,225),new Point(280,224),new Point(289,224),new Point(294,226),new Point(300,230),new Point(303,235),new Point(303,240),new Point(304,245),new Point(304,247),new Point(301,249),new Point(295,252),new Point(279,252),new Point(270,252),new Point(265,249),new Point(261,245),new Point(261,241),new Point(261,237),new Point(261,235),new Point(264,231),new Point(273,229),new Point(282,229),new Point(287,230),new Point(290,231),new Point(297,233),new Point(304,235),new Point(306,235),new Point(309,236),new Point(316,240),new Point(321,241),new Point(323,242),new Point(325,243),new Point(328,243),new Point(333,246),new Point(340,247),new Point(346,247),new Point(351,247),new Point(360,248),new Point(366,248),new Point(372,248),new Point(377,248),new Point(387,248),new Point(391,248),new Point(395,247),new Point(401,247),new Point(407,247),new Point(412,247),new Point(416,247),new Point(421,247),new Point(426,246),new Point(432,246),new Point(435,246),new Point(441,245),new Point(449,245),new Point(453,245),new Point(456,245),new Point(460,244),new Point(463,244),new Point(465,244),new Point(465,244),new Point(466,244),new Point(467,244),new Point(468,244),new Point(470,244),new Point(472,244),new Point(474,244),new Point(477,244),new Point(482,244)))); 163 this.Multistrokes[11] = new Multistroke("midpoint", false, new Array(new Array (new Point(43,471),new Point(57,474),new Point(58,475),new Point(78,482),new Point(85,485),new Point(95,487),new Point(102,489),new Point(111,490),new Point(120,490),new Point(129,492),new Point(142,492),new Point(153,492),new Point(162,492),new Point(173,492),new Point(189,492),new Point(205,494),new Point(224,495),new Point(243,497),new Point(260,503),new Point(270,511),new Point(270,518),new Point(265,524),new Point(256,525),new Point(249,525),new Point(243,521),new Point(239,512),new Point(240,502),new Point(243,496),new Point(252,489),new Point(261,484),new Point(270,483),new Point(280,485),new Point(309,494),new Point(319,496),new Point(328,497),new Point(335,496),new Point(343,496),new Point(350,497),new Point(359,498),new Point(377,499),new Point(387,500),new Point(395,500),new Point(400,501),new Point(405,500),new Point(411,501),new Point(416,501),new Point(420,501),new Point(425,502),new Point(429,502),new Point(432,502),new Point(436,503),new Point(440,504),new Point(444,505),new Point(447,506),new Point(450,506),new Point(453,507),new Point(455,507),new Point(456,507),new Point(458,507),new Point(459,508),new Point(459,507),new Point(462,509),new Point(462,509),new Point(463,509),new Point(465,509),new Point(467,509),new Point(467,508),new Point(469,507),new Point(470,508),new Point(472,507),new Point(473,507),new Point(474,505),new Point(476,504),new Point(477,503),new Point(480,501),new Point(482,500),new Point(483,499),new Point(486,497),new Point(487,495),new Point(489,495),new Point(492,493),new Point(492,492),new Point(494,491)))); 164 /* this.Multistrokes[0] = new Multistroke("T", useLimitedRotationInvariance, new Array( 165 new Array(new Point(30,7),new Point(103,7)), 166 new Array(new Point(66,7),new Point(66,87)) 167 )); 168 this.Multistrokes[1] = new Multistroke("N", useLimitedRotationInvariance, new Array( 169 new Array(new Point(177,92),new Point(177,2)), 170 new Array(new Point(182,1),new Point(246,95)), 171 new Array(new Point(247,87),new Point(247,1)) 172 )); 173 this.Multistrokes[2] = new Multistroke("D", useLimitedRotationInvariance, new Array( 174 new Array(new Point(345,9),new Point(345,87)), 175 new Array(new Point(351,8),new Point(363,8),new Point(372,9),new Point(380,11),new Point(386,14),new Point(391,17),new Point(394,22),new Point(397,28),new Point(399,34),new Point(400,42),new Point(400,50),new Point(400,56),new Point(399,61),new Point(397,66),new Point(394,70),new Point(391,74),new Point(386,78),new Point(382,81),new Point(377,83),new Point(372,85),new Point(367,87),new Point(360,87),new Point(355,88),new Point(349,87)) 176 )); 177 this.Multistrokes[3] = new Multistroke("P", useLimitedRotationInvariance, new Array( 178 new Array(new Point(507,8),new Point(507,87)), 179 new Array(new Point(513,7),new Point(528,7),new Point(537,8),new Point(544,10),new Point(550,12),new Point(555,15),new Point(558,18),new Point(560,22),new Point(561,27),new Point(562,33),new Point(561,37),new Point(559,42),new Point(556,45),new Point(550,48),new Point(544,51),new Point(538,53),new Point(532,54),new Point(525,55),new Point(519,55),new Point(513,55),new Point(510,55)) 180 )); 181 this.Multistrokes[4] = new Multistroke("X", useLimitedRotationInvariance, new Array( 182 new Array(new Point(30,146),new Point(106,222)), 183 new Array(new Point(30,225),new Point(106,146)) 184 )); 185 this.Multistrokes[5] = new Multistroke("H", useLimitedRotationInvariance, new Array( 186 new Array(new Point(188,137),new Point(188,225)), 187 new Array(new Point(188,180),new Point(241,180)), 188 new Array(new Point(241,137),new Point(241,225)) 189 )); 190 this.Multistrokes[6] = new Multistroke("I", useLimitedRotationInvariance, new Array( 191 new Array(new Point(371,149),new Point(371,221)), 192 new Array(new Point(341,149),new Point(401,149)), 193 new Array(new Point(341,221),new Point(401,221)) 194 )); 195 this.Multistrokes[7] = new Multistroke("exclamation", useLimitedRotationInvariance, new Array( 196 new Array(new Point(526,142),new Point(526,204)), 197 new Array(new Point(526,221)) 198 )); 199 this.Multistrokes[8] = new Multistroke("line", useLimitedRotationInvariance, new Array( 200 new Array(new Point(12,347),new Point(119,347)) 201 )); 202 this.Multistrokes[9] = new Multistroke("five-point star", useLimitedRotationInvariance, new Array( 203 new Array(new Point(177,396),new Point(223,299),new Point(262,396),new Point(168,332),new Point(278,332),new Point(184,397)) 204 )); 205 this.Multistrokes[10] = new Multistroke("null", useLimitedRotationInvariance, new Array( 206 new Array(new Point(382,310),new Point(377,308),new Point(373,307),new Point(366,307),new Point(360,310),new Point(356,313),new Point(353,316),new Point(349,321),new Point(347,326),new Point(344,331),new Point(342,337),new Point(341,343),new Point(341,350),new Point(341,358),new Point(342,362),new Point(344,366),new Point(347,370),new Point(351,374),new Point(356,379),new Point(361,382),new Point(368,385),new Point(374,387),new Point(381,387),new Point(390,387),new Point(397,385),new Point(404,382),new Point(408,378),new Point(412,373),new Point(416,367),new Point(418,361),new Point(419,353),new Point(418,346),new Point(417,341),new Point(416,336),new Point(413,331),new Point(410,326),new Point(404,320),new Point(400,317),new Point(393,313),new Point(392,312)), 207 new Array(new Point(418,309),new Point(337,390)) 208 )); 209 this.Multistrokes[11] = new Multistroke("arrowhead", useLimitedRotationInvariance, new Array( 210 new Array(new Point(506,349),new Point(574,349)), 211 new Array(new Point(525,306),new Point(584,349),new Point(525,388)) 212 )); 213 this.Multistrokes[12] = new Multistroke("pitchfork", useLimitedRotationInvariance, new Array( 214 new Array(new Point(38,470),new Point(36,476),new Point(36,482),new Point(37,489),new Point(39,496),new Point(42,500),new Point(46,503),new Point(50,507),new Point(56,509),new Point(63,509),new Point(70,508),new Point(75,506),new Point(79,503),new Point(82,499),new Point(85,493),new Point(87,487),new Point(88,480),new Point(88,474),new Point(87,468)), 215 new Array(new Point(62,464),new Point(62,571)) 216 )); 217 this.Multistrokes[13] = new Multistroke("six-point star", useLimitedRotationInvariance, new Array( 218 new Array(new Point(177,554),new Point(223,476),new Point(268,554),new Point(183,554)), 219 new Array(new Point(177,490),new Point(223,568),new Point(268,490),new Point(183,490)) 220 )); 221 this.Multistrokes[14] = new Multistroke("asterisk", useLimitedRotationInvariance, new Array( 222 new Array(new Point(325,499),new Point(417,557)), 223 new Array(new Point(417,499),new Point(325,557)), 224 new Array(new Point(371,486),new Point(371,571)) 225 )); 226 this.Multistrokes[15] = new Multistroke("half-note", useLimitedRotationInvariance, new Array( 227 new Array(new Point(546,465),new Point(546,531)), 228 new Array(new Point(540,530),new Point(536,529),new Point(533,528),new Point(529,529),new Point(524,530),new Point(520,532),new Point(515,535),new Point(511,539),new Point(508,545),new Point(506,548),new Point(506,554),new Point(509,558),new Point(512,561),new Point(517,564),new Point(521,564),new Point(527,563),new Point(531,560),new Point(535,557),new Point(538,553),new Point(542,548),new Point(544,544),new Point(546,540),new Point(546,536)) 229 )); 230 */ 231 // 232 // The $N Gesture Recognizer API begins here -- 3 methods 233 // 234 this.Recognize = function(strokes, matchOnlyIfSameNumberOfStrokes, useLimitedRotationInvariance) 235 { 236 var points = CombineStrokes(strokes); // make one connected unistroke from the given strokes 237 points = Resample(points, NumPoints); 238 var radians = IndicativeAngle(points); 239 points = RotateBy(points, -radians); 240 points = ScaleDimTo(points, SquareSize, OneDThreshold); 241 if (useLimitedRotationInvariance) points = RotateBy(points, +radians); 242 points = TranslateTo(points, Origin); 243 var startv = CalcStartUnitVector(points, StartAngleIndex); 244 245 var b = +Infinity; 246 var u = -1; 247 for (var i = 0; i < this.Multistrokes.length; i++) // each multistroke 248 { 249 if (!matchOnlyIfSameNumberOfStrokes || strokes.length == this.Multistrokes[i].NumStrokes) // optional -- only attempt match when number of strokes is same 250 { 251 for (var j = 0; j < this.Multistrokes[i].Templates.length; j++) // each unistroke permutation 252 { 253 if (AngleBetweenUnitVectors(startv, this.Multistrokes[i].Templates[j].StartUnitVector) <= AngleSimilarityThreshold) 254 { 255 var d = DistanceAtBestAngle(points, this.Multistrokes[i].Templates[j], -AngleRange, +AngleRange, AnglePrecision); // iterative start 256 if (d < b) 257 { 258 b = d; // distance 259 u = i; // multistroke 260 } 261 } 262 } 263 } 264 } 265 if (u == -1) { 266 return new Result("No match.", 0.0); 267 } else { 268 return new Result(this.Multistrokes[u].Name, 1.0 - (b / HalfDiagonal)); 269 } 270 }; 271 // 272 // add/delete new multistrokes 273 // 274 this.AddMultistroke = function(name, useLimitedRotationInvariance, strokes) 275 { 276 this.Multistrokes[this.Multistrokes.length] = new Multistroke(name, useLimitedRotationInvariance, strokes); 277 var num = 0; 278 for (var i = 0; i < this.Multistrokes.length; i++) 279 { 280 if (this.Multistrokes[i].Name == name) 281 num++; 282 } 283 return num; 284 } 285 this.DeleteUserMultistrokes = function() 286 { 287 this.Multistrokes.length = NumMultistrokes; // clear any beyond the original set 288 return NumMultistrokes; 289 } 290 } 291 // 292 // Private helper functions from this point down 293 // 294 function HeapPermute(n, order, /*out*/ orders) 295 { 296 if (n == 1) 297 { 298 orders[orders.length] = order.slice(); // append copy 299 } 300 else 301 { 302 for (var i = 0; i < n; i++) 303 { 304 HeapPermute(n - 1, order, orders); 305 if (n % 2 == 1) // swap 0, n-1 306 { 307 var tmp = order[0]; 308 order[0] = order[n - 1]; 309 order[n - 1] = tmp; 310 } 311 else // swap i, n-1 312 { 313 var tmp = order[i]; 314 order[i] = order[n - 1]; 315 order[n - 1] = tmp; 316 } 317 } 318 } 319 } 320 function MakeUnistrokes(strokes, orders) 321 { 322 var unistrokes = new Array(); // array of point arrays 323 for (var r = 0; r < orders.length; r++) 324 { 325 for (var b = 0; b < Math.pow(2, orders[r].length); b++) // use b's bits for directions 326 { 327 var unistroke = new Array(); // array of points 328 for (var i = 0; i < orders[r].length; i++) 329 { 330 var pts; 331 if (((b >> i) & 1) == 1) { // is b's bit at index i on? 332 pts = strokes[orders[r][i]].slice().reverse(); // copy and reverse 333 } else { 334 pts = strokes[orders[r][i]].slice(); // copy 335 } 336 for (var p = 0; p < pts.length; p++) { 337 unistroke[unistroke.length] = pts[p]; // append points 338 } 339 } 340 unistrokes[unistrokes.length] = unistroke; // add one unistroke to set 341 } 342 } 343 return unistrokes; 344 } 345 function CombineStrokes(strokes) 346 { 347 var points = new Array(); 348 for (var s = 0; s < strokes.length; s++) { 349 for (var p = 0; p < strokes[s].length; p++) { 350 points[points.length] = new Point(strokes[s][p].X, strokes[s][p].Y); 351 } 352 } 353 return points; 354 } 355 function Resample(points, n) 356 { 357 var I = PathLength(points) / (n - 1); // interval length 358 var D = 0.0; 359 var newpoints = new Array(points[0]); 360 for (var i = 1; i < points.length; i++) 361 { 362 var d = Distance(points[i - 1], points[i]); 363 if ((D + d) >= I) 364 { 365 var qx = points[i - 1].X + ((I - D) / d) * (points[i].X - points[i - 1].X); 366 var qy = points[i - 1].Y + ((I - D) / d) * (points[i].Y - points[i - 1].Y); 367 var q = new Point(qx, qy); 368 newpoints[newpoints.length] = q; // append new point 'q' 369 points.splice(i, 0, q); // insert 'q' at position i in points s.t. 'q' will be the next i 370 D = 0.0; 371 } 372 else D += d; 373 } 374 // somtimes we fall a rounding-error short of adding the last point, so add it if so 375 if (newpoints.length == n - 1) 376 { 377 newpoints[newpoints.length] = new Point(points[points.length - 1].X, points[points.length - 1].Y); 378 } 379 return newpoints; 380 } 381 function IndicativeAngle(points) 382 { 383 var c = Centroid(points); 384 return Math.atan2(c.Y - points[0].Y, c.X - points[0].X); 385 } 386 function RotateBy(points, radians) // rotates points around centroid 387 { 388 var c = Centroid(points); 389 var cos = Math.cos(radians); 390 var sin = Math.sin(radians); 391 392 var newpoints = new Array(); 393 for (var i = 0; i < points.length; i++) 394 { 395 var qx = (points[i].X - c.X) * cos - (points[i].Y - c.Y) * sin + c.X 396 var qy = (points[i].X - c.X) * sin + (points[i].Y - c.Y) * cos + c.Y; 397 newpoints[newpoints.length] = new Point(qx, qy); 398 } 399 return newpoints; 400 } 401 function ScaleDimTo(points, size, oneDratio) // scales bbox uniformly for 1D, non-uniformly for 2D 402 { 403 var B = BoundingBox(points); 404 var uniformly = Math.min(B.Width / B.Height, B.Height / B.Width) <= oneDratio; // 1D or 2D gesture test 405 var newpoints = new Array(); 406 for (var i = 0; i < points.length; i++) 407 { 408 var qx = uniformly ? points[i].X * (size / Math.max(B.Width, B.Height)) : points[i].X * (size / B.Width); 409 var qy = uniformly ? points[i].Y * (size / Math.max(B.Width, B.Height)) : points[i].Y * (size / B.Height); 410 newpoints[newpoints.length] = new Point(qx, qy); 411 } 412 return newpoints; 413 } 414 function TranslateTo(points, pt) // translates points' centroid 415 { 416 var c = Centroid(points); 417 var newpoints = new Array(); 418 for (var i = 0; i < points.length; i++) 419 { 420 var qx = points[i].X + pt.X - c.X; 421 var qy = points[i].Y + pt.Y - c.Y; 422 newpoints[newpoints.length] = new Point(qx, qy); 423 } 424 return newpoints; 425 } 426 function DistanceAtBestAngle(points, T, a, b, threshold) 427 { 428 var x1 = Phi * a + (1.0 - Phi) * b; 429 var f1 = DistanceAtAngle(points, T, x1); 430 var x2 = (1.0 - Phi) * a + Phi * b; 431 var f2 = DistanceAtAngle(points, T, x2); 432 while (Math.abs(b - a) > threshold) 433 { 434 if (f1 < f2) 435 { 436 b = x2; 437 x2 = x1; 438 f2 = f1; 439 x1 = Phi * a + (1.0 - Phi) * b; 440 f1 = DistanceAtAngle(points, T, x1); 441 } 442 else 443 { 444 a = x1; 445 x1 = x2; 446 f1 = f2; 447 x2 = (1.0 - Phi) * a + Phi * b; 448 f2 = DistanceAtAngle(points, T, x2); 449 } 450 } 451 return Math.min(f1, f2); 452 } 453 function DistanceAtAngle(points, T, radians) 454 { 455 var newpoints = RotateBy(points, radians); 456 return PathDistance(newpoints, T.Points); 457 } 458 function Centroid(points) 459 { 460 var x = 0.0, y = 0.0; 461 for (var i = 0; i < points.length; i++) 462 { 463 x += points[i].X; 464 y += points[i].Y; 465 } 466 x /= points.length; 467 y /= points.length; 468 return new Point(x, y); 469 } 470 function BoundingBox(points) 471 { 472 var minX = +Infinity, maxX = -Infinity, minY = +Infinity, maxY = -Infinity; 473 for (var i = 0; i < points.length; i++) 474 { 475 if (points[i].X < minX) 476 minX = points[i].X; 477 if (points[i].X > maxX) 478 maxX = points[i].X; 479 if (points[i].Y < minY) 480 minY = points[i].Y; 481 if (points[i].Y > maxY) 482 maxY = points[i].Y; 483 } 484 return new Rectangle(minX, minY, maxX - minX, maxY - minY); 485 } 486 function PathDistance(pts1, pts2) // average distance between corresponding points in two paths 487 { 488 var d = 0.0; 489 for (var i = 0; i < pts1.length; i++) // assumes pts1.length == pts2.length 490 d += Distance(pts1[i], pts2[i]); 491 return d / pts1.length; 492 } 493 function PathLength(points) // length traversed by a point path 494 { 495 var d = 0.0; 496 for (var i = 1; i < points.length; i++) 497 d += Distance(points[i - 1], points[i]); 498 return d; 499 } 500 function Distance(p1, p2) // distance between two points 501 { 502 var dx = p2.X - p1.X; 503 var dy = p2.Y - p1.Y; 504 return Math.sqrt(dx * dx + dy * dy); 505 } 506 function CalcStartUnitVector(points, index) // start angle from points[0] to points[index] normalized as a unit vector 507 { 508 var v = new Point(points[index].X - points[0].X, points[index].Y - points[0].Y); 509 var len = Math.sqrt(v.X * v.X + v.Y * v.Y); 510 return new Point(v.X / len, v.Y / len); 511 } 512 function AngleBetweenUnitVectors(v1, v2) // gives acute angle between unit vectors from (0,0) to v1, and (0,0) to v2 513 { 514 var n = (v1.X * v2.X + v1.Y * v2.Y); 515 if (n < -1.0 || n > +1.0) 516 n = Round(n, 5); // fix JS rounding bug that can occur so that -1<=n<=+1 517 return Math.acos(n); // arc cosine of the vector dot product 518 } 519 function Round(n,d) { d = Math.pow(10,d); return Math.round(n*d)/d; } // round 'n' to 'd' decimals 520 function Deg2Rad(d) { return (d * Math.PI / 180.0); } 521 function Rad2Deg(r) { return (r * 180.0 / Math.PI); }