{"id":1319,"date":"2014-10-02T14:14:59","date_gmt":"2014-10-02T14:14:59","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=1319"},"modified":"2018-05-21T13:10:59","modified_gmt":"2018-05-21T13:10:59","slug":"why-dyalog-14-was-a-shear-delight","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2014\/10\/why-dyalog-14-was-a-shear-delight\/","title":{"rendered":"Why Dyalog &#8217;14 was a Shear Delight"},"content":{"rendered":"<p><a href=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot55.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1341\" src=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot55.png\" alt=\"rot55\" width=\"411\" height=\"175\" srcset=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot55.png 411w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot55-300x127.png 300w\" sizes=\"auto, (max-width: 411px) 100vw, 411px\" \/><\/a><\/p>\n<p>Recent versions of Microsoft Windows support touch screens, which of course means that applications can respond to events originating from touches. Microsoft calls these events &#8220;gestures&#8221;.<\/p>\n<p>Dyalog decided to add support for gestures to version 14.1 and so projects were planned, designs were designed, code was coded and, at <a href=\"http:\/\/www.dyalog.com\/user-meetings\/dyalog14.htm\">Dyalog &#8217;14<\/a> (<a href=\"https:\/\/twitter.com\/search?f=realtime&amp;q=%23dyalog14&amp;src=typd\">#Dyalog14<\/a>), a demonstration was demonstrated. The video of that demonstration is <a href=\"https:\/\/dyalog.tv\/Dyalog14\/?v=0y5-ophsdGA\" target=\"_blank\" rel=\"noopener\">here<\/a><\/p>\n<p>The three most interesting gestures are &#8220;pan&#8221;, &#8220;zoom&#8221; and &#8220;rotate&#8221;; I needed a good demo for the rotate gesture. I had an idea but was unsure how to implement it, so I decided to ask the team. Here&#8217;s the email I sent (any typos were included in the original email!):<\/p>\n<p><em>&#8220;Does any have code (or an algorithm, but code &#8216;d be better) to rotate a matrix by an arbitrary angle. The resulting matrix may then be larger than the original but will be filled with an appropriate value.<br \/>\nDoes the question makes sense? For the conference I want to demonstrate 14.1 support for Windows touch gestures, one of which is a &#8220;rotate&#8221; gesture, and I thought that a good demo would be to rotate a CD cover image when the gesture is detected. So I need to be able to rotate the RGB values that make up the image.&#8221;<\/em><\/p>\n<p>There were a number of helpful responses, mainly about using <a href=\"http:\/\/en.wikipedia.org\/wiki\/Rotation_matrix\" target=\"_blank\" rel=\"noopener\">rotation matrices<\/a>, but what intrigued me was Jay Foad&#8217;s almost throw away comment: <em>&#8220;It&#8217;s also possible to do a rotation with repeated shears&#8221;<\/em><\/p>\n<p>That looked interesting, so I had a bit of a Google and found an article on <em><a href=\"https:\/\/www.ocf.berkeley.edu\/~fricke\/projects\/israel\/paeth\/rotation_by_shearing.html\" target=\"_blank\" rel=\"noopener\">rotation by shearing<\/a><\/em> written by Tobin Fricke. The gist of this article is that shearing a matrix three times (first horizontally, then vertically and then again horizontally) effects a rotation. An interesting aspect of this (as compared to the rotation method) is that no information is lost. Every single pixel is moved and there is no loss of quality of the image.<\/p>\n<p>I&#8217;m no mathematician, but I could read my way though enough of that to realise that it would be trivial in APL. The only &#8220;real&#8221; code needed is to figure how much to shear each line in the matrix.<\/p>\n<p>Converting Fricke&#8217;s <code>\u03b1=-tan(\u0398\/2)<\/code> and <code>\u03d0=sin(\u0398)<\/code>, we get (using <code>\u237a<\/code> for <code>\u0398<\/code>):<\/p>\n<pre><code class=\"language-apl\">a\u2190-3\u25cb\u237a\u00f72\r\nb\u21901\u25cb\u237a<\/code><\/pre>\n<p>and so, for a given matrix, the amounts to shift are given by:<\/p>\n<pre><code class=\"language-apl\">\u230a\u237a\u00d7(\u2373\u2262\u2375)-0.5\u00d7\u2262\u2375<\/code><\/pre>\n<p>where <code>\u237a<\/code> is either <code>a<\/code> or <code>b<\/code>, depending on which shift we are doing.<\/p>\n<p>Wrapping this in an operator (where <code>\u237a\u237a<\/code> is either <code>\u233d<\/code> or <code>\u2296<\/code>):<\/p>\n<pre><code class=\"language-apl\">shear\u2190{\r\n(\u230a\u237a\u00d7(\u2373\u2262\u2375)-0.5\u00d7\u2262\u2375)\u237a\u237a \u2375\r\n}\r\n<\/code><\/pre>\n<p>Our three shears of matrix <code>\u2375<\/code>, of size <code>s<\/code>, can therefore be written as:<\/p>\n<pre><code class=\"language-apl\">a\u233dshear b\u2296shear a\u233dshear(3\u00d7s)\u2191(-2\u00d7s)\u2191\u2375\r\n<\/code><\/pre>\n<p>Note the resize and pad of the matrix before we start so that we don&#8217;t replicate the edges of the bitmap. The padding elements are zeros and display as black pixels. They have been removed from the images below for clarity.<\/p>\n<p>The final rotate function is:<\/p>\n<pre><code class=\"language-apl\">rotate\u2190{\r\nshear\u2190{(\u230a\u237a\u00d7(\u2373\u2262\u2375)-0.5\u00d7\u2262\u2375)\u237a\u237a \u2375}\r\na\u2190-3\u25cb\u237a\u00f72 \u22c4 b\u21901\u25cb\u237a \u22c4 s\u2190\u2374\u2375\r\na\u233dshear b\u2296shear a\u233dshear(3\u00d7s)\u2191(-2\u00d7s)\u2191\u2375\r\n}<\/code><\/pre>\n<p>Let&#8217;s look at a 45\u00b0 rotate of a bitmap called &#8220;jd&#8221;.<\/p>\n<pre><code class=\"language-apl\">jd.CBits\u2190(\u25cb.25)rotate jd.CBits<\/code><\/pre>\n<p>Prior to performing any shears our image is:<\/p>\n<p><a href=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot0.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1259\" src=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot0.png\" alt=\"rot0\" width=\"256\" height=\"257\" \/><\/a><\/p>\n<p>After the first shear it becomes:<\/p>\n<p><a href=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1260\" src=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot1.png\" alt=\"rot1\" width=\"252\" height=\"283\" \/><\/a><\/p>\n<p>After the second shear it is:<\/p>\n<p><a href=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1257\" src=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot2.png\" alt=\"rot2\" width=\"298\" height=\"280\" \/><\/a><\/p>\n<p>And after the third shear it is:<\/p>\n<p><a href=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-1274\" src=\"http:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot3-300x293.png\" alt=\"rot3\" width=\"399\" height=\"391\" srcset=\"https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot3-300x293.png 300w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot3-306x300.png 306w, https:\/\/www.dyalog.com\/blog\/wp-content\/uploads\/2014\/10\/rot3.png 399w\" sizes=\"auto, (max-width: 399px) 100vw, 399px\" \/><\/a><\/p>\n<p>All nicely rotated.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Recent versions of Microsoft Windows support touch screens, which of course means that applications can respond to events originating from touches. Microsoft calls these events &#8220;gestures&#8221;. Dyalog decided to add support for gestures to version 14.1 and so projects were &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2014\/10\/why-dyalog-14-was-a-shear-delight\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":8,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,8,21],"tags":[],"class_list":["post-1319","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-apl-language","category-dyalog-14"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1319","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/8"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=1319"}],"version-history":[{"count":31,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1319\/revisions"}],"predecessor-version":[{"id":5172,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1319\/revisions\/5172"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=1319"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=1319"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=1319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}