MySQL Geo Distance Code and Samples

Over the years, I’ve implemented and re-implemented the haversine formula whenever I’ve needed to compute great-circle distances, which is pretty common when you’re doing geospatial proximity searches, e.g., “What’s near me?” or “How far are these two locations from each other?”

For an implementation of the formula in MySQL, Alexander Rubin’s presentation is quite useful, and is what I’ve based the following code on this time around.

Hopefully, rather than re-implementing this yet again the next time I need it, I’ll find my own blog entry on it and just reuse this code. I keep forgetting where I’ve stashed the most recent copy, which is why I keep ending up re-implementing this every time I’ve needed it.

Here’s the code, tested on MySQL 5.1.41:

DELIMITER $$

DROP FUNCTION IF EXISTS geodist $$
CREATE FUNCTION geodist (
  src_lat DECIMAL(9,6), src_lon DECIMAL(9,6),
  dst_lat DECIMAL(9,6), dst_lon DECIMAL(9,6)
) RETURNS DECIMAL(6,2) DETERMINISTIC
BEGIN
  SET @dist := 3956 * 2 * ASIN(SQRT(
      POWER(SIN((src_lat - ABS(dst_lat)) * PI()/180 / 2), 2) +
      COS(src_lat * PI()/180) *
      COS(ABS(dst_lat) * PI()/180) *
      POWER(SIN((src_lon - dst_lon) * PI()/180 / 2), 2)
    ));
  RETURN @dist;
END $$

DROP FUNCTION IF EXISTS geodist_pt $$
CREATE FUNCTION geodist_pt (src POINT, dst POINT) 
RETURNS DECIMAL(6,2) DETERMINISTIC
BEGIN
  RETURN geodist(Y(src), X(src), Y(dst), X(dst));
END $$

DROP PROCEDURE IF EXISTS geobox $$
CREATE PROCEDURE geobox (
  IN src_lat DECIMAL(9,6), IN src_lon DECIMAL(9,6), IN dist DECIMAL(6,2),
  OUT lat_top DECIMAL(9,6), OUT lon_lft DECIMAL(9,6),
  OUT lat_bot DECIMAL(9,6), OUT lon_rgt DECIMAL(9,6)
) DETERMINISTIC
BEGIN
  /*
   * src_lat, src_lon -> center point of bounding box
   * dist -> distance from center in miles
   * lat_top, lon_lft -> top left corner of bounding box
   * lat_bot, lon_rgt -> bottom right corner of bounding box
   */
  SET lat_top := src_lat - (dist / 69);
  SET lon_lft := src_lon - (dist / ABS(COS(RADIANS(src_lat)) * 69));
  SET lat_bot := src_lat + (dist / 69);
  SET lon_rgt := src_lon + (dist / ABS(COS(RADIANS(src_lat)) * 69));
END $$

DROP PROCEDURE IF EXISTS geobox_pt $$
CREATE PROCEDURE geobox_pt (
  IN pt POINT, IN dist DECIMAL(6,2),
  OUT top_lft POINT, OUT bot_rgt POINT
) DETERMINISTIC
BEGIN
  /*
   * pt -> center point of bounding box
   * dist -> distance from center in miles
   * top_lft -> top left corner of bounding box
   * bot_rgt -> bottom right corner of bounding box
   */
  CALL geobox(Y(pt), X(pt), dist, @lat_top, @lon_lft, @lat_bot, @lon_rgt);
  SET top_lft := POINT(@lon_lft, @lat_top);
  SET bot_rgt := POINT(@lon_rgt, @lat_bot);
END $$

DROP PROCEDURE IF EXISTS geobox_pt_bbox $$
CREATE PROCEDURE geobox_pt_bbox (
  IN pt POINT, IN dist DECIMAL(6,2), OUT bbox POLYGON
) DETERMINISTIC
BEGIN
  /*
   * pt -> center point of bounding box
   * dist -> distance from center in miles
   * bbox -> bounding box, dist miles from pt
   */
  CALL geobox_pt(pt, dist, @top_lft, @bot_rgt);
  SET bbox := Envelope(LineString(@top_lft, @bot_rgt));
END $$

DELIMITER ;

And, here’s examples on how to use the above function and procedures:

SELECT @src := pt FROM exp_geo
WHERE postal_code = '07405' AND city = 'Butler';

CALL GEOBOX_PT(@src, 10.0, @top_lft, @bot_rgt);
SELECT Y(@top_lft) AS lat_top, X(@top_lft) AS lon_lft,
       Y(@bot_rgt) AS lat_bot, X(@bot_rgt) AS lon_rgt;

CALL GEOBOX_PT_BBOX(@src, 10.0, @bbox);
SELECT AsWKT(@bbox);

-- Assuming INDEX on (lat, lon) and SPATIAL INDEX on (pt) ...

-- Fast:
SELECT g.postal_code, g.city, g.state,
       GEODIST(Y(@src), X(@src), lat, lon) AS dist
FROM exp_geo g
WHERE lat BETWEEN Y(@top_lft) AND Y(@bot_rgt)
AND lon BETWEEN X(@top_lft) AND X(@bot_rgt)
HAVING dist < 5.0
ORDER BY dist;

-- Also fast:
SELECT g.postal_code, g.city, g.state, GEODIST_PT(@src, g.pt) AS dist
FROM exp_geo g
WHERE lat BETWEEN Y(@top_lft) AND Y(@bot_rgt)
AND lon BETWEEN X(@top_lft) AND X(@bot_rgt)
HAVING dist < 5.0
ORDER BY dist;

-- Slow:
SELECT g.postal_code, g.city, g.state, GEODIST_PT(@src, g.pt) AS dist
FROM exp_geo g
WHERE Y(pt) BETWEEN Y(@top_lft) AND Y(@bot_rgt)
AND X(pt) BETWEEN X(@top_lft) AND X(@bot_rgt)
HAVING dist < 5.0
ORDER BY dist;

-- Also slow:
SELECT g.postal_code, g.city, g.state, GEODIST_PT(@src, g.pt) AS dist
FROM exp_geo g
WHERE MBRContains(@bbox, pt) = 1
HAVING dist < 5.0
ORDER BY dist;

Normally, I try to explain the stuff I post, but this time I’m doing it for somewhat selfish reasons — so I don’t lose this work yet again. I’m just throwing this up here so Google will index it, so I can find it the next time I need it.

I suppose if you read this and have questions, please ask them in the comments below. I’ll do my best to answer, if I can.

How To Upgrade an AT&T Captivate to Gingerbread with Cognition 5 on a Mac

Disclaimer: Everything you see here is at-your-own-risk. If this doesn’t work for you, or it ends up bricking your phone, etc., it’s your own damn fault. Sorry. All I can say is that it worked great for me.

Prerequisites

You’ll need to download all of these files before you get started. If figuring out how to download these things proves to be too hard for you to figure out, then you should not be attempting this project. You probably don’t understand enough of the basics, and will make a mistake that will likely brick your device.

Now, let’s get started …

1. BACK UP EVERYTHING FIRST!

Use Titanium Backup to back up all of your data and apps. Use ClockworkMod ROM Manager to back up your current ROM.

Don’t say I didn’t warn you …

2. Copy Cognition5-v2.zip to your internal SD card

You’ll need to do this first, before you start the following steps. Hook up your phone using your USB cable and use “mass storage mode” to copy the zip file over.

3. Reboot into download mode

Throughout this process, you’ll need to keep putting your phone into “download mode.” You’ll know you’re in download mode because the phone will display a screen with a big yellow triangle with the Android robot holding a shovel, and the word “Downloading…” underneath it, and the words “Do not turn of Target!!!” at the bottom of the screen.

Android download mode screen

To put your phone into “download mode,” use the following steps:

1. Disconnect the USB cable, remove your battery.
2. Wait 5 seconds.
3. Connect the USB cable.
4. Press and hold the volume up and volume down buttons.
5. Insert the battery.

If you’ve done this right, you should be in download mode.

4. Flash stock Gingerbread using Heimdall

I’m not thrilled with the Heimdall frontend, so I just use the command-line interface using Terminal.app.

First, verify that Heimdall can see your Captivate in download mode. You should see:

$ heimdall detect
Device detected

If, instead, you see this:

$ heimdall detect
Failed to detect compatible download-mode device.

Stop now. Go back, figure out what you did wrong. You cannot proceed until Heimdall can see your phone connected via USB and in download mode.

***

To flash the stock Gingerbread ROM, we’ll need to prepare a little bit, first. Start by extracting the I897UCKF1.rar file, which should contain the following files:

CODE_I897UCKF1_CL273832_REV02_user_low_ship.tar.md5
Kepler_odin_new_part_JE3_S1JE4.pit
MODEM_I897UCKF1_CL1017518_REV02.tar.md5
odin v1.81.zip
SGH-I897-CSC-ATTKF1.tar.md5

We will need to extract the files from two of these tar files:

$ tar xf CODE_I897UCKF1_CL273832_REV02_user_low_ship.tar.md5

$ tar xf MODEM_I897UCKF1_CL1017518_REV02.tar.md5

Now we should have the following files: Sbl.bin, boot.bin, cache.rfs, dbdata.rfs, factoryfs.rfs, modem.bin, param.lfs, zImage. With our Captivate in download mode, we will flash these using the following command:

$ heimdall flash --repartition --pit Kepler_odin_new_part_JE3_S1JE4.pit \
    --factoryfs factoryfs.rfs --cache cache.rfs --dbdata dbdata.rfs \
    --param param.lfs --primary-boot boot.bin --secondary-boot Sbl.bin \
    --kernel zImage --modem modem.bin

Heimdall v1.3.0, Copyright (c) 2010-2011, Benjamin Dobell, Glass Echidna
http://www.glassechidna.com.au

This software is provided free of charge. Copying and redistribution is
encouraged.

If you appreciate this software and you would like to support future
development please consider donating:
http://www.glassechidna.com.au/donate/

Initialising connection...
Detecting device...
Claiming interface...
Setting up interface...

Beginning session...
Handshaking with Loke...

Uploading PIT
PIT upload successful
Uploading KERNEL
100%
KERNEL upload successful
Uploading MODEM
100%
MODEM upload successful
Uploading FACTORYFS
100%
FACTORYFS upload successful
Uploading DBDATAFS
100%
DBDATAFS upload successful
Uploading CACHE
100%
CACHE upload successful
Uploading IBL+PBL
100%
IBL+PBL upload successful
Uploading SBL
100%
SBL upload successful
Uploading PARAM
100%
PARAM upload successful
Ending session...
Rebooting device...

After the device reboots, you should have a working Captivate running stock Gingerbread ROM.

5. Flash Cognition 5 v2 using Heimdall

Again, put yourself in download mode using the instructions from the previous step, then flash the Cognition 5 v2 initial kernel:

$ heimdall flash --kernel Cognition5-v2-initial-kernel.tar

[...]
Uploading KERNEL
100%
KERNEL upload successful
Ending session...
Rebooting device...

From here, follow the usual steps to get into ClockworkMod Recovery, and install the Cognition5-v2.zip update that we copied onto the internal SD earlier in step #3.

If all goes well, you should be able to reboot your phone after the update and be up and running on Cognition 5 v2!

***

If I’ve made a mistake in any of the steps, or have left out important details, feel free to help correct them by leaving a comment below.

Personal update and new family photo

I went through all the trouble of setting up a much improved email subscription for my blog using MailChimp almost 3 weeks ago, and of course I haven’t even posted anything to the blog since! That means a bunch of you signed up to see what I’d done, and didn’t get to see anything, yet. Sorry about that.

Personal Update

Despite the recent hurricane Irene, we spent a week up on Cape Cod, in Mashpee, for the week of August 27th through September 3rd. After dealing with very strong winds and a power outage for a few hours on Sunday, we all had a fantastic time and incredibly good weather. Here’s a family photo we were able to take while we were out at a mini-golf place:

Family photo on Cape Cod - 2011-08-30

We’re back home, the girls have started school again, and work has been keeping me particularly busy.

Work Update

At work, we’ve been testing a fully fault-tolerant design: redundant firewalls, redundant load balancers, a farm of web frontends and replicated database backends. We’ve done several load tests to verify that they’ll be able to handle the volume of traffic that we get, with a fairly large multiple of our highest peak volume.

Tonight, we’re deploying these servers. Even though I’ve done this many times over the course of my career, it’s still exciting in its own way. Sometimes you have something unexpected happen that you have to deal with. However, when things just go smoothly, according to plan, like it did tonight … it’s just a great feeling, watching everything just fall into place.

I hope everyone’s had as best a week they can, given the circumstances–the flooding on the east coast, etc. I’ll try to post updates more frequently. Oh, and if you have any comments or feedback about the new MailChimp-delivered blog email updates, definitely let me know! I really want to hear what everyone thinks of them. Thanks!

Blog updates, now via MailChimp

mailchimp.jpg

A few dozen people have signed up to receive email updates to this blog, which I’ve used Feedburner for in the past. However, I realize that I don’t have much control over how Feedburner does things, and I’ve finally decided to do something about it.

Now, I’m changing over to using MailChimp to send out the blog updates using their RSS campaign feature.

Using MailChimp, I can have my blog updates emailed out using a custom template, which I’ve styled to look very similar to my actual blog. Now, maybe my choice of colors and style needs serious help, but at least now I have the option, where I didn’t before.

What this all means is, if you’d like to receive (or continue to receive) emailed blog updates, you’ll need to subscribe to this new list. (Sorry!) To make that easier, I’m including a sign-up form below.

Fill out this form now to get updates emailed to you:

* indicates required



Email Format

Cross-posting from WordPress to LiveJournal woes

WordPress to LiveJournal woes

I hate to do this, but I’m finally fed up with something that’s been bothering me for a while …

I’ve used a series of various WordPress plugins that mirror posts to LiveJournal, and for the most part, they work great. However, there’s been an issue: whenever I edit a post, it appears to delete the LJ post and post it as new. Not a huge problem, except for the fact that any comments left on the old LJ post are lost, which is a real drag.

I’m starting to wonder if it’s not WordPress or the plugins that are causing the problem, but the blog post authoring app that I use: MarsEdit. I don’t think so, but I haven’t ruled it out yet.

So, I’m posting this entry and will be using it as a test entry in which I’ll try to get to the bottom of things, either fixing the plugin that I’m currently using or otherwise figuring out what the problem is. Therefore …

Don’t post comments on this entry, or at least expect them to disappear suddenly as I test.

Thanks.

Update: This post originally was posted to LJ as http://dossy.livejournal.com/68169.html. Here’s the first edit using the WP web interface directly.

Update #2: Great, WP updated the post and updated the LJ post without changing the post ID. Now, I’m editing the post and adding this update using MarsEdit. Let’s see what happens …

Update #3: Aha! After posting the last edit using MarsEdit, the post on LiveJournal disappeared. A new post on LJ was created, with the latest post content, though: http://dossy.livejournal.com/68462.html. Not sure if it’s really MarsEdit’s fault, or a bug in the WordPress XML-RPC interface that MarsEdit uses, or the way that MarsEdit uses it. For completeness, I’m going to note that the WordPress post_id hasn’t changed regardless of how the post is edited.

Update #4: This reminds me, I need to submit an enhancement request for MarsEdit, to refresh an individual post from the server. Having to refresh all posts and pages just to pick up the edits within MarsEdit that I make in the WP interface is quite cumbersome.

Update #5: I’ve also posted a thread on the Red Sweater MarsEdit forum about this issue, to see if I can get any troubleshooting help there.

Update #6: I posted detailed troubleshooting information to the forum, but the summary is that MarsEdit invokes the WP XML-RPC in a way that marks the blog post as unpublished, then published again, and that causes the WP plugin to delete the LJ post and then re-post it. I’ve gone and made some adjustments to the plugin to NOT do this, so hopefully folks commenting on LJ won’t have their comments so unceremoniously deleted. Ideally, MarsEdit shouldn’t be marking posts as unpublished then republished (seriously, what?) but since I can’t fix that, I can fix the plugin to not delete LJ posts in response.

Of course, Google takes G+ very seriously …

So seriously, in fact, that …

Google has just launched games on Google+.

Because, you know, having games on G+ is SO much more important than fixing ALL the horrible usability problems with G+ …

Every time I say something negative about G+, the rabid fanboys say something that goes like this (paraphrasing):

But, but, but, the G+ team is doing all they can to make the service, the experience, etc., better … just cut them some slack and give them time.

… and then, Google goes and does something like this.

Google Mannekin Pis
(credit: Accidental Hedonist on Flickr)

Launching games on G+ now is like pissing on G+ users and calling it rain.

It’s one of the features that users explicitly do not want. In the early days of G+, one of the things most commonly cited by the fanboys as giving Google an edge over Facebook was “the lack of games cluttering up the stream”.

Like I’ve been saying all along, everyone will slowly come out of the “ooh, new and shiny” haze they’re in, and realize how badly G+ sucks in comparison to Facebook.

Google+ will soon join the ranks of Google Wave and Google Buzz. Remember them? Yeah …

Capturing analog video on the Mac

Years ago, I purchased a Dazzle Hollywood DV-Bridge to capture DV video over FireWire. It wasn’t great, but it was good enough — okay, fine, it was better than nothing and it was affordable. I wasn’t ready to spend the money on a Canopus ADVC at the time.

Fast forward to today, and there’s a larger variety of affordable products that do analog video capture. Specifically, I’m looking at products that can be used on MacOS X, and a popular one is the Elgato Video Capture device. It looks like a great product, but it only has composite video input, and I need something that can accept component video input, either RGB or YPbPr.

Blackmagic Design Video Recorder

Blackmagic Video Recorder

The Blackmagic Design Video Recorder is an affordable (under $150) USB 2.0-based device that can accept both component and composite video and produces H.264-encoded video, and supports on MacOS X.

What makes me somewhat nervous is that there’s really no good, qualitative reviews of the equipment in comparison to comparable products. The best review I’ve found at all is this one on iLounge from back in 2009, and it’s really just an unboxing of the product, not really a review.

I’ve gone and contacted Blackmagic support and asked them the following questions:

  • Does the Video Recorder do time-base correction (TBC) or will I need to add one between the source video and the Video Recorder device?
  • Also, reviews all state that the device cannot accept 480p as input? Is this still true? Is this something that can/has been fixed with newer firmware?
  • Reviewers also state that the Video Recorder only generates output in 720×480 – is this the only resolution that it can output? If I’m converting PAL video and want to output for PAL DVD, I’d like to capture in 720×576. Can the Video Recorder handle this?

Matrox MXO2

Matrox MXO2 family

Remember how I was talking about cheap and affordable? If money were no object, I’d be seriously looking at the Matrox MXO2 family of products. At the lowest end, the MXO2 Mini starts at bare minimum of $450, but I wouldn’t even bother considering buying it without the Matrox MAX H.264 hardware encoder, which bumps the price up to $850.

Pro’s:

  • Extremely versatile: HDMI, component, composite video.
  • Fast: MAX H.264 provides faster-than-realtime encoding acceleration.

Con’s:

  • Not cheap: You get what you pay for.
  • Strange host connector: PCIe, not USB 2.0 or FireWire 800.

If you have an older MacBook Pro, like me, that still has an ExpressCard/34 slot, Matrox offers a PCIe ExpressCard that you can use to connect to the MXO2 devices. The newest 17″ MacBook Pro still has an ExpressCard slot, but the 13″ and 15″ don’t. Matrox appears to be offering a Thunderbolt adapter for the MXO2, but it’s priced at $299. No, that’s not a typo: just shy of $300 for what is effectively a Thunderbolt-to-PCIe-2.0 adapter. Still, it’s a usable solution.

In the short term, I’ll probably pick up the Blackmagic Video Recorder assuming it actually works as advertised, but if I start getting more video conversion and production work, I’ll definitely be investing in the MXO2 Mini MAX ($849) or MXO2 LE MAX ($1,395), or perhaps even the full MXO2 MAX ($1,995).

What do you feed your brain?

I’ve never really been a huge consumer of podcasts, because I’ve never really had the opportunity to consume them. When I work, I prefer to listen to music. Until recently, I haven’t had a regular commute; since May, I now commute into Manhattan once a week. This gives me close to 2 hours each week where I can listen to and/or watch podcasts.

Head silhouette

So far, I’ve only subscribed to TED, which has been incredibly excellent. Today, I added RSA videos. This is the kind of content I’m interested in — stuff that I can learn something from.

I’m surprised no one’s done a “Wikipedia Daily” podcast: take Wikipedia’s “Today’s Featured Article” and do a clear audio reading of it, ideally in various languages, possibly with a video component which could be as simple as a slideshow of the images from the article. Right now, you can subscribe by email, but you just get a portion of the Wikipedia article emailed to you, which is a useful reminder to check the full article, but not very useful on its own. If anyone is interested in pursuing this idea, I’d be happy to collaborate.

I’m looking to feed my brain with new, interesting, useful and preferably factual information. What are your favorite podcasts? What do you feed your brain? Let me know by leaving a comment!

It doesn’t get better

Anyone who tries to tell you that it gets better is either full of shit or is trying to sell you something. Or, both.

It doesn't get better

People all around me in my personal life are going through very difficult times emotionally (and some physically) right now, and I don’t know what to tell them. I’d love to tell them, with sincerity and compassion, that things will get better. But, I can’t. I know it would be nothing but a lie.

When a loved one dies, or life just seems so out of control that you want to ragequit, or bad shit just keeps happening over and over … does it ever really get better? You might get used to it. You might even learn to care less. You might just grow numb and cold to it. But, shit, what’s happened has happened. Nothing is going to magically reverse it. There’s no “undo” to life. It isn’t going to get better, ever. That “it gets better” rhetoric is just bullshit.

I don’t know what to say to all these people who are hurting. I know enough about myself to know that anything I say is just going to make things worse, so I try really hard to not say anything at all. But, I don’t want my silence to be construed as apathy, either.

I wish I could cheer you up. I wish I could ease your suffering. I wish I could end your pain. I wish I knew how to say the right thing at the right time to you. I wish things would actually get better.

You’d never watch Cheers if it were like this

The other day, my friend Mike invited me out for some drinks at a local bar. It’s a nice bar with friendly staff and good food. I’m not much of a drinker; my vice is smoking. Still, I like spending time with friends, and bars tend to be a popular place to go and be social.

Now, this particular bar has no dance floor. It’s a bar on one side and a restaurant on the other. It’s not the kind of place that would come to mind when you think of places to go and dance. Just keep that in mind …

The night we went, the music was especially loud. Now, I love music and some ambient tunes in a social setting can be really pleasant. That wasn’t what we had that night, though. It was loud … so loud that I strained to hear anything Mike had to say and had to shout for him to hear me. By the time we’d left, my throat was sore and my voice was hoarse, and my ears were still buzzing once we got outside. This was ridiculous.

Here’s a pro-tip to anyone who runs a bar:

Unless there’s some titties dancing on the bar or around it, turn down the fucking music.

Remember that old TV show “Cheers”? Do you remember there being music playing in the background during the show? I sure as hell don’t. What they had were people drinking and socializing at a bar. Nobody would have watched that show if everyone were shouting over some high-energy music the whole episode.

I guess I just need to find a better bar. One that is actually run in a way that encourages people to enjoy alcohol while actually interacting with other people. Anyone have any recommendations for places within 15-20 miles of Butler, NJ? Or, are all bars like the one I was at, and I should just not bother going out for drinks any more?