Teleranek

I’ve udpated my sketch recognition algorithm, so it doesn’t load 30 minutes in the browser and is actually usable. First load for slow connections is a bit longer though.
The update was possible by usage of browser’s Indexed Database and some other stuff. I should’ve thought about it 4 years ago… Now this app looks outdated. Even some big corporations managed to make their own recognition web apps during that time -_-

PROBABLY DOESN’T WORK IN FIREFOX – it is because this app is super-old and I’d have to update CSS stuff. Don’t have time for this.

http://teleranek.org/sketchenhancer

Today’s 200th aniversary of Goerge Boole‘s birth, so this is a post about polygon clipping – boolean operations on polygons.
Most popular (and quite simple and fast) algorithm for this task is Greiner-Hormann. Unfortunately, as wikipedia says, it has 1 big drawback – cannot handle shapes with common edges. So XOR boolean operation won’t work. And we won’t be able to clip following “rectangles” (AND operation in this example):

[[]]→[[]]

Original Greiner-Hormann consists of 3 phases:

1. Compute intersections and add them to polygon
2. Marking intersections as “entering” or “exiting”
3. Final traversal and generating new polygons

The improved algorithm involves just adding additional phase of algorithm, just after the 1st one:
1.5 disabling “bad” intersections

Of course all intersections shouldn’t double themselves, so before adding intersections to polygon you should remove duplicate intersections. Doubling intersections are esp. possible when computing bezier intersections using traditional bezier clipping or computing intersections via approximation of bezier curves with polygons – the approximation leads to finding too many intersections for almost collinear curves.

Disabling bad intersections should mark intersections as “bad” and then they should be ignored in further steps of an algorithm.

The following pseudocode explains disabling bad intersections algorithm:

1. Do this for each intersection of current polygon in intersections:
   compute 2 boolean properties in current intersection: previousInside and nextInside. These properties determine whether the edge that is before the intersection point and the edge that is after the intersection point lies inside the second polygon (not current). In practice, we will be checking whether the point in the middle of the next and previous edge is inside second polygon, using some PIP-check algorithm, for example winding or odd-even algorithm.Important remark: if previous or next edge is collinear with corresponding edge in the second polygon, we mark it always as inside, or always as outside. (we could also mark it as “collinear” and then during second phase use some advanced heuristic how to treat collinear edges, but I won’t cover that method in this article, maybe later…).
2. Now traverse polygon. If we meet an intersection, and when intersection.nextInside == intersection.prevInside then disable this intersection

Remark: To apply this algorithm to curves, we can treat each curve segment as polygon segment. We just have to change the collinearity check to support curves, and the PIP check algorithm should be changed accordingly (e.g. check insideness through bezier subdivision).

As you can see, this simple change repairs Greiner-Hormann and there’s no need for perturbing vertices, as suggested in the original paper and on Wikipedia. Perturbing could generate random results in some cases.

Very useless post.

I’ve ported duktape javascript engine to javascript (using emscripten). No js interface for it, so you gotta call methods like this:

var result = Module.ccall('functionName' /*name of C function*/,
'number|string' /*return type*/,
['number|string',...]/*arg types*/, [666] /*args*/);


The API documentation is available at duktype site.

DEMO

source: dux.js

This can be used when eval is forbidden, or when we want to analyse js execution more closely.

Recently I wanted to display a number of week in a month. At first I wanted to get the formula from google instead of thinking, but there was no such formula. Also, I’ve found a lengthy discussion and only some indian guy gave the formula (which was incorrect of course:D)

Suppose that November the 1st is Thursday. Then for example, November 2nd is a 1st week of November, November 16th is a 3rd week, 30th is 5th week (basing on a fact that Monday starts the week)
Here’s the table that illustrates it:

?How to get the week number?

~~( ( m - w + 6 ) / 7 )

where m is an integer, a month day, 0 or 1-based
w is an integer, a week day, 0 or 1-based (e.g. Monday = 1, Thursday = 4)

Double bitwise negation is just a conversion to integer, you can use floor if you don’t care about speed (I guess that’s the case in times of virtual machine driven emulators and regex-based [greets angular;) ] js frameworks).

I’ll rebelliously leave it without a proof.

Recently I stumbled upon a challenge on challengepost.com – “20 lines of JavaScript”. The goal was to write a 20 line JS code that does something that can make the challenge judges vote for you. I thought the best idea would be to treat this challenge like a good ol’ demoscene compo. I’ve already had a good effect – the flower fractals. Unfortunately, after porting it to JavaScript it was 11 KBytes :( and 383 lines of code, not always shorter than the required 80 chars (or maybe even more, but I don’t remember where I put the first version). I used PIXI, great 2D javascript library because it uses several enhancements for JS canvas (it also supports WebGL, but WebGL isn’t really a vector-like drawing thing, the lines are aliased and poor quality, to obtain better quality I’d need to use textures and stuff, I thought it would be too complicated for 20 lines of code).

OK, so I’ve got 383 lines and 11 kilobytes. As we all know, 20 lines of 80 char code is 1600 bytes, so there’s way to go… I checked with google closure compiler, how I could squish that – after compressing, it was about 5 kilos. Still too much. After hours of merging functions, deleting smooth line bezier-based rendering, reusing some vars, it went down to about 3 kilos.

I started to think that its impossible to do, unless some miracle happens.

Then I stumbled upon this great method of utilising somehow buggy behaviour of browsers – treating PNG files like HTML, when compressed PNG data resembles HTML data. After changing the JS to one big eval(…) function and compressing it to PNG I went down to 1600 bytes. Well, exactly 1595. Changing some things inside eval and making the code larger allowed PNG to compress it enough. So there’s this curiosity – PNG JavaScript: 1600BYTES

This was of course no-go, because it wasn’t really javascript – it was png, and I it would be really really hard to intoduce line breaks inside zipped binary data. Also, it’s very ugly, you can see some errors appearing when running this code – some PNG IHDR data is displayed for a short period of time. I had to come up with something else. But how to squish the code better than the zip algorithm itself?

Then I had a moment of enlightning – it’s 20 lines of 80 characters challenge, not 1600 bytes challenge. How about UTF-16? I could write 2 bytes inside 1 UTF16 character.

It worked! Excited, I searched on google if anyone else did it – of course someone already came up with that idea ;/ And the idea was better because the decoder is like:
eval(unescape(escape('SOME STRING').replace(/uD./g,'')))

And mine was much longer and 2 lines:
function(s){A=[];for(i=0;i<s.length;i++){c=s.charCodeAt(i);A.push(c&255);
c>>8?A.push(c>>8):c;}return String.fromCharCode.apply(String,A)}("SOME STRING");

But my method used a bit different technique, so I could use normal letters and fit some ASCII art inside the code, not only some strange chinese letters.

OK, so after compiling with google closure, making big eval and changing to UTF-16, the code looks like this:

And can be seen on the challengepost’s winners’ ( ?° ?? ?°)  gallery:
http://challengepost.com/software/20-lines-of-green

or here
or JSFiddle: http://jsfiddle.net/to267224/tbgad7uz/

ps. I will enhance this post later maybe, to provide some missing info on technical things and add some images, cause there’s too much unformatted text ; )

When working on the android recognition app, I’ve also made version in JavaScript. Its around 60 megabytes site, so its quite unusable. And it loads so long that you can start doubting that it’s going to load at all.
To see it, better turn off AdBlock (it has a bug which prevents some sources from loading) and use chrome.
To make it harder and less usable (and lighter for my dropbox), to see this site you must first go to my experimental domain timmott-twerten.com, click and type “drawings”:
. This isn’t user friendly at all, so if you type something else in the box, or delete a letter, then the site will close itself and you will loose time that you wasted waiting for it.

It could be much more compact in flash/actionscript, but I wanted to check how fast is JS. It appears to be pretty fast ; )

The “save” button

… uploads your creation to imgur.

It is hosted on my dropbox, so when the transfer is exhausted, it won’t shutdown my blog ; )

ps. the javascript isn’t compressed or uglified, so you can see how it is all made.