Mercator projection routines for OpenStreetMaps.

So here’s a simple class which I cobbled together that converts to and from Mercator projected coordinates. The data stored in our database here at work is projected into Mercator coordinates, with the results stored apparently in meters.

I cobbled it together from the OpenStreetMap Wiki discussion on Mercator projections, and the complete class is below.

/**
 * Mercator projection routines, as used by OSM in their internal database.
 * Data stored in OSM is stored as points in X and Y, in meters projected
 * from a Mercator projected map. This allows conversion to and from those
 * points into lat/lng.
 * 
 * @author woody
 *
 */
public class Mercator
{
    final private static double R_MAJOR = 6378137.0;
    final private static double R_MINOR = 6378137.0;
//    final private static double R_MINOR = 6356752.3142;
 
    public static double[] toMerc(double x, double y) 
    {
        return new double[] {toMercX(x), toMercY(y)};
    }
 
    private static double toMercX(double lon) 
    {
        return R_MAJOR * Math.toRadians(lon);
    }
 
    private static double toMercY(double lat) 
    {
        if (lat > 89.5) {
            lat = 89.5;
        }
        if (lat < -89.5) {
            lat = -89.5;
        }
        double temp = R_MINOR / R_MAJOR;
        double es = 1.0 - (temp * temp);
        double eccent = Math.sqrt(es);
        double phi = Math.toRadians(lat);
        double sinphi = Math.sin(phi);
        double con = eccent * sinphi;
        double com = 0.5 * eccent;
        con = Math.pow(((1.0-con)/(1.0+con)), com);
        double ts = Math.tan(0.5 * ((Math.PI*0.5) - phi))/con;
        double y = 0 - R_MAJOR * Math.log(ts);
        return y;
    }
    
    public static double[] fromMerc(double x, double y)
    {
    	return new double[] { fromMercX(x), fromMercY(y) };
    }

	private static double fromMercY(double y)
	{
		double temp = R_MINOR / R_MAJOR;
		double e = Math.sqrt(1.0 - (temp * temp));
		return Math.toDegrees(phi2(Math.exp(-y/R_MAJOR),e));
	}
	
	private static double phi2(double ts, double e)
	{
		int N_ITER=15;
		double HALFPI=Math.PI/2;
 
		double TOL=0.0000000001;
		double eccnth, phi, con, dphi;
		int i;
		eccnth = .5 * e;
		phi = HALFPI - 2. * Math.atan (ts);
		i = N_ITER;
		do 
		{
			con = e * Math.sin (phi);
			dphi = HALFPI - 2. * Math.atan (ts * Math.pow((1. - con) / (1. + con), eccnth)) - phi;
			phi += dphi;
 
		} 
		while ( Math.abs(dphi)>TOL && (0 != --i));
		return phi;
	}

	private static double fromMercX(double x)
	{
		return Math.toDegrees(x / R_MAJOR);
	}
}

Here’s the funny thing. While on the talk page they discuss using a Mercator projection using values for an elliptical Earth, it turns out that the projected data actually uses a spherical projection. Thus, the two values for R_MINOR, with the elliptical solution commented out.

Feh. Time to start a discussion on the OpenStreetMaps Wiki.

The lowly string concatenation operator.

So the other day I encountered the following code. (I’ve rewritten this to protect the innocent.)

        HashMap<String,String> map = ...;

        for (int i = 0; i < 20; ++i) {
            if (check(map.get("label" + i))) break;
            
            String thing = map.get("thing" + i);
            String other = map.get("other" + i);
            
            doOperation(thing,other);
        }

Now for most applications, this is perfectly fine. I like idioms which are clear, even if they are slightly more computationally expensive. However, for a high performance application, it’s surprising how much stuff is going on behind the rather innocuous statement map.get(“label” + i);.

According to the Java spec, string concatenation is a shortcut for using a StringBuilder class. So map.get(“label” + i) becomes:

    StringBuilder tmp = new StringBuffer();
    tmp.append("label");
    tmp.append(i);
    map.get(tmp.toString());

And the append(int i) call is translated into a call to Integer.toString():

    StringBuilder tmp = new StringBuffer();
    tmp.append("label");
    String tmp2 = Integer.toString(i);
    tmp.append(tmp2);
    map.get(tmp.toString());

But wait, it gets worse! The StringBuilder.append() routine has to (a) check to see if there is enough buffer space allocated to store the string, growing the array (and copying the contents using System.arraycopy() to copy the memory across if not), and (b) use System.arraycopy() to copy the contents at the end of the buffer.

So each tmp.append() call involves a call to System.arraycopy() and an array length compare.

Then the tmp.toString() call allocates another buffer, copying the internal StringBuilder copy into the string buffer. (The internal source for String is permitted to simply copy a reference to the internal array in StringBuilder over rather than copying the bytes, but it doesn’t appear to do this.)

And I haven’t even gotten started!

Then we pass tmp to the map.get() method, which does a lookup, calling into the string’s hashCode() and equals() call. And because we have a brand-new string, hashCode() has to iterate through the entire array of characters, doing a math operation on each character, accumulating the results into a hash code.

Every time we go through this routine.

The answer, of course, if you’re writing a high performance application, is not to repeatedly do the same thing over and over again, especially if you can store away the results in memory.

In our above case, it would be easy enough to pre-populate an array of strings. Thus:

        /* Do this initialization once */
        String[] labels = new String[20];
        String[] things = new String[20];
        String[] others = new String[20];
        for (int i = 0; i < 20; ++i) {
            labels[i] = "label" + i;
            things[i] = "label" + i;
            others[i] = "label" + i;
        }

This pre-populates an array of strings with the labels we’ll be checking against. Then:

        
        /* Then do this a lot */
        for (int i = 0; i < 20; ++i) {
            if (check(map.get(labels[i]))) break;
            
            String thing = map.get(things[i]);
            String other = map.get(others[i]);
            
            doOperation(thing,other);
        }

Now each time we pass through the loop, instead of creating a StringBuilder object, allocating two character arrays (or more, if our key string is too big to fit in the StringBuilder’s default buffer) for each call to get() above, which winds up allocating 60 StringBuilder objects and 120 arrays, along with 60 calls to hashMap() each time through, instead we move those internal allocations into an initializer.

And each time we go through our loop, we’ve replaced 60 StringBuilder allocations and 120 array allocations with 60 array lookups–which is a hell of a lot faster.

Nondeterministic Maven

Understanding Maven Dependency Mediation (Part 1)

The important thing is the version number. It is stated “as is” without any extra additions (I’ll come back to this in a follow-up post). If you define version numbers in this syntax, Maven treats it as a recommended version. So what you’re actually doing is to tell Maven “I would prefer V1.2.11 of Log4J, but hey, I can live with any other version, too”.

This represents the biggest problem I have with Maven. It just feels non-deterministic to me. In solving one problem (“how can we integrate against a large number of jar files from a centralized location and administrate that repository”), we’ve introduced fragility in the resulting build product–we’re not entirely sure what jar files may be loaded and used to build our product.

Now of course this wouldn’t matter if jar files rigorously adhered to a proper API design methodology: proper versioning announcements (like the old Macintosh “Gestalt” manager) or guaranteed a proper and steady evolution of the API calls (similar to what Microsoft does with it’s COM interfaces does with things like IClassFactory and IClassFactory2), along with proper abstraction of the interfaces into higher level operations. Then it wouldn’t matter if you used version 1.0, 1.1 or 8.5 of a particular jar file. And if the API is designed with the principle of Graceful Degradation in mind, it wouldn’t even really matter if you found yourself using version 0.9.

But all this depends on proper documentation, proper design, and knowing the design patterns used by API developers to guarantee that your code will work regardless of what version of the API you’re calling–and when there is an API break, that break is properly announced in a major revision change and how the break will affect you in their documentation set.

But many jar file developers working on smaller projects (especially internal corporate projects) don’t do this–which is why sometimes you can find your code failing as you switch from version 1.1.4 (build 16) and version 1.1.4 (build 18).

Worse, this problem is compounded by the literally dozens of jar files that seem to be sucked in by things like Apache Commons and the Spring framework. If all the moving parts were designed correctly, again this wouldn’t be a problem. But how many people building APIs for common jar files even have any experience designing properly working, properly tested and properly supported APIs? And how many of the potentially thousands of possible combinations are even tested?

It just feels fragile to me.

And when you’re talking about the final build product of your team, after countless months of work trying to get your product solid and stable, fragile is bad.

Answering the question “what environment variables are available on the iPhone”

Just wrote a simple program to use NSProcessInfo to dump the environment variables on my iPhone. And I found the iPhone running my app standalone predefines the following environment variables:

SHELL = /bin/sh
CFFIXED_USER_HOME = /private/var/mobile/Applications/[UUID]
PATH = /usr/bin:/bin:/user/sbin:/sbin
TMPDIR = /private/var/mobile/Applications/[UUID]/tmp
__CF_USER_TEXT_ENCODING = 0x1F5:0:0
USER = mobile
LOGNAME = mobile
HOME = /private/var/mobile/Applications/[UUID]

The [UUID] is the UUID for your application, to differentiate the directory for your application from the directory used by other applications.


I find it interesting because it means that if you have some Unix C code that attempts (for example) to find the location of a file without using the various search methods available in iOS Cocoa, you can do it. For example, you can change the working directory to the documents folder by writing:

chdir(getenv("HOME"));
chdir("Documents");

(The standard iPhone directories are documented here: The Application Runtime Environment, under “The File System”.)

That can be quite useful…

Just look at the hardware specs.

Gizmodo is running a piece: Why Nobody Can Match the iPad’s Price

They have several theories. First, they theorize that because Apple sells most of their units through their own retail outlets, Apple can sell for a lower margin. But then, those retail outlets are not cheap. Then they theorize that Apple controls the hardware and the software–but then chalk it to Apple being willing to take lower profit margins on the pieces of the components.

But no-one looks at the design of the iOS operating system.

Apple created an operating system that is quite usable without multitasking, with an API which encourages fast switching applications in and out of memory. Because they don’t encourage the use of interpreted languages, and because they make heavy integrated use of the on-board GPU, they don’t need as much computing power to run most typical applications. The API also encourages the use of callbacks in a single-threaded event loop, which allows quickly idling the CPU when needed. And the OS runs in a very small memory footprint.

What this means is that the Apple iPad can run very well with very few resources: the Apple iPad uses only 256mb of RAM (as opposed to the Motorola Xoom’s 1gb of RAM–and God help you if you try to run Windows in that memory footprint), and the base model ships with only 16gb of flash memory: the same amount of flash in a cheap keyring flash drive.

Because Apple controls the software and because they control the hardware, they can also use a more integrated approach to reducing the part count in their iPads: my guess is that they are perhaps even looking at putting the RAM into the same wafer as the Apple A4 CPU. Never underestimate the cost savings of reducing chip count, as Steve Wozniak knew. Each chip that has to be mounted is an additional cost during design and manufacturing, and an additional chip that consumes energy and releases heat.

Apple’s iPad hardware is perfect for Apple’s iOS operating system and development environment. But if you were to try to run Android or Windows on a similar memory footprint, you’d have something that is sluggish and slow–Windows wants to run multiple processes and Android wants to kick off threads like crazy, which explains the hiccups you see when you try to run either on a Netbook computer.

For someone to compete with Apple, they would need to design an operating system which makes the compromises necessary to run on an inexpensive operating system–including enforcing development policies (such as no multi-process multi-tasking) that allow those compromises. That would allow them to reduce the chip count, memory requirements and CPU requirements that would allow them to create a much more inexpensive motherboard and reduce the battery size while maintaining battery longevity.

And unfortunately there is no-one currently out there who even sees the problem, much less is striving to find the solution to these problems.

If I were Google, I’d hire some CPU people and some CPU fabrication time, and figure out how to put the Davlik instruction set on a chip. Then I’d license the CPU design to anyone who wants to build a low power, but fast, Android phone.

25 Years Ago Today

NASA remembers the Challenger disaster 25 years later

… Today, NASA marked the 25th anniversary of the Challenger disaster which ended the lives of seven astronauts including the first teacher in space, Christa McAuliffe, due to a midair explosion 76 seconds into its flight. In honor of the heroes of STS-51-L, a memorial was dedicated in the Arlington National Cemetery where some remains of the crew members were buried. …

Fixed e-mail

So I broke the outgoing e-mail for this blog.

And it was interesting how I did it: I broke outgoing e-mail by, um, well, changing to Google’s GMail. The problem is LunarPages (which hosts this account) blocks outgoing SMTP ports to allow the blog to send e-mail out to GMail. So by reverting back to LunarPages for e-mail hosting fixed the problem.

I don’t know what came over me, switching to GMail…

Scroll FlowCover to a specified panel.

I thought for some reason this code was in FlowCover. It’s not, so here it is.

The following routine, if added below -startAnimation: will cause the tiles to scroll to the specified tile, with pos specified from 0 to the max-1 tile.


- (void)runToPos:(int)pos
{
	int max = [self numTiles]-1;
	if (pos  max) pos = max;
	
	startOff = offset;
	startSpeed = sqrt(fabs(pos - startOff) * FRICTION * 2);
	if (pos < startOff) startSpeed = -startSpeed;
	
	runDelta = fabs(startSpeed / FRICTION);
	startTime = CACurrentMediaTime();
	
	NSLog(@"startSpeed: %lf",startSpeed);
	NSLog(@"runDelta: %lf",runDelta);
	timer = [NSTimer scheduledTimerWithTimeInterval:0.03
					target:self
					selector:@selector(driveAnimation)
					userInfo:nil
					repeats:YES];
}

The way this works is to calculate the flick speed necessary to run the animation to the specified position, and runs the animation.