Finding Points in a Rectangle or Circle with mysql

Question

I have a mysql database table with a list points with their Co-ordinates (x,y)

I want to find the list of points which fall inside the rectangle. This would have been simple had any one side of the rectangle been aligned parallel or perpendicular to any axis. But is not. Which means the rectangle is rotated. I also have to find the points inside a circle.

Known Data for Rectangle -Coordinates for all the four points Known Data for Circle -Co-ordinates for the center and the radius.

How do I query the mysql table to find the points falling in the rectangle and the circle?

If it matters then the front end I am using is PHP.

Answer 1

A rectangle can be defined by two points representing the opposing corners, eg: A(x,y) and B(x,y). If you have a point C(x,y) that you want to test to see if it is inside the rectangle then:

IF( (Cx BETWEEN Ax AND Bx) AND (Cy BETWEEN Ay AND By) ) THEN
  point C is in the rectangle defined by points A and B
ELSE
  nope
ENDIF

A circle can be defined by a single point C(x,y) and a radius R. If the distance D between the center and the point P(x,y) is less than the radius R, then it is inside the circle:

And of course you remember the Pythagorean Theoreom, right?

C² = A² + B² SO C = SQRT(A² + B²)

So:

D = SQRT( ABS(Cx - Px)² + ABS(Cy - Py)²)

IF( D <= R ) THEN
  point P is inside the circle with center C and radius R
ELSE
  nope
ENDIF

edit:

The algorithm for checking if a point is within a polygon is a bit more complex than what I'd prefer to write in a SQL query or stored procedure, but it is entirely possible. It's worth noting that it runs in constant-time and is very lightweight. [requires roughly 6 arithmetic ops and maybe 2 or 3 logic ops for each point in the poly]

To pare down the number calculations required you can simply write your select to get points within a rough bounding box before procesing them further:

WHERE
  x BETWEEN MIN(x1,x2,x3,x4) AND MAX(x1,x2,x3,x4)
  AND
  y BETWEEN MIN(y1,y2,y3,y4) AND MAX(y1,y2,y3,y4)

Assuming the columns containing the x and y values are indexed this might use a few less CPU cycles than simply doing the math, but it's debatable and I'm inclined to call it a wash.

As for the circle you can't possibly get more efficient than

WHERE
  SQRT( POW(ABS($Cx - x),2) + POW(ABS($Cy - y),2) ) < $radius

You're far too concerned with the perceived cost of these calculations, just write the code and get it working. This is not the stage to be performing such niggling optimizations.

Answer 2

One thing to add to @Sammitch's answer is, calculating haversine distance in case you are looking at latitudes and longitudes on world map (distance calculation on a spherical surface, since Earth is a sphere ;) https://en.wikipedia.org/wiki/Haversine_formula)

Here's a vanilla Javascript example for calculating that:

          function calculateHaversineDistance(lat1x, lon1, lat2x, lon2) {
            var R = 6371; // km
            var dLat = toRad(lat2x-lat1x);
            var dLon = toRad(lon2-lon1);
            var lat1 = toRad(lat1x);
            var lat2 = toRad(lat2x);
            var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
                    Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2);
            var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
            return R * c;
          }
          function toRad(x) {
             return x * Math.PI / 180;
          }

EDIT->

Here's a php version I wrote:

function toRad($x) {
 return $x * pi() / 180;
}

function calculateHaversineDistance($lat1, $lon1, $lat2, $lon2) {

    $R = 6371; // km
    $dLat = $this->toRad($lat2-$lat1);

    $dLon = $this->toRad($lon2-$lon1);

    $lat1 = $this->toRad($lat1);

    $lat2 = $this->toRad($lat2);


    $a = sin($dLat/2) * sin($dLat/2) +
            sin($dLon/2) * sin($dLon/2) * cos($lat1) * cos($lat2);

    $c = 2 * atan2(sqrt($a), sqrt(1-$a));

    return $R * $c;
}