I want to be free

We at SunnyRentals are working a lot with geo data.

The last task I was solving was inclusion of all cities in a touristic regions bounds automatically.

Yes, there are MySQL spatial data types, so region border and cities coordinates can be stored in native data types, but the processing functions are not implemented right: they only operate on MBRs (minimum bounding rectangles) to make things simpler…

So, let’s create our own MySQL function for that.

There are different approaches to distinguish if a point is within a given polygon. I prefered the way to iterate the edges of the polygon and check where the point relatively to the edge is – at right or at left; if the point is always at the same side, it lies within the border.

So we came to a fact that we need 2 functions:

1. Distinguish the side at which the point lies from the line
2. Check that for every edge in the polygon.

Here is the first function:

DELIMITER //

DROP FUNCTION `GetPointPositionOfLine`//
CREATE FUNCTION `GetPointPositionOfLine`( a POINT, b POINT, p POINT) RETURNS tinyint NO SQL
  COMMENT 'Distinguish the side at which the point lies from the line'
BEGIN
  DECLARE s DOUBLE;
  SET s = (X(b) - X(a))*(Y(p) - Y(a)) - (Y(b) - Y(a))*(X(p) - X(a));
  IF s > 0 THEN
    RETURN 1;
  END IF;
  IF s < 0 THEN
    RETURN -1;
  END IF;
  RETURN 0;
END //

All three params are of type POINT. Points a and b are the beginning and end of the line. Point p is the point we check.

Here is the main function:

DELIMITER //

DROP FUNCTION `IsPointWithin`//
CREATE FUNCTION `IsPointWithin`( ls LINESTRING, p POINT) RETURNS tinyint(1) NO SQL
BEGIN
  DECLARE i INT;
  DECLARE a, b POINT;
  DECLARE LineStringNumPoints INT;
  DECLARE Position, PrevPosition TINYINT;

  SET i = 1;
  SET PrevPosition = 0;
  SET LineStringNumPoints = NumPoints(ls);

  WHILE i <= LineStringNumPoints DO
    SET a = PointN( ls, i);
    IF i = LineStringNumPoints THEN
      SET b = StartPoint( ls);
    ELSE
      SET b = PointN( ls, i+1);
    END IF;

    SET Position = GetPointPositionOfLine( a, b, p);
    IF Position <> 0 THEN
      IF Position <> PrevPosition AND PrevPosition <> 0 THEN
        RETURN FALSE;
      END IF;
      SET PrevPosition = Position;
    END IF;
    SET i = i + 1;
  END WHILE;
  RETURN TRUE;
END //

It checks if a point p lies within a polygon of type LINESTRING.

Usage example. Given you have coordinates of cities in the separate float columns (to keep them readable) lat and lng of city table, and the polygon is given as a string too — but of course you can use a column of type LINESTRING:

SELECT *
FROM `city` c
WHERE IsPointWithin(GeomFromText('LINESTRING(4 8, 15 16, 23 42)'), POINT(c.`lat`, c.`lng`));

The solution works pretty fast, especially if you first limit the cities by the rectangle that the polygon lies in.

Reverse Geocoding is process opposite to Geocoding (when you get map coordinates by city/country given). So the idea is to get city name by coordinates on the map.

Why you may need it? For example, user is supposed to add a marker on the map, and you want to check that the marker is within a particular country or region.

Solutions:

1. Google GeoCoder (JavaScript) can work with coordinates to retrieve location name. Advantage is that return information is translated to the preferred language of your browser. Here is an example you can play with.
2. GeoNames.org offers several services, among which you can find Reverse Geocoding web service (REST or JSON) which can work with coordinates and postal codes. Advantage — you can download city/region/country names and POI with coordinates.

By the way, here are results of benchmarking Google vs. GeoNames.