Search code examples
google-mapsgeometrygeospatialgeo

Point in polygon test for London map data


I need to test if a point is in a polygon for some map data across London.

Is it safe to ignore the spherical aspect of the data at this scale and just treat it as planar? It's not super critical for our needs to be 100% accurate. An error of about 10m is probably OK.

(I'm aware there might be functions in the Google maps API that already does this but we're pre-calculating server-side.)


Solution

  • In the worst case, where you have a single polygon representing the whole of London the error may well exceed your target of 10m. If:

    • London is centred at N51.5deg,E0.0deg;
    • the radius of London is 0.5deg of longitude;

    then the maximum displacement between the great circle from N51.5 E0.5 to N51.5 W0.5 and the rhumb line between the same points (the rhumb line is the one which you would work with if treating spherical coordinates as plane) would be about 142m. If you used one giant rectangle to model London the error would exceed your tolerance.

    The safety of the approximation depends, therefore, on how many polygons you are using to represent London, more particularly on the maximum length of the side of any polygon in your representation.

    EDIT

    to address OP's comments:

    Yes, I believe that using the rhumb line is the same as naively pretending lat/lng are planar coordinates and that no further transformation is required. In the simple example I constructed the rhumb line between N51.5 E0.5 and N51.5 W0.5 is an arc of the small circle between the points which is also a line of latitude and in this case is also the same line you'd draw if treating lat/long as plane coordinates. But this is a special case, tailored for my answer. To be honest I'm not certain, but I think that on a Mercator projection this is generally true, ie that a rhumb line is the same as the line you'd get by treating lat/long as plane coordinates.

    The question, as posed, can be reduced to asking whether a point is on one side of a line or the other. A point is inside a polygon if it is on the inside side of one of the line segments which form the boundary of the polygon.

    On a sheet of paper draw a circle. Then draw a chord between any 2 points on the circle. Now you have an illustration of the problem: the circle represents the great circle between any 2 points on a spherical earth, the straight line represents the small circle between the points. The distance between the chord and the circle represents the distance between the great and small circles which is the error you might make with the naive assumption.

    It's rough and it's ready and the only claim I make is that IF your map of London is modelled as one polygon with a side of approximately 1deg of longitude in length THEN the error in positioning arising from treating spherical coordinates as plane may be greater than 140m.