Calculating distances with three dimensional cartesian coordinates

First brief disclaimer, I might not know all correct terms, and that kind of hinders my googling fu. If you know good examples of this problem, please direct me to those, and I’m happy to dig in to those. :slight_smile:

Problem context:
I have data dump in JSON, that contains cartesian coordinates of points of interests (POI’s). Simplified structure of one document is like this:

{
   "name": "Example Origo",
   "coords": {
      "x": 0,
      "y": 0,
      "z": 0
   }
}

Names are unique to POI’s, and coordinates tell their positioning in 3d space in relation to each other.

Problem I want to solve:
I want to be able to search & group POIs by distance relative to other POIs in same dataset.

For example, I want to search for distance of 10, and get return list of POIs that have other POIs within that 10 unit distance in coordinates.

I’m really interested if there could be query that can be ran on the spot, and it does calculations every time again. I’m also ok to run search once, and have that output saved to new collection, with some simple data structure of having POI name, and array of POI’s that are within given distance. I could then further process that list.

Bruteforce way to solve this would be iterating all documents in collection, reading coordinates from that one POI and then calculate distances to all other POIs in collection, save matches to some variable in this bruteforce program and then in the end display results. I however have feeling that MongoDB would be able to handle this inside query, and that would be so much more elegant way.

If this would be latitude/longitude, I know there are some tools in mongo specific for those. But quick glance to those didn’t seem to allow using three axis of (x,y,z). And still I would be a bit loss how to start construct query that goes through all POIs, instead of having one reference POI with coordinates, and then trying to find if there are other within range.

And if calculating distance with coordinates isn’t readily in mind, it is calculated like this:

ABS ( SQRT ( (x1 - x0)^2 + (y1 - y0)^2 + (z1-z0)^2 ) )

Where (x0, y0, z0) is one POI coordinates and (x1, y1, z1) is coordinates of another POI.

Any help and direction how to start constructing this kind of query is appreciated, and even pointers which Mongo features to try and use for it. :smiley:

let p0 be a point in R3 (actually it’s Q3) and d be a distance.
if you want to find all points p where |p-p0| < d,
you can do something like this (this is in mongo shell):

var p0 = {
   name: "some point",
   coords: {
      x: 1.2,
      y: 4.0,
      z: 3.5
   }
};
var d = 8;
db.points.aggregate([
   {
     $project: {
        distance: {
           $sqrt: {
               $add: [
                  { $pow: [ { $subtract: [ "$coords.x", p0.coords.x ] }, 2 ] },
                  { $pow: [ { $subtract: [ "$coords.y", p0.coords.y ] }, 2 ] },
                  { $pow: [ { $subtract: [ "$coords.z", p0.coords.z ] }, 2 ] }
               ]
           }
        }
     }
   },
   {
     $match: {
       distance: {
         $lt: d
       }
     }
   }
])

if you want idea for performance, you can filter (at the beginning of the aggregation) the points p where
p0.coords.x - d < p.coords.x < p0.coords.x + d
and p0.coords.y - d < p.coords.y < p0.coords.y + d
and p0.coords.z - d < p.coords.z < p0.coords.z + d

{
  $match: {
    "coords.x": {$gt: p0.coords.x - d, $lt: p0.coords.x + d},
    "coords.y": {$gt: p0.coords.y - d, $lt: p0.coords.y + d},
    "coords.z": {$gt: p0.coords.z - d, $lt: p0.coords.z + d}
  }
}

(these are the points inside the cube around the sphere)
this index can be used to achieve the performance

{
  "coords.x": 1,
  "coords.y": 1,
  "coords.z": 1
}

Good luck,
Rafael,

1 Like

Thank you @Rafael_Green, that helps me quite much! I was quite close with my tests, but didn’t realize how to use those variables, especially p0. With this, I can iterate every POI, set their coordinates to p0 and find other POIs, so my goal can be achieved.

However, I’m curious is there way to dynamically update that p0 var with new coordinates, once per POI in dataset? With regular SQL I would try to start doing some joins, but not sure how something similar can be achieved with mongo, if possible at all.

try this:

db.points.aggregate([
   {
     $match:
       {
         /* your condition for POI */
       }
   },
   {
      $lookup:
         {
           from: "points",
           let: { x: "$coords.x", y: "$coords.y",   z: "$coords.z"},
           pipeline: [
             {
               $project: {
                  distance: {
                     $sqrt: {
                         $add: [
                            { $pow: [ { $subtract: [ "$coords.x", "$$x" ] }, 2 ] },
                            { $pow: [ { $subtract: [ "$coords.y", "$$y" ] }, 2 ] },
                            { $pow: [ { $subtract: [ "$coords.z", "$$z" ] }, 2 ] }
                         ]
                     }
                  }
               }
             },
             {
               $match: {
                 distance: {
                   $lt: d
                 }
               }
             }
           ],
           as: "points_in_sphere"
         }
    }
])
2 Likes

Thank you @Rafael_Green, this was spot on. :slight_smile: I didn’t figure out $lookup and pipeline on my own, but this seems to be in correct direction. I knew that there is elegant solution, and you were able to show it. :slight_smile:

I have some reading to do about $match and how I can do some further matching/filtering to as: "points_in_sphere" result, but even if this is all I get done in Mongo, it is really good. :smiley:

This once again shows that best way to learn new things is to try solving real problems that matter to you, then your mind is ready to learn. :grinning_face_with_smiling_eyes:

2 Likes

This topic was automatically closed 5 days after the last reply. New replies are no longer allowed.