That got me thinking. Julian Assange/Wikileaks has been branded as “dangerous”, “terroristic”, or merely presented as not-a-force-for-good by prominent politicans, pundits, including but not limited to:

• United States vice-president Joe Biden who described Assange as a “dangerous hi-tech terrorist”;
• Sarah Palin who thinks Assange should be “hunted down like Al Qaeda”, while other members of the Republican party called for the capital sentence against Wikileaks personel;
• Canadian Thomas Flanagan who thinks Julian Assange should be assassinated because “there is no good coming of [the publication of the leaked documents]“;
• James Richardson, who stated that Wikileaks “ought to leave international relations to those who understand it – at least to those who understand the value of a life”;
• Glenn Garvin who stated that Assange has “difficulty translating binary code into flesh and blood”.

With the kind of statements as the ones listed above, I thought we should have as well a “Wikileaks death map”, such as the “Afghanistan war death map” published by the Guardian, but this one related to deadly incident as a result of Wikileaks’ publication of leaked materials, and presented side-by-side with the “Afghanistan war death map”. So here it is:

Deadly incidents in Afghanistan resulting from the Afghanistan war (on principles of “war on terror”):

(Image source: The Guardian: Data for December of 2006 through end of 2009)

Deadly incidents in Afghanistan resulting from the publication of leaked documents by Wikileaks (on principles of transparency/accountability):

(Data source: here, here, since Wikileaks first published in December of 2006.)

Here is the thing: This is about Afghanistan here, but the fact is that you could use the map of any country and be unable to place a single dot on the Wikileaks version of the map. (It would be nonsense to blame Wikileaks for the assassination of two “Wikileaks-related senior human rights activists” in 2009 in Kenya, possibly linked to their work investigating “extrajudicial assassinations by the Kenyan Police”, Wikileaks has actually been awarded for redistributing the report.)

So, hum, next time someone is trying to convince you that Wikileaks is not a force for good, don’t let yourself all worked up by the rhetoric out there. Keep in mind principles of transparency and accountability are not readily embraced by those who thrive on secrecy, duplicity and unchecked powers, quite the opposite.

Note: Keep in mind the Guardian‘s map is based on leaked materials published by Wikileaks, which covers Afghanistan between 2004-2009. More deadly incidents beyond 2009 are not included, and neither are casualities from other U.S.-led wars.

I finally got around to do it. I also took the opportunity to put the code on Github, under a MIT license. Also, I modified the way Voronoi sites are passed to the Voronoi object, to minimize the amount of data duplication.

Since this new version takes care of annoying arithmetic finite precision issues, this allowed me to finally implement an idea I had for another demo page for Voronoi diagrams — the precision issues were causing my original implementation to often fail, somehow using fractional counterparts for the Voronoi sites caused the algorithm to often break because of the finite precision.

So here is another page demonstrating how to use the Voronoi object: Fancy tiling.

I found it works best with browsers having fast Javascript engine. I did not try it with Internet Explorer, I am curious to know how smooth the interface is with IE9 (which supports the canvas element natively), so if you do try it, please share here whether it’s fast enough for a fluid interface. Also, if you stumbled onto a pretty tiling of your own, share with all and paste the associated permalink here.

I plan to implement other modifications to my implementation of Fortune’s algorithm, particularly to get rid of choke points I have identified which should help improve performance significantly.

I needed a diff algorithm to efficiently generate compact string of opcodes of all the actions required to transform exactly the content of a “from” string into the content of a “to” string.

So here is a demo page of the algorithm:
FineDiff demo page

And here is the PHP code on github:
PHP-FineDiff.

finediff.php contains the PHP FineDiff class, other files are for the web pages to demo the FineDiff class.

But that’s not a very good way to do this if the text is to contain HTML tags, as you could end up damaging the document structure by unexpectedly replacing HTML markups instead of just plain text.

So I took the time to rewrite the code to traverse the DOM, inspect each text node to find the portion of text to highlight, and replacing it with the same portion of text, surrounded with <span class="highlight">...</span>. This is a safe way to do this since text nodes do not contain HTML tags.

However, I wasn’t happy with the result, as there were cases where the portions of text to highlight were spanning two or more HTML tags, in which case, the text nodes found when walking the DOM tree do not match the whole portion of text I was trying to highlight.

To illustrate the problem, take the following dummy text:

The quick brown fox jumped

over the lazy dog.

The quick brown fox jumped ^over the lazy dog.

The quick brown fox jumpeds over the lazy dog.

The quick brown fox jumped over the lazy dog.

The quick brown fox jumped over the lazy dog.

With this latest method, it isn’t possible to highlight all the instances of “jumped”, because in many instances, internally the text is not contiguous in a single DOM text node, as there are intervening HTML tags in the middle.

This is a caveat present in all the JavaScript “highlighter” algorithm I found, like this one, this one, and also this one.

Asked to highlight “jumped”, the above code would result in:

The quick brown fox jumped

over the lazy dog.

The quick brown fox jumped ^over the lazy dog.

The quick brown fox jumpeds over the lazy dog.

The quick brown fox jumped over the lazy dog.

The quick brown fox jumped over the lazy dog.

Although these might be suitable for many applications, it wasn’t in my particular application.

So I decided to write a piece of JavaScript code which would take care of highlighting portions of text regardless of intervening HTML tags. I also wanted a self-sufficient (does not depend on any particular JavaScript framework), single function to make it easy for others to reuse the code.

So here it is:

Non-minified version: dohighlight.js
Minified version: dohighlight-min.js

You are free yo use/modify the above code, as long as you preface the portion of code with, at the very least, a comment line which contains the URL to this blog entry. Preferably, I would appreciate that all the comment lines as seen in the above JavaScript files are kept along with the code.

Syntax

doHighlight(node, className, searchFor[, which]);

Arguments

• node – (mixed) A reference to the DOM node, or a string representing the id of a DOM node which contains the text to highlight.
• className – (string) The class name to assign to the portions of text to highlight.
• searchFor – (mixed) A string, or a RegExp object, which will be used in searching for portions of text to highlight.
• which – (integer, optional, default to 0) When searchFor is a RegExp, this specifies which subpattern to highlight.

Notes

• To keep the function as compact as possible, the arguments are not tested for validity. It is the programmer’s responsibility to feed the function with valid arguments.

Example

Highlight Reset

The quick brown fox jumped

over the lazy dog.

The quick brown fox jumped ^over the lazy dog.

The quick brown fox jumpeds over the lazy dog.

The quick brown fox jumped over the lazy dog.

The quick brown fox jumped over the lazy dog.

• The quick brown fox
• jumped
• over
• the lazy dog.

The JavaScript code for the above example:

(function(){
  var resetHighlight = function(){
    var elems = document.querySelectorAll('.highlight');
    var n = elems.length;
    while (n--){
      var e = elems[n];
      e.parentNode.replaceChild(e.childNodes[0], e);
      }
    };

  var e = document.querySelector('#highlightButton');
  if (!e) {return;}
  e.onclick = function(){
    resetHighlight();
    var e = document.querySelector('#textToHighlight');
    if (!e) {return;}
    var searchFor = new RegExp(e.value.replace(/\s+/g,'\\s+'), 'gi');
    doHighlight('test', 'highlight', searchFor);
    };

  e = document.querySelector('#resetButton');
  if (!e) {return;}
  e.onclick = resetHighlight;
})();

While I was working on it, I found out that such a tool — CableSearch — had already been released on Dec. 3rd by a group of reporters.

Oh well.

Anyways, I decided to keep going as I was almost finished, and on Dec. 9th, I worked my idea of a full-text search tool for the leaked cables publicly available on Wikileaks: cablegatesearch.net

Hope you find it useful.

I will continue to work on it, as I have a few more ideas which I think would improve browsing through the collection of leaked cables.

Jan 1st, 2011 update: Found another full-text search tool for the cables, KABELS. The more the merrier.

That would be Mr. Thomas Flanagan. Watch on Youtube

Tom Flanagan: “Well, I think Assange should be assassinated, actually <chuckles>. I think Obama should put out a contract and maybe use a drone or something. … I would not feel unhappy if Assange ‘disappeared’.”

Tom Flanagan is a political science teacher at the University of Calgary. He was formerly an adviser to current prime minister Stephen Harper.

Tom Flanagan: “I made a thoughtless comment that I have retracted with regret.”

What’s not to regret when you stoop to the level of terrorists?

I suspect though that Mr. Flanagan was speaking his mind, the only thoughtless part was to speak up his mind loudly on national television. He better should have expressed his mind secretly to a U.S. embassy. Oh wait…

In opposition to, and protest against Canadian fellow-countryman Mr. Tom Flanagan:

Wikileaks mirror (available since Dec. 5th), and a Full-text search tool for the leaked cables (available since Dec. 9th)

Raymond Hill
Canadian citizen

Dec. 7, 2010: Tom Flanagan threatened me over WikiLeaks comment, Toronto woman says, Globe and Mail. Tom Flanagan to a woman who complained to him via email re. his suggestion that of Assange should be assassinated: “Better be careful, we know where you live.” (Who is “we”?)

Dec. 6, 2010: Complaint filed over call to assassinate WikiLeaks founder, Vancouver Sun

Dec. 6, 2010: Just read over at the Guardian: “The US attorney general, speaking at a press conference in Washington, said: ‘The lives of people who work for the American people have been put at risk. The American people themselves have been put at risk by these actions that I believe are arrogant, misguided and ultimately not helpful in any way.’ ”

You might want to read this piece here, which makes a point that the U.S. government itself is much more a risk to the lives of people than Wikileaks is. The article conludes:

Civilian Body Count so Far:

WikiLeaks: approximately 0
America: approximately 873,000

Also, Assange didn’t call for the assassination of anybody, as opposed to, say, Canadian Tom Flanagan. But somehow we are suppose to believe he is a treat to the lives of people.

• Dec. 7, 2010: Open letter: To Julia Gillard, re Julian Assange, Australian Broadcast Corporation. Excellent open letter, which goes on to mention some of the extremists calling for the assassination of Julian Assange. Tom Flanagan didn’t make it to the succinct list though.
• Dec. 6, 2010: Live with the WikiLeakable world or shut down the net. It’s your choice, The Guardian
• Dec. 6, 2010: The lawless Wild West attacks WikiLeaks, Salon

In the summer of 2009, while looking for a generic way to create fancy tilings for this project, I became interested with Voronoi diagrams, and realized this was the solution to my problem.

Eventually I understood that the most efficient way to compute Voronoi diagrams was to implement Steven J. Fortune’s sweep line algorithm. However, I couldn’t find any ready to use Javascript implementation of his algorithm at the time.

Looking around, I stumbled upon and decided to port a C# implementation by Benjamin Dittes I found there.

However, once the port was completed, I realized there were unresolved issues with Benjamin Dittes’ implementation, specifically, the computed Voronoi diagram was left unfinished, with dangling Voronoi edges and open Voronoi cells. At the time, I tried to add the missing code, to find out there was a deeper issue with the code, which issue prevented me from properly “closing” the Voronoi diagram. (Note: I believe the problem is in VoronoiEdge.AddVertex() in FortuneVoronoi.cs: the vertex should be added in an orderly manner.)

Before I could pinpoint the exact fix in the code, I moved on to other things, and left my Javascript port attempt of Benjamin’s code unattended since then.

A few weeks ago, I decided to get back at work to create a fully working Javascript implementation of Fortune’s algorithm to generate Voronoi diagram, but this time I started from scratch, with my own ideas on how to implement Fortune’s algorithm. [Note: Meanwhile, two more Javascript implementations to compute Voronoi diagrams have become available on the net: Voronoi Tessellation by Nicolas Garcia Belmonte, and A JavaScript implementation of the planar ordinary Voronoi diagram by Greg Ross.]

So here is my personal Javascript implementation of Steven Fortune’s algorithm to generate Voronoi diagrams. I didn’t use Fortune’s suggested data structures (binary tree for the “beach line”, linked lists for the edges), this implementation relies only on Javascript arrays, but of course is based on the concepts underlying Steven Fortune’s very clever algorithm (sweep line, beach line, circle events, etc.)

The center piece of Fortune’s algorithm is the “beach line,” i.e. the “curve formed by the lowest parabolic arcs,” as stated in this excellent tutorial of Fortune’s algorithm. I myself refer to these “parabolic arcs” as “beach sections.” Each break in the beach line, that is, each transition between two distinct beach sections represents a Voronoi edge, shared by two Voronoi sites, and for which a start and end point must be found. A start and/or end point is defined for a Voronoi edge when a transition between two beach sections appears or disappears.

Steven J. Fortune suggested, and used a binary tree in his C implementation to represent the beach line. In Fortune’s binary tree, transitions between two beach sections are represented by “internal nodes” in his binary tree, beach sections themselves are represented by “leaf nodes.” The binary tree is theoretically the most efficient way to represent the beach line.

However, this implementation relies on a simple Javascript ordered array to maintain the beach line, and all items in the beach line array are beach section objects. I chose to use an ordered array over a binary tree to simplify this first implementation. In such an ordered array, the transitions between two beach sections are implicit, we do not need a dedicated data structure to represent them internally.

Using an ordered array, it is thus possible to use a binary search, so we still have the benefit of the binary tree, the ability of fast look-up of any particular beach section on the beach line.

There are two main disadvantages though of using an ordered array over a binary tree in Fortune’s algorithm:

1. Modifying the beach line means removing/adding elements in the array, which means memory movements, which is more costly than adding/removing nodes in a binary tree. However, most certainly the memory moves are ultimately done using machine code (Array.splice), whereas the managing of a binary tree isn’t done natively in Javascript [This is no longer true for Javascript engines supporting just-in-time compilation, so I might move to a binary tree structure in a near future...]
2. The other disadvantage, more serious, is the inability for Fortune’s circle events to keep a direct reference to their associated beach section, as is possible using a binary tree. Because of this, an extra look-up is required when a Fortune’s circle event needs to be processed, to find the associated beach section on the beach line. This is mitigated by the fact that a binary search is used to perform the look-up.

Given the disadvantages detailed above, it is useful to note that in typical circumstances, the number of beach sections in the array describing the beach line is relatively low. As an example, for 1,000 randomly generated Voronoi sites, I gathered that the beach line grows to an average of 75 beach sections at any time. The fact that the number of beach sections on the beach line is relatively low helps both the performance of the binary search look-ups (log₂(N) − 1), and the memory movements due to insertion/removal of beach sections in the array.

On my Core i5-660 computer, running Ubuntu Lucid Lynx, rough measurements (using Demo 1) showed that to compute a Voronoi diagram for 5,000 sites (rendering not included) required:

Chromium v6.*: 150-180 ms (impressive!)
Firefox 3.6.*: 1,500-1,600 ms
IE 8 within Virtualbox: 6,000-10,000 ms
Safari v5.* within Virtualbox: 500-1,000 ms
Google Chrome v6.* within Virtualbox: 350-450 ms

This page uses an extended version of the core version of the algorithm — less suitable for code reuse — allowing full control of the execution of the Fortune’s events queue, allowing examination of the beach line, and also useful as a tutorial for Fortune’s sweep line algorithm (it was also very useful as a debugging tool.)

The core version used on this blog post (rhill-voronoi-core.js/rhill-voronoi-core-min.js), is faster since it contains only the code to compute a Voronoi diagram, given a set of vertices. The rendering of the resulting Voronoi diagram is left to the user. A typical usage:

You are free to use or modify all or portion of rhill-voronoi-core.js or rhill-voronoi-core-min.js under the GNU General Public License MIT License.

Other interesting online Voronoi-related web pages:

• Steven Fortune‘s web page — somewhere in there is his original algorithm in C language.
• Shane O’Sullivan: A C++ port of Steven Fortune’s code. The site hosts a PDF document detailing Fortune’s algorithm: Lecture 16: Voronoi Diagrams and Fortune’s Algorithm.
• Voronoi Tessellation by Nicolas Garcia Belmonte — a faithful Javascript port of Steven Fortune’s C implementation.
• A JavaScript implementation of the planar ordinary Voronoi diagram by Greg Ross — a non-Fortune algorithm allowing incremental computation of a Voronoi diagram.
• Fortune’s Algorithm in C++ by Matt Brubeck, a C++ implementation.
• Voronoi Diagrams and a Day at the Beach by David Austin, an excellent tutorial on Steven Fortune’s algorithm.
• VoroGlide (Java-based).