Location Based Result in couchbase


#1

here is my report doc

{
   "agree_allowed":true,
   "assigned_by":"",
   "assigned_to":"",
   "comments_allowed":true,
   "location": {
    "coordinates": [
      "-74.168868",
      "40.854655"
    ],
    "type": "Point"
  },
   "subscribed":{
      "user_cfd29b81f0263a380507":true,
      "user_cfd29b81f0263a3805010":true
   },
   "type":"report",
   "user_id":"user_cfd29b81f0263a380507",
   "username":"test17"
}

i want to write view who get lat, long as input key and search report within 1 miles of distance and return all report within
1 miles, can i get examples of how to overcome this task.


#2

You can’t do distance calculations directly. You would need to calculate a bounding box instead and use that for querying.

For calculating a bounding box you could e.g. code a function that determines points 1 mile north, east, south and west from your center point (and example can be found here: http://www.movable-type.co.uk/scripts/latlong.html#destPoint). Then use these points as the extremes of your bounding box.

This will lead to false positives as the bounding box will contain points that are not strictly within the radius (as the radius is round-ish). You can filter them out with e.g. like that: https://github.com/maxogden/geojson-js-utils/blob/5edaf7e12fd8eb5a5cf806d09df614fe696fa33c/geojson-utils.js#L198-L220


#3

I am reviving the topic because I guess the doubt and the tips given here do still apply to my use case.

I am using Couchbase 4.1 CE.

I have a list of objects that contain a location object with a lat and a lng.

Supposing that I want to get the nearest objects to a specified lat/lng that I would pass, I would need to create a Spatial View that I could query?

From what I have seen, I can’t query it currently with PHP SDK - neither with N1ql - so I would need to call the Couchbase REST API to get some results on the view.

Is that correct? Are there any recommendations for this approach?

Implementing the points pointed by @vmx would be done in the Spatial View itself?

Thanks


#4

Hi @ivoecpereira, @keshav_m can help you with geospatial queries using N1QL. He can also point you to other forum topics on this issue.


#5

Please see this thread.


#6

Thanks a lot.

I was able to get something working. However I have got a new question on it.

Imagine I do want to get all the items inside a specific bounding box (that I have calculated by providing a Lat/Lng/Radius to a PHP function), and I want to order the documents I receive by the highest distance.

From what I have understood that’s not possible. And loading let’s say ~500.000 (for reference only) into server memory, and sort all of them there is something totally out of reach, of course.

What do you suggest here @keshav_m?

Thanks!


#7

Hi @ivoecpereira,

You should project this expressions (acos(sin(1.3963) * sin(Lat) + cos(1.3963) * cos(Lat) * cos(Lon - (-0.6981))) * 6371) and then do ORDER BY (expression) DESC.

Then the query will ONLY SORT the qualified documents within your bounding box.

If 500K documents do qualify for your bounding box, you’ll require memory to sort it!


#8

@keshav_m but I should do that query exactly where? As I am supposed to be calling the spatial view from a REST API call from PHP, where exactly should I implement that?

Thanks a lot!


#9

Hi @ivoecpereira,

If you provide the query you’re using now (for the bounding box), I can tell exactly where.


#10

Hello again,

Sorry, I thought I had already added it here.

This is my Spatial View:

function(doc, meta)
{
  if (typeof doc._type !== 'undefined' && doc._type === 'location_object') {
    var lng = parseFloat(doc.location[0].lng);
    var lat = parseFloat(doc.location[0].lat);
    
    emit([{
       "type": "Point",
       "coordinates":[lng, lat]
    }], doc);
  }
}

My document:

{
   "title": "Location Object 1",
   "location": [
       {
           "lat": "-9.117047399999999",
           "lng": "38.7626105"
       }
   ],
   "created_by": "user_account::2",
   "updated_at": null,
   "_id": 5,
   "_type": "location_object",
   "created_at": 1474139561
}

The function I am using for creating the Bounding Box:

<?php

function getBoundingBox($lat_degrees, $lon_degrees, $distance_in_meters) {

    $distance_in_meters = $distance_in_meters * 1000;

    $radius = 6371; // of earth in kms

    // bearings - FIX   
    $due_north = deg2rad(0);
    $due_south = deg2rad(180);
    $due_east = deg2rad(90);
    $due_west = deg2rad(270);

    // convert latitude and longitude into radians 
    $lat_r = deg2rad($lat_degrees);
    $lon_r = deg2rad($lon_degrees);

    // find the northmost, southmost, eastmost and westmost corners $distance_in_miles away
    // original formula from
    // http://www.movable-type.co.uk/scripts/latlong.html

    $northmost  = asin(sin($lat_r) * cos($distance_in_meters/$radius) + cos($lat_r) * sin ($distance_in_meters/$radius) * cos($due_north));
    $southmost  = asin(sin($lat_r) * cos($distance_in_meters/$radius) + cos($lat_r) * sin ($distance_in_meters/$radius) * cos($due_south));

    $eastmost = $lon_r + atan2(sin($due_east)*sin($distance_in_meters/$radius)*cos($lat_r),cos($distance_in_meters/$radius)-sin($lat_r)*sin($lat_r));
    $westmost = $lon_r + atan2(sin($due_west)*sin($distance_in_meters/$radius)*cos($lat_r),cos($distance_in_meters/$radius)-sin($lat_r)*sin($lat_r));


    $northmost = rad2deg($northmost);
    $southmost = rad2deg($southmost);
    $eastmost = rad2deg($eastmost);
    $westmost = rad2deg($westmost);

    // sort the lat and long so that we can use them for a between query        
    if ($northmost > $southmost) { 
        $lat1 = $southmost;
        $lat2 = $northmost;

    } else {
        $lat1 = $northmost;
        $lat2 = $southmost;
    }


    if ($eastmost > $westmost) { 
        $lon1 = $westmost;
        $lon2 = $eastmost;

    } else {
        $lon1 = $eastmost;
        $lon2 = $westmost;
    }

    return [$lat1,$lat2,$lon1,$lon2];
}

$testing = getBoundingBox(-9.117, 38.762, 5000);

Thanks @keshav_m!


#11

oh… You’re using the spatial view. You can’t use this in the N1Ql query.

If you follow the direction here: http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates
You can write the N1QL query and add the distance expression for sorting.


#12

To sort by a complex expression, do the following:

SELECT some_complex_expression AS a
ORDER BY a;

#13

Hi @ivoecpereira,

Here is a python program you can get the bounding box and get the N1QL query to return the qualified geo documents. The bounding box calculation was obtained from: https://github.com/jfein/PyGeoTools/blob/master/geolocation.py

Once you see this working with your data, you can create appropriate indices.
create index i1 onbeer-sample(RADIANS(geo.lat), RADIANS(geo.lon));

import math
 
 
class GeoLocation:
    '''
    Class representing a coordinate on a sphere, most likely Earth.
    
    This class is based from the code smaple in this paper:
        http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates
        
    The owner of that website, Jan Philip Matuschek, is the full owner of 
    his intellectual property. This class is simply a Python port of his very
    useful Java code. All code written by Jan Philip Matuschek and ported by me 
    (which is all of this class) is owned by Jan Philip Matuschek.
    '''
 
 
    MIN_LAT = math.radians(-90)
    MAX_LAT = math.radians(90)
    MIN_LON = math.radians(-180)
    MAX_LON = math.radians(180)
    
    EARTH_RADIUS = 6378.1  # kilometers
    
    
    @classmethod
    def from_degrees(cls, deg_lat, deg_lon):
        rad_lat = math.radians(deg_lat)
        rad_lon = math.radians(deg_lon)
        return GeoLocation(rad_lat, rad_lon, deg_lat, deg_lon)
        
    @classmethod
    def from_radians(cls, rad_lat, rad_lon):
        deg_lat = math.degrees(rad_lat)
        deg_lon = math.degrees(rad_lon)
        return GeoLocation(rad_lat, rad_lon, deg_lat, deg_lon)
    
    
    def __init__(
            self,
            rad_lat,
            rad_lon,
            deg_lat,
            deg_lon
    ):
        self.rad_lat = float(rad_lat)
        self.rad_lon = float(rad_lon)
        self.deg_lat = float(deg_lat)
        self.deg_lon = float(deg_lon)
        self._check_bounds()
        
    def __str__(self):
        degree_sign= u'\N{DEGREE SIGN}'
        return ("({0:.4f}deg, {1:.4f}deg) = ({2:.6f}rad, {3:.6f}rad)").format(
            self.deg_lat, self.deg_lon, self.rad_lat, self.rad_lon)
        
    def _check_bounds(self):
        if (self.rad_lat < GeoLocation.MIN_LAT 
                or self.rad_lat > GeoLocation.MAX_LAT 
                or self.rad_lon < GeoLocation.MIN_LON 
                or self.rad_lon > GeoLocation.MAX_LON):
            raise Exception("Illegal arguments")
            
    def distance_to(self, other, radius=EARTH_RADIUS):
        '''
        Computes the great circle distance between this GeoLocation instance
        and the other.
        '''
        return radius * math.acos(
                math.sin(self.rad_lat) * math.sin(other.rad_lat) +
                math.cos(self.rad_lat) * 
                math.cos(other.rad_lat) * 
                math.cos(self.rad_lon - other.rad_lon)
            )
            
    def bounding_locations(self, distance, radius=EARTH_RADIUS):
        '''
        Computes the bounding coordinates of all points on the surface
        of a sphere that has a great circle distance to the point represented
        by this GeoLocation instance that is less or equal to the distance argument.
        
        Param:
            distance - the distance from the point represented by this GeoLocation
                       instance. Must be measured in the same unit as the radius
                       argument (which is kilometers by default)
            
            radius   - the radius of the sphere. defaults to Earth's radius.
            
        Returns a list of two GeoLoations - the SW corner and the NE corner - that
        represents the bounding box.
        '''
        
        if radius < 0 or distance < 0:
            raise Exception("Illegal arguments")
            
        # angular distance in radians on a great circle
        rad_dist = distance / radius
        
        min_lat = self.rad_lat - rad_dist
        max_lat = self.rad_lat + rad_dist
        
        if min_lat > GeoLocation.MIN_LAT and max_lat < GeoLocation.MAX_LAT:
            delta_lon = math.asin(math.sin(rad_dist) / math.cos(self.rad_lat))
            
            min_lon = self.rad_lon - delta_lon
            if min_lon < GeoLocation.MIN_LON:
                min_lon += 2 * math.pi
                
            max_lon = self.rad_lon + delta_lon
            if max_lon > GeoLocation.MAX_LON:
                max_lon -= 2 * math.pi
        # a pole is within the distance
        else:
            min_lat = max(min_lat, GeoLocation.MIN_LAT)
            max_lat = min(max_lat, GeoLocation.MAX_LAT)
            min_lon = GeoLocation.MIN_LON
            max_lon = GeoLocation.MAX_LON
        
        return [ GeoLocation.from_radians(min_lat, min_lon) , 
            GeoLocation.from_radians(max_lat, max_lon) ]


            
if __name__ == '__main__':
    # Test degree to radian conversion
    loc1 = GeoLocation.from_degrees(26.062951, -80.238853)
    loc2 = GeoLocation.from_radians(loc1.rad_lat, loc1.rad_lon)
    assert (loc1.rad_lat == loc2.rad_lat and loc1.rad_lon == loc2.rad_lon 
        and loc1.deg_lat == loc2.deg_lat and loc1.deg_lon == loc2.deg_lon)
    
    # Test distance between two locations
    loc1 = GeoLocation.from_degrees(26.062951, -80.238853)
    loc2 = GeoLocation.from_degrees(26.060484,-80.207268)
    assert loc1.distance_to(loc2) == loc2.distance_to(loc1)
    
    # Test bounding box
    loc = GeoLocation.from_degrees(37.61, -122.38)
    distance = 50  # 1 kilometer
    SW_loc, NE_loc = loc.bounding_locations(distance)
    print loc.distance_to(SW_loc)
    print loc.distance_to(NE_loc)
    print SW_loc
    print NE_loc
    # print SW_loc.deg_lat, SW_loc.deg_lon

    condition = (" OR " if (SW_loc.rad_lon < NE_loc.rad_lon) else " AND ")

    query = ("SELECT * FROM `beer-sample` WHERE " +
             "(RADIANS(geo.lat) >= " + str(SW_loc.rad_lat) + " and RADIANS(geo.lat) <= " + str(NE_loc.rad_lat) + ") and "
             "(RADIANS(geo.lon) >= " + str(SW_loc.rad_lon) + " and RADIANS(geo.lon) <= " + str(NE_loc.rad_lon) + ")" + condition +
             " acos(sin( " + str(loc.deg_lat) + ") * sin (geo.lat) + cos( " + str(loc.deg_lat) +  " ) " +
             " * cos(geo.lat) * cos (geo.lon - " + str(loc.deg_lon) + ")) <= "+ str(distance/6371.0) + " ;"  )

    print query

How to index this location query?
#14

Thanks a lot for your contribution! I was able to get this working in N1ql.

I already had a working query in MySQL, and it was painless to convert it to N1ql.

I will post it here as soon as I clean it up, so it could help someone who stumble here through Google.

Thanks!


#15

That’ll be great. Thank you, @ivoecpereira


#16

Hi @ivoecpereira,

You should write a guest blog about this.


#17

Hello again,

To follow up with @keshav_m suggestion, I will try this approach. I’ve converted the Class you gave me to PHP. Will only test it tomorrow in a practical case.

I will leave it here in case anyone needs it.

<?php
class GeoLocation {
    
    const MIN_LAT = -1.5707963267949;
    const MAX_LAT = 1.5707963267949;
    const MIN_LON = -3.1415926535898;
    const MAX_LON = 3.1415926535898;
    
    const EARTH_RADIUS = 6378.1; # kilometers
    
    public $rad_lat;
    public $rad_lon;
    public $deg_lat;
    public $deg_lon;
    
    public static function fromDegrees($deg_lat, $deg_lon) {
        $rad_lat = deg2rad($deg_lat);
        $rad_lon = deg2rad($deg_lon);
        return new GeoLocation($rad_lat, $rad_lon, $deg_lat, $deg_lon);
    }
    
    public static function fromRadians($rad_lat, $rad_lon) {
        $deg_lat = rad2deg($rad_lat);
        $deg_lon = rad2deg($rad_lon);
        return new GeoLocation($rad_lat, $rad_lon, $deg_lat, $deg_lon);
    }
    
    public function __construct($rad_lat, $rad_lon, $deg_lat, $deg_lon) {
        $this->rad_lat = (float) $rad_lat;
        $this->rad_lon = (float) $rad_lon;
        $this->deg_lat = (float) $deg_lat;
        $this->deg_lon = (float) $deg_lon;
        
        $this->checkBounds();
    }
    
    public function checkBounds() {
        if ($this->rad_lat < self::MIN_LAT
            || $this->rad_lat > self::MAX_LAT
            || $this->rad_lon < self::MIN_LON
            || $this->rad_lon > self::MAX_LON
        ) {
            throw new \Exception('Illegal arguments');
        }
    }
    
    public function distanceTo($other, $radius = self::EARTH_RADIUS) {
        /*
        Computes the great circle distance between this GeoLocation instance
        and the other.
        */
        return $radius * acos(
            sin($this->rad_lat) * sin($other->rad_lat) +
            cos($this->rad_lat) * 
            cos($other->rad_lat) * 
            cos($this->rad_lon - $other->rad_lon)
        );
    }
    
    public function boundingLocations($distance, $radius = self::EARTH_RADIUS) {
        /*
        Computes the bounding coordinates of all points on the surface
        of a sphere that has a great circle distance to the point represented
        by this GeoLocation instance that is less or equal to the distance argument.
        
        Param:
            distance - the distance from the point represented by this GeoLocation
                       instance. Must be measured in the same unit as the radius
                       argument (which is kilometers by default)
            
            radius   - the radius of the sphere. defaults to Earth's radius.
            
        Returns a list of two GeoLoations - the SW corner and the NE corner - that
        represents the bounding box.
        */
        
        if ($radius < 0 || $distance < 0) {
            throw new \Exception('Illegal arguments');
        }
        
        # angular distance in radians on a great circle
        $rad_dist = $distance / $radius;
        
        $min_lat = $this->rad_lat - $rad_dist;
        $max_lat = $this->rad_lat + $rad_dist;
        
        if ($min_lat > self::MIN_LAT && $max_lat < self::MAX_LAT) {
            $delta_lon = asin(sin($rad_dist) / cos($this->rad_lat));
            
            $min_lon = $this->rad_lon - $delta_lon;
            if ($min_lon < self::MIN_LON) {
                $min_lon += 2 * pi();
            }
            
            $max_lon = $this->rad_lon + $delta_lon;
            if ($max_lon > self::MAX_LON) {
                $max_lon -= 2 * pi();
            }
        } else {
            # a pole is within the distance
            $min_lat = max($min_lat, self::MIN_LAT);
            $max_lat = min($max_lat, self::MAX_LAT);
            $min_lon = self::MIN_LON;
            $max_lon = self::MAX_LON;
        }
        
        return [ self::fromRadians($min_lat, $min_lon),
            self::fromRadians($max_lat, $max_lon) ];
    }
    
}

$loc1 = GeoLocation::fromDegrees(26.062951, -80.238853);
$loc2 = GeoLocation::fromRadians($loc1->rad_lat, $loc1->rad_lon);

// http://php.net/manual/en/language.types.float.php
// Warning: Floating point precision
assert( round($loc1->rad_lat) == round($loc2->rad_lat) && round($loc1->rad_lon) == round($loc2->rad_lon)
        && round($loc1->deg_lat) == round($loc2->deg_lat) && round($loc1->deg_lon) == round($loc2->deg_lon));
        
# Test distance between two locations
$loc1 = GeoLocation::fromDegrees(26.062951, -80.238853);
$loc2 = GeoLocation::fromDegrees(26.060484,-80.207268);
assert( round($loc1->distanceTo($loc2)) == round($loc2->distanceTo($loc1)) );
    
# Test bounding box
$loc = GeoLocation::fromDegrees(37.61, -122.38);
$distance = 50; # 1 kilometer
$boundingLocations = $loc->boundingLocations($distance);
$SW_loc = $boundingLocations[0];
$NE_loc = $boundingLocations[1];
print $loc->distanceTo($SW_loc);
echo "\n";
print $loc->distanceTo($NE_loc);
echo "\n\n";
var_dump($SW_loc);
echo "\n";
var_dump($NE_loc);
echo "\n\n";
# print SW_loc->deg_lat, $SW_loc->deg_lon

if ($SW_loc->rad_lon < $NE_loc->rad_lon) {
    $condition = ' OR ';
} else {
    $condition = ' AND ';
}

$query = 'SELECT * FROM `default` WHERE (RADIANS(geo.lat) >= ' . (string) $SW_loc->rad_lat . ' and RADIANS(geo.lat) <= ' . (string) $NE_loc->rad_lat . ') and (RADIANS(geo.lon) >= ' . (string) $SW_loc->rad_lon . ' and RADIANS(geo.lon) <= ' . (string) $NE_loc->rad_lon . ') ' . $condition . ' acos(sin(' . (string) $loc->deg_lat . ') * sin (geo.lat) + cos(' . (string) $loc->deg_lat . ') * cos(geo.lat) * cos (geo.lon - ' . (string) $loc->deg_lon . '))) <= ' . (string) ($distance/6371.0) . ';';

print $query;