How to draw an ellipse

Pretty much every drawing tool and library comes with an ellipse-drawing function, so you never even need to think about how it's done. Until, one day, you're the one writing the drawing tool.

Formulae and sample code abound for calculating the outline of an ellipse. The problem is when you try to draw a nice-looking ellipse, the edge needs to be smooth, and this means half-colouring some of the pixels at the edge.

The first thing is to remember that a pixel doesn't represent a point, it represents a square. So there are two things to calculate: for any given ideal euclidean point, whether that point is inside the ellipse; and for any given square, its "insideness", ie how much of that square is covered by the ellipse. So a pixel is drawn 100% opaque if it is completely inside the ellipse, and 100% transparent if it is completely outside. Otherwise, it is drawn with a transparency proportional to its insideness.

So, if all four corners of a pixel are "inside" the ellipse, consider the pixel is 100% covered by the ellipse. If all four corners are not "inside", consider the pixel 0% covered. Otherwise, subdivide the pixel into four sub-pixels, and calculate the insideness of each sub-pixel, recursively. The percent coverage for any given pixel is the average coverage for all its sub-pixels. Below a certain threshold, don't recurse; just use the values for the corner points.

To calculate whether a single point is inside the ellipse, use this function:

/**
 * determines whether a point p,q is inside an ellipse
 * specified by (x,y,a,b)
 *
 * returns 1 if inside, 0 if outside
 *
 * @param x x-coordinate of centre of ellipse
 * @param y y-coordinate of centre of ellipse
 * @param a horizonatal radius
 * @param b vertical radius
 * @param p x-coordinate of point to consider
 * @param q y-coordinate of point to consider
 */
insideEllipse = function(x, y, a, b, p, q) {
  var dx = (p - x) / a;
  var dy = (q - y) / b;
  var distance = dx * dx + dy * dy;
  return (distance < 1.0) ? 1 : 0;
};

To calculate the insideness of a square area, use this:

/**
 * determines what proportion of a square (p,q) - (p+side, q+side) is covered by this
 * ellipse. If side < threshold, returns an approximate result.
 *
 * returns: a value in the range [0.0, 1.0]
 *
 * @param p x-coordinate of point to consider
 * @param q y-coordinate of point to consider
 * @param side the length of the edge of the square to sample
 * @param threshold do not recurse if side is less than this value
 */
insideness = function(x, y, a, b, p, q, side, threshold) {
  var i1 = insideEllipse(x, y, a, b, p, q);
  var i2 = insideEllipse(x, y, a, b, p + side, q);
  var i3 = insideEllipse(x, y, a, b, p + side, q + side);
  var i4 = insideEllipse(x, y, a, b, p, q + side);
  var total = i1 + i2 + i3 + i4;
  if (total == 4 || total == 0 || side < threshold) {
    return total / 4.0;
  }

  side = side / 2;
  var j1 = insideness(x, y, a, b, p, q, side, threshold);
  var j2 = insideness(x, y, a, b, p + side, q, side, threshold);
  var j3 = insideness(x, y, a, b, p + side, q + side, side, threshold);
  var j4 = insideness(x, y, a, b, p, q + side, side, threshold);
  return (j1 + j2 + j3 + j4) / 4.0;
};

Enjoy.

Parisharing

If you live in Paris, or would like to visit Paris, you might be interested in Parisharing, a radical new authentic tourism concept. It's still new, and you can help by taking the relevant survey:

• Residents
• Tourists

From the site:

30 million people dream of visiting Paris, if only for a few days. 30 thousand who live in Paris dream of traveling elsewhere, if only for a few days.

PariSharing is the meeting of those dreams.

If you hope to visit Paris, this will be your chance to rent a real Parisian apartment at an unbeatable price while enjoying an authentic Parisian lifestyle.

If you live in Paris, this is your chance to increase your earnings and offer yourself a nicer or longer vacation.

There you have it - Parisharing will offer visitors an authentic and affordable experience of Paris, and at the same give residents of Paris an additional incentive to leave the city for vacation. Is that a win-win situation or what?

How Do You Find Me?

When you hit google's cache of a page it conveniently highlights all of your search terms. Some web sites have this neat trick of highlighting your search terms when you've come from a search, even though you're not in google any more. The "referer" (sic) http header gives them the necessary information. Thanks to the amazing technology presented in this article, you, too, can do the same thing and dazzle your visitors.

On top of that, if you're not using Google Analytics, you will surely want to know what search terms people are using to get to your site. Why not Google Analytics? Because They Know Too Much Already!

Here's a lump of java code you can stick into your web app for extracting google search term information. There are three important methods:

public String getSearchTerm(HttpServletRequest req) - return the URL-decoded search term. Given a referrer http://google.com/search?q=awesome+icon+editor, return "awesome icon editor". This String is what you would use for highlighting content on your page to give visitors the creepy feeling that you know what they're thinking.

public boolean isSearching(HttpServletRequest req) - true if getSearchTerm returns a non-empty String

public static Object[] google(String referrer) - returns an array of length 2; google()[0] is the same as getSearchTerm; google()[1] is the search results page number. This tells you how many times your user clicked "next" on google's search results before they got to your site. This is useful information - it tells you how desperately your user wants your app, and how irrelevant google considers your site. Yes, the truth hurts, but you need to know before you can do anything about it. I'm sorry. The page number comes from the "start" parameter. So, with this referrer string http://google.com/search?q=awesome+icon+editor&start=80, the page number would be 8.

If you're using Freemarker, you can bind this object to a global variable, so unless you abhor globalisation you will know directly within your template whether you're being googled.

So, the code. Free for private and commercial use. Don't be afraid to link back here. Enjoy.

ExternalSearchHelper.java

/*
  copyright conan dalton 2009, license http://creativecommons.org/licenses/by-sa/3.0/ 
*/
import org.apache.commons.lang.StringUtils;

import javax.servlet.http.HttpServletRequest;
import java.net.URLDecoder;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class ExternalSearchHelper {
  static final Pattern itsGoogle = Pattern.compile("http://[^/]*google[^/]+/.*[&\\?]q=([^&]+).*");
  static final Pattern itsGoogle2 = Pattern.compile("http://[^/]*google[^/]+/.*[&\\?]q=([^&]+).*&start=([^&]+).*");

  public String getSearchTerm(HttpServletRequest req) {
    String referrer = req.getHeader("Referer");
    if (referrer == null || referrer.length() == 0) {
      return "";
    }

    return (String) google(referrer)[0];
  }

  public boolean isSearching(HttpServletRequest req) {
    // re-implement this if you don't want to depend on apache-commons
    return StringUtils.isNotBlank(getSearchTerm(req)); 
  }

  public static Object[] google(String referrer) {
    Object[] result = new Object[2];
    if (referrer == null || referrer.length() == 0) {
      return result;
    }

    Matcher m2 = itsGoogle2.matcher(referrer);
    if (m2.matches()) {
      result[0] = decode(m2.group(1));
      result[1] = new Integer(Integer.parseInt(m2.group(2)) / 10);
      return result;
    }

    Matcher m = itsGoogle.matcher(referrer);
    if (m.matches()) {
      result[0] = decode(m.group(1));
      result[1] = 0;
    }

    System.out.println("search term " + result[0]);
    return result;
  }

  private static String decode(String s) {
    return URLDecoder.decode(s);
  }
}

On the Latest Intellij

I downloaded Intellij 8 the other day and as usual it was full of wonderful goodies:

• Freemarker support, at last - syntax colouring, and freemarker stacktrace navigation from the console: awesome! [UPDATE] and navigation between templates included with the #include directive
• Git support, at last!
• Better javascript syntax highlighting
• Hibernate: uses reverse-data-flow to find some strings which will become HQL queries, and highlights appropriately. Wow. I mean: wow, that must have been hard work, especially for something that isn't really all that essential ...
• Little "close" button on each tab (the way web browsers do it), so I don't have to right-click and choose "close tab" any more. This is great. One of those little details.
• Recognises associated source code when I update a dependency and its source - which I do a lot because some code for some projects is split into a separate project. Previously it would get all confused and not find the source any more.

I'm sure there's heaps more stuff, this is just what I noticed from the subset of features I use daily. Still missing:

• Option to silence "Open in new frame" dialog when opening a new project. This is really annoying: most annoying dialogs come with a "don't ask this again" option - but not this one. Go away, pesky dialog!

Anyway, bravo, jetbrains.

A Simple Javascript Slider

HTML5 might well have a native slider element (as part of Webforms 2.0); jQuery and MooTools have slider components, and the StackOverflow slider page points to these and other implementations.

In the spirit of NIH, I wrote my own. Rolling your own is one way to learn to appreciate a language; afterwards you get bored and start trusting the libraries. Here's a screenshot:

This slider invokes a callback function (onchange) when necessary, with the percentage value of the slider. It's up to you to translate that into dates, numbers, colours, or whatever it is you're sliding. Use like this:

<table>
  <tr>
    <th>
      Slider
    </th>

    <td id="foo_slider_min">
      <img src='/images/slider_min.png'>
    </td>
    
    <td valign="top" style="padding-top:5px;">
      <div id="foo_slider_bar" style="width:128px;background-image:url('/images/slider-bar.png');background-repeat:repeat-x;position:relative;">
         
        <div id="foo_slider_button" style="position:absolute;top:0;left:95%;">
          <img src="/images/slider-button.png" alt="editor pixel size controller"/>
        </div>
      </div>
    </td>

    <td id="foo_slider_max">
      <img src='/images/slider_max.png'>
    </td>

  </tr>
</table>

Initialise this with

var onFooChange = function(percent) {
    // update foo so it's at percent%
  }
  var sliderControl = new Slider("foo_slider", onFooChange);

If your slider's name (the 1st argument to new Slider()) is "foo_slider", it expects the following DOM elements to exist:

• foo_slider_bar - the object whose width is considered a value of 100%
• foo_slider_button - the object whose position relative to foo_slider_bar determines the value of the component
• foo_slider_min - an object which sets the slider to 0% when clicked
• foo_slider_max - an object which sets the slider to 100% when clicked

Here's the actual Slider code, use as you please -

function Slider(name, onchange) {
  var sliderBar = $(name + '_bar');
  var sliderButton = $(name + '_button');
  var sliderMin = $(name + '_min');
  var sliderMax = $(name + '_max');
  var min = 0;
  var self = this;

  var max = function() {
    return parseInt(sliderBar.style.width) - 2;
  };

  var setButtonPosition = function(px) {
    if (px > max()) {
      px = max();
    } else if (px < min) {
      px = min;
    }
    sliderButton.style.left = "" + (px - 8) + "px";
    onchange(px / max());
  };

  sliderBar.onmousedown = function(event) {
    document.onmousedown = returnFalse;

    offsets(event, sliderBar, function(y, x) {
      setButtonPosition(x);
    });

    document.onmousemove = function(event2) {
      offsets(event2, sliderBar, function(y, x) {
        setButtonPosition(x);
      });
    }

    document.onmouseup = cancelMouse;
  };

  sliderMin.onclick = function() {
    self.resetTo(0);
  };

  sliderMax.onclick = function() {
    self.resetTo(1);
  };

  this.resetTo = function(proportion) {
    setButtonPosition(proportion * max());
  }
}

Objects in Javascript

As a consequence of building iconfu.com, I've used more javascript in the past four months than in all the previous ten years combined. Javascript is not difficult, but its superficial similarities with java can be misleading for someone, such as I, coming from that language. Javascript is also, surprisingly, a respectable language, tarnished only by browser incompatibilities and buggy implementations (I'm thinking of one browser implementation in particular).

Here are the three worst stumbling blocks I faced on the slow path of figuring out how objects work in javascript: (1) what does "this" refer to? (2) how to write a constructor, and (3) how to define functions on objects.

If you're just scripting mouse events on a web page, you won't need much of this, but it's handy if you're doing anything serious with javascript (like, writing an image editor, ahem).

1. "this" refers to the object on which the function was called, not necessarily the place where the function was defined

Unlike java, javascript lets you copy methods about from object to object. So, suppose you have

var Truck = {
  fuel : 100,

  drive: function(km) {
    this.fuel = this.fuel - km;
  }
}

You can legitimately write

var Car = {
  fuel: 100
};

Car.drive = Truck.drive;

And then,

Car.drive(10);
alert(Car.fuel); // alerts 90

The "this" reference in the drive function references the callee's object, in this case Car, even though "this" originally referred to Truck.

"this" can be a source of much grief when setting up event listeners on objects. Suppose you want to install an onclick handler on a DOM element that allows your user interact with your vehicle, thus:

<a id='drive_truck'>drive the truck!</a>

and

var Truck = {
  // same as before, plus

  init : function() {
    document.getElementById('drive_truck').onclick = function(event) {
      // this.drive();  // FAIL: "this" is the span element, not the Truck object
      Truck.drive(); // this works, but it's ugly!
      someOtherStuff();
    };
  }
}

Truck.init();

the moral of the story: this inside an event handler function refers to the DOM element on which the event was fired - NOT the place where the function was defined. Fortunately, there are better ways to declare objects so that this ugliness can be avoided.

2. Two ways of creating objects: direct declaration (hash), or via constructor

The Truck example above shows a simple, direct way of creating objects, and it's common to do this all over the place in javascript. Mostly, it's the right thing to do, if you want something that's similar to a HashMap in java.

But, javascript also has constructors, and the funny thing about a javascript constructor is that it looks just like an ordinary function.

function Truck() {
  this.fuel = 100;

  this.drive = function(km) {
    this.fuel = this.fuel - km;
  }

  var self = this;

  document.getElementById('drive_truck').onclick = function(event) {
    // this.drive();  // FAIL: "this" is the span element, not the Truck object
    self.drive(); // this works, but you need the "self" local variable
    someOtherStuff();
  };
}

var myTruck = new Truck();
myTruck.drive(60);
alert(myTruck.fuel); // alerts 40

The Truck() function is, in fact, the Truck constructor. When you call new Truck(), instead of just calling Truck(), the "this" keyword within the function references a new object, for which this instanceof Truck returns true.

The difference between this approach and the previous one is that now you have a typed object, and you can have multiple instances of the same type of object.

3. Two ways of defining functions on objects: in constructor, or via prototype

So there are a few ways of associating functions with objects: you can declare them in the constructor, as we did above, or you can just add them later, as we did with the "Car" example. A problem arises with the constructor method if you define functions on your objects within the constructor: each object instance you create will have its own unique instance of each function as well. This can potentially introduce memory issues if you're creating a lot of objects.

The prototype approach eliminates this issue. Every object has an associated "prototype" object, to which you can add properties. Truck.prototype is just another object, but one treated with special respect by all Truck objects.

function Truck() {
  this.fuel = 100;

  var self = this;

  document.getElementById('drive_truck').onclick = function(event) {
    // this.drive();  // FAIL: "this" is the span element, not the Truck object
    self.drive(); // this works, but you need the "self" local variable
    someOtherStuff();
  };
}

Truck.prototype.drive = function(km) {
  this.fuel = this.fuel - km;
}

var myTruck = new Truck();
myTruck.drive(60);
alert(myTruck.fuel); // alerts 40, same as before

When the javascript interpreter searches a Truck instance for a "drive" property and finds nothing, it will consult "Truck.prototype" and see if there's anything appropriate there. If there is, the interpreter behaves as if that property were originally defined on the Truck instance itself. So the "this" reference remains intact for all properties inherited from the object's prototype.

Don't confuse the "prototype" concept with the "prototype.js" library. Javascript is a "prototype-based" object-oriented language, unlike java, which is a "class-based" object-oriented language. The prototype.js library relies heavily on the prototype feature of javascript, that's all.

HTH, let me know how it works for you ...

Do You Really Want Analytics?

Kontra's article on Google, linking Android and Youtube via video search, speech recognition and phoneme harvesting, made a lot of sense, and I realised there's even more cleverness in that whole google product suite. I have Google Analytics on this site, and enjoy watching my bounce rate bounce and my visitors jump up and down and pages per visit and time on site and all this statistical goodness generally so much that I risk carpal tunnel from continuously hitting the refresh button on my permanently-open multiple analytics tabs in firefox.

I don't know why Analytics is free, but here's a possible reason: when google sends a visitor to your site from a search result, the only way they can judge the quality of that result (the relevance of your site to the search query), without analytics, is whether and how soon the user clicks on another result for the same search. Now that you have analytics installed, they have much richer and deeper information: how long does the user stay on your site, how many and which pages to they visit? Having this information allows them decide whether that particular result was in fact a "good" hit.

I have no idea if google correlates search data with analytics data. But the point is, they have the data. And if I were google, I would do it. Wouldn't you? It's not necessarily a Bad Thing, but it's nice to know what you're paying for when it's free.