Voronoi: A solution to proximity based problems

In computational geometry, Voronoi diagram is a partitioning of a plane with n points into n convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. GeoVoronoi is an extension of Voronoi optimized for geo locations.

vor1

To dive deeper into Voronoi geometry, read chapter seven of Computational Geometry: Algorithms and Applications. Or maybe play with this cool demo.

If you're working on any proximity-based problem, Voronoi diagram can be a lot of help. In layman's language, Voronoi diagram divides a 2-D plane with n sites into n zones, one for each sites, such that any point inside the zone is nearer to the site that owns the zone as compared to any other sites. In the above Voronoi diagram, 'a' is a site and 'v(a)' is its zone.

In my particular use case, I've been creating a proximity based mobile app that needs to know which site is nearest to the device during each location update. The zone information provided by Voronoi diagram saves me from polling among distances from each site upon each location update. Now I just need to check which zone the device is currently inside of and would poll among the zones only if the device moves out of the current zone. This optimizes the process multiple folds.

I'm extending this Javascript implementation of Voronoi diagram. Although it works perfectly for a normal X-Y plane, it wouldn't quite fit in for geo locations. So, I've written a geo wrapper over it, namely, GeoVoronoi which basically does the following patch-work:

  1. Longitudes don't stay linear near the international date line. They discontinue and go like '..., 178, 179, -179, -178,...'. GeoVoronoi would take care of this.
  2. Auto-boxing super area of sites with optimal padding. (Bbox in code).
  3. Keeping latitude-longitudes sanitized in terms of range and decimal places.

Usage

Input an array of sites(latitude-longitudes) and a voronoi-graph will be returned to you. The information inside voronoi graph can be used to do calculations, to determine zones and even to draw the Voronoi diagram on a plane, Google Map, etc.

I've created an npm package for geovoronoi here. To install this package use the following command:
npm install geovoronoi

Above code will generate voronoi-graph data. This voronoiGraph object contains following three major objects and a key-value for execution time:

  1. cells: This contains information for all the polygons(zone) along with their owner sites. A polygon is represented by halfedges (called so as most of them are shared among two adjacent polygons). Each half-edge has start and end vertices called 'va' and 'vb' respectively. Set of start vertices of all half-edges will be all the vertices of the polygon. Information of cells is enough for basic calculations.
  2. edges: This contains information about start and end points of all the edges in the resulting Voronoi diagram.
  3. vertices: This contains information about all the vertices in the resulting Voronoi diagram.

Please refer to this README for the data inside cells.

If you found this post interesting go explore more about Voronoi. Leave a comment about your use case. You might also want to take a look at my post about Ray casting. It will help in determining whether a point lies inside a polygon or not.


A Rails Developer's impression of CoffeeScript - Part 2

We had a look at the basics of CoffeeScript in the previous post. In this tutorial, we'll see how it is supported in Rails and how can we use it. Ruby CoffeeScript is a ruby bridge to the CoffeeScript compiler. The coffee-script library will automatically choose the best JavaScript engine for our platform. The available engines are V8, Node.js, and JavaScriptCore.

To use CoffeeScript with Rails 3.0.x

We can use either of the two gems available:
- Barista – gem that provides CoffeeScript support for Rails and Rack apps
- BistroCar - another gem that serves up CoffeeScript from within our Rails application

The latest versions of Barista depends on the coffee-script gem. It auto-detects the available compilers on our system as there are several ways to install CoffeeScript. We can install via node.js as the official documentation suggests or else we can use the therubyracer gem and we won’t have to install anything else! therubyracer includes V8 (the fast Javascript engine from Google).

Finally the coffee-script gem depends on the coffee-script-source gem. This gem contains the CoffeeScript source code and it is synced with official releases.

RubyInside has a good tutorial for installing necessary gems and get CoffeeScript working in Rails projects. It also describes how to use CoffeeScript with jQuery.

Here is what we need to add to our Gemfile :

Next, we need to generate barista_config.rb file which is stored in config/initializers/ that contains a set of options to configure Barista options

The two basic settings for barista are the root and output_root configurations. The default directory where barista looks for your coffeescript files is the coffeescripts folder in your app directory which you need to manually create. We can change this default location by making changes in barista_config.rb.

Similarly, default location for compiled javascript files generated by Barista gem is the public/javascripts directory. Lets say, we want Barista to compile CoffeeScript files into public/javascripts/compiled, we’ll need to add this line to Barista configuration file :

CoffeeScript with JQuery

To use CoffeeScript with JQuery, the initial setup is as follows -

Lets start by writing the simplest JS statement in CoffeeScript



Generated JS -

Well, parenthesis for arguments are optional in CoffeeScript, so we can write

So far, so good.

Executing something on document.ready with Jquery

Doing it this way, the .bind call would executing too soon, before the document is ready and thus it doesn't do anything. Wrap it in a call to $(document).ready like this

Global functions

If we want to make a global function in coffeescript, we can explicitly assign it as a property of the global window object

Sample code to highlight(in red color) all required but empty fields, on clicking the form. Example -

We give 'required' class to all the required input text fields.

Generated JS -

CoffeeScript Demo (GitHub Repo)

This sample Rails application lets us create posts, each post can have multiple sections. It uses Ryan Bates's Nifty Generator Plugin to generate form layouts and basic skeleton for controllers and models.

Add_More_coffeescript

Clicking the “Add more” link lets us create more sections. This JavaScript functionality has been created using CoffeeScript.

If we clone the repo and run server.. notice the log -

On every request, Barista compiles the coffee files and generates equivalent JavaScript code. Every coffee file in app/coffeescript has an auto-generated corresponding file in public/javascript directory.

Other support

rack-coffee - Serves up coffeescript from rack middleware
After we've required 'rack/coffee', we put this in the Rails initializer config block:

coffee-haml-filter Custom haml filter for rendering CoffeeScript inside our Haml templates. Sample Code -


CoffeeScript in the wild - Is a comprehensive list of all projects that have adopted CoffeeScript.

Coffeebeans gives us inline CoffeeScript

Generated JavaScript -

Rails 3.1 and CoffeeScript

Rails 3.1 will have native CoffeeScript supports(via Sprockets 2). RubyInside has another good tutorial on how to start using CoffeeScript in Rails 3.1. This default can be turned off by commenting out the depedndencies in the generated Gemfile. If we want to write code in JS, we still can - just leave off the .coffee suffix from the filename. The application.js file is no longer shipping with .coffee added for the simple reason that it'll have no code. But if coffee is available, we'll be generating JS stubs for new controllers (like helpers) with the coffee extension on). Write .js files, like we were doing before. Be sure not to write coffeescript in .coffee files if we don't want to use coffeescript. By doing so, we will be using coffeescript. Instead we should only write javascript in .js files.


A Rails developer’s impression of CoffeeScript - Part 1

DHH has announced that Rails 3.1 will ship with CoffeeScript as default option for writing JavaScript.

All web apps use JavaScript (if you don’t, I don’t want to know you! ), and most Rails developers who are used to writing clean and pretty ruby code find it cumbersome to write JavaScript with all its curly braces and colons, (well, at least I did). Compared to that, CoffeeScript is wonderfully easy to understand and maintain. Lets hear it direct from the horse’s mouth -

  • CoffeeScript is neat language that provides an alternative syntax for writing JavaScript; the code compiles one-to-one into the equivalent JS, and there is no interpretation at runtime.
  • Its integration with existing JavaScript libraries is seamless (like jQuery, Facebook JS SDK, Google API etc)
  • Works wonderfully in browsers that support JavaScript and JavaScript platforms like node.js
  • The code generated by CoffeeScript is syntactically correct and passes through JSLint without warnings.

A lot of writing about coffee. Let's brew some -

Equivalent CoffeeScript -


It doesn't need to explicitly declare the variable 'square'. The function body starts after '->'. We don't need to use semicolons ; to terminate expressions. And we don't need an explicit return statement, the last expression evaluated is returned.

How easy that makes a developer’s life! Understandably, Coffeescript has found acceptance in a lot of big rails projects. It is used by Github, 37 signals and more..

Getting Started

  * Lets get it working first - Check out the installation
  * The command-line version of coffee is available as a Node.js utility. The core compiler however, does not depend on Node, and can be run in any JavaScript environment, or in the browser.
  * Check out - the TextMate bundle for CoffeeScript

Why Ruby/Rails devs would love it or The similarity with familiar Ruby/Rails syntax


Variable declaration and expressions
You don't need to use semicolons ; to terminate expressions, ending the line will do just as well, (although semicolons can still be used to fit multiple expressions onto a single line.) Also, no explicit variable declaration needed. Example -

Functions
Functions are defined by an optional list of parameters in parentheses, an arrow, and the function body. The empty function looks like this: -> .CoffeeScript uses significant whitespace to delimit blocks of code – very haml-like. Last evaluated expression is returned (no need explicitly 'return' values). Almost everything can be wrapped in an anonymous function and used as an expression. Example -

Default Arguments for functions
Functions may also have default values for arguments. We can override the default value by passing a non-null argument. You also have ruby-style string interpolation. Double-quoted strings can have interpolated values, using #{ ... }

Function Calling
You don't need to use parentheses to call a function if you're passing arguments. The function call would wrap till the end of line for arguments.

Significant Indendation
Instead of using curly braces { } to surround blocks of code in functions, if- statements, switch, and try/catch, use indentation.

Iterators
We can loop over arrays, ranges, hashes and objects using for operator in the postfix.

Other goodies

Single line conditionals
It provides you with Post fix if-else conditionals. It compiles to ternary operator when possible and closure wrapping otherwise.

Class inheritance using extends keyword
CoffeeScript gives a basic class structure,very much like ruby. It lets you add super class, assign prototype-properties and write the constructor.
Constructor functions begin with the name 'constructor'. You are provided with concise constructors. Rather than doing this.length = length for class constructors, you can simply use the @ shorthand for this, (@length, @breadth) -> with an empty method body would form our constructor.

Splats
Variable number of arguments get passed as an array in the last argument with '...'. Splats are used both for function definition as well as invocation.

Heredocs
You can use single-quotes (otherwise - triple-quotes) for multi-line strings, leading indentation common to all lines will be stripped. Example -

Literals in coffeescript for objects and arrays.
When each property is listed on its own line, the commas are optional. Objects may be created using indentation instead of explicit braces, similar to YAML.

Next Post will cover CoffeeScript in Rails 3 and Rails 3.1