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:
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.
On September 2010, I posted about my implementation of Fortune’s algorithm to compute Voronoi diagrams. There were some issues related to finite arithmetic precision, and I could see no way to fix this once and for all other then by using a binary tree structure rather than a plain array to hold the beachline.
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.
I needed JavaScript code to highlight portions of text on a web page. At first I went with the quick and dirty, naive approach of using regular expressions to find a portion of text, and replacing it with the same portion of text, surrounded with <span class="highlight">...</span>.
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:
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:
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.
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.
(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;
})();
Shortly after I decided to support Wikileaks by joining the mass-mirroring movement on Dec. 5th, I decided to work on a full-text search tool for the Cablegate’s cables.
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: “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:
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.
Update (2011-05-20): The source code has been updated since this entry was posted. Refer now to Github for the latest version of the Javascript code which implements Fortune’s algorithm to compute Voronoi diagrams.
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.)
or
sites randomly, or
You should see a Voronoi diagram here if Javascript is enabled in your browser, and if your browser supports the HTML5 <canvas> tag.
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:
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...]
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 (log2(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:
var vertices = [{x:300,y:300}, {x:100,y:100}, {x:200,y:500}, {x:250,y:450}];
var bbox = {xl:0, xr:800, yt:0, yb:600};
var voronoi = new Voronoi();
voronoi.setSites(vertices);
var result = voronoi.compute(bbox); // render, further analyze, etc. // . . . // modify one site and re-compute
var sites = voronoi.getSites();
sites[0].x = 310;
sites[0].y = 290;
result = voronoi.compute(bbox); // render, further analyze, etc.
