2

I have a geojson object defining Neighborhoods in Los Angeles using lon/lat polygons. In my web application, the client has to process a live stream of spatial events, basically a list of lon/lat coordinates. How can I classify these coordinates into neighborhoods using Javascript on the client (in the browser)?

I am willing to assume neighborhoods are exclusive. So once a coordinate as been classified as neighborhood X, there is no need to further test it for other neighborhoods.

Jeroen Ooms
  • 31,998
  • 35
  • 134
  • 207

2 Answers2

3

There's a great set of answers here on how to solve the general problem of determining whether a point is contained by a polygon. The two options there that sound the most interesting in your case:

  • As @Bubbles mentioned, do a bounding box check first. This is very fast, and I believe should work fine with either projected or unprotected coordinates. If you have SVG paths for the neighborhoods, you can use the native .getBBox() method to quickly get the bounding box.

  • the next thing I'd try for complex polygons, especially if you can use D3 v3, is rendering to an off-screen canvas and checking pixel color. D3 v3 offers a geo path helper that can produce canvas paths as well as SVG paths, and I suspect if you can pre-render the neighborhoods this could be very fast indeed.

Update: I thought this was an interesting problem, so I came up with a generalized raster-based plugin here: http://bl.ocks.org/4246925

This works with D3 and a canvas element to do raster-based geocoding. Once the features are drawn to the canvas, the actual geocoding is O(1), so it should be very fast - a quick in-browser test could geocode 1000 points in ~0.5 sec. If you were using this in practice, you'd need to deal with edge-cases better than I do here.

If you're not working in a browser, you may still be able to do this with node-canvas.

Community
  • 1
  • 1
nrabinowitz
  • 55,314
  • 10
  • 149
  • 165
  • It looks like leaflet won't directly generate bounding boxes for you, but you can [specify them with coordinates and check points for membership](http://leafletjs.com/reference.html#bounds). Creating the bounding box should be a pretty straightforward affair though, so that'd get you pretty close to a full solution. – Bubbles Dec 09 '12 at 07:11
  • See edit - pretty sure this is the right solution for this case. – nrabinowitz Dec 11 '12 at 23:08
  • Edit: a good solution for this case. It depends how important accuracy is. – nrabinowitz Dec 11 '12 at 23:43
  • I did manage to hack together a ray-casting algorithm over the weekend, but didn't have a chance to do much by way of testing. I'll see if I can cook something up to compare accuracy and speed later tonight. – Bubbles Dec 12 '12 at 00:41
  • I like this solution, however it has some strange bugs. For example http://bl.ocks.org/jeroenooms/5440947 gives a completely differente result in chrome and firefox. – Jeroen Ooms Apr 23 '13 at 18:07
  • @Jeroen - really? I see "Central-Alameda" in both browsers, for both points. It's quite possible that edge-case handling is different across browsers, though, as it depends on browser anti-aliasing. – nrabinowitz Apr 23 '13 at 22:41
  • It says "Castaic Canyons" in chrome 25 on Ubuntu. Actually it classifies a quite large share of the point differently, not just edge cases. I have a hard time figuring out what the problem is. – Jeroen Ooms Apr 24 '13 at 19:04
  • Huh. Have you tried visually plotting the lat/lon points to see where it thinks they are? – nrabinowitz Apr 24 '13 at 20:25
1

I've seen a few libraries out there that do this, but most of them are canvas libraries that may rely on approximations more than you'd want, and might be hard to adapt to a project which has no direct need to rely on them for intersections.

The only other half-decent option I can think of is implementing ray casting in javascript. This algorithm isn't technically perfect since it's for Euclidean geometry and lat/long coordinates are not (as they denote points on a curved surface), but for areas as small as a neighbourhood in a city I doubt this will matter.

Here's a google maps extension that essentially does this algorithm. You'd have to adapt it a bit, but the principles are quite similar. The big thing is you'd have to preprocess your coordinates into paths of just two coordinates, but that should be doable.*

This is by no means cheap - for every point you have to classify, you must test every line segment in the neighborhood polygons. If you expect a user to be reusing the same coordinates over and over between sessions, I'd be tempted to store their neighborhood as part of it's data. Otherwise, if you are testing against many, many neighborhoods, there are a few simple timesavers you can implement. For example, you can preprocess every neighborhoods extreme coordinates (get their northmost, eastmost, southmost, and westmost points), and use these to define a rectangle that inscribes the town. Then, you can first check the points for candidate neighborhoods by checking if it lies inside the rectangle, then run the full ray casting algorithm.

*If you decide to go this route and have any trouble adapting this code, I'd be happy to help

Bubbles
  • 3,795
  • 1
  • 24
  • 25
  • I'm using leaflet. It needs to be fast though, it should be able to classify 1000 points without experiencing hickups. I was secretly hoping for an existing implementation that does this efficiently. It probably requires some smart algorithm as you describe. Perhaps calculate the mean lat and long for each neighborhood, and testing them in order of how close the coordinate is to the means. I am assuming neighborhoods are exclusive, so once there is a hit, it can go on to the next point. – Jeroen Ooms Dec 08 '12 at 01:37
  • Hurm. Well, if this can wait until Monday, there's a decent chance I could try out the rectangle-inscription technique tomorrow afternoon. I've been meaning to implement something like that for a while now, I'm kinda curious how it performs. Since you're looking at neighborhoods instead of cities I bet it will work reasonably well, since you don't have to worry about nonsense like Los Angeles including San Pedro in it's city boundaries; neighborhoods tend to be fairly square-ish in their distribution. – Bubbles Dec 08 '12 at 22:07