Detect if city is within area

db, development, geo Add comments

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.

One Response to “Detect if city is within area”

  1. vitalka Says:

    Hi!
    Will work with these functions defining entry points to a polygon or multipolygon?
    But not in LINESTRING.
    Thank you.

WP Theme & Icons by N.Design Studio
Entries RSS Comments RSS Log in