1

I need to evaluate the proximity of a Point to a LineString using MongoDB.

Because the $near operator can only compare a Point to another Point, I need to generate a polygon out of the LineString, so I can use the $within operator. The distance between the LineString and the edges of the polygon should represent the radius I want to search in, such as represented in red below:

Polygon from Linestring

What might be a useful algorithm in order to accomplish this?

Christophe Marois
  • 6,471
  • 1
  • 30
  • 32
  • I believe you are looking for a buffer function, which MongoDB does not provide, so that you buffer the linestring by a certain amount and can then use geoWithin to find points that are inside you polygon? – John Powell Aug 07 '14 at 19:28
  • I'm not really sure to understand your question, but it sounds like it, yeah! – Christophe Marois Aug 07 '14 at 19:45
  • 1
    A buffer means to grow by an equal amount in all directions, so a point would become a circle, and a line would become a polygon, as in your image above. MongoDB does not have a buffer function, so you will need to either load a spatial javascript library into MongoDB or convert you geojson outside of MongoDB. – John Powell Aug 07 '14 at 19:47

2 Answers2

3

I think much easier would be to write your own function

To find (perpendicular) distance between point and line and then creating thickness of poly-line by polygon means.

pnt line

Where:

  • P0,P1 are line endpoints
  • P is point
  • d is distance between them

Line is defined as: p(t)=P0+(P1-P0)*t where t=<0.0,1.0>

So the function should do this:

  1. create perpendicular line

    • q(t)=P+DQ*u where u=(-inf,+inf)
    • DQ is perpendicular vector to (P1-P0)

    In 2D you can obtain it easily like this (x,y) -> (y,-x). In higher dimensions use cross product with some non coplanar vectors.

  2. compute line vs. line intersection

    there are tons of stuff about this so google or solve the equation yourself here you can extract mine implementation.

  3. now after successful intersection

    just compute d as distance between P and intersection point. Do not forget that parameter t must be in range. If not (or if no intersection) then return min(|P-P0|,|P-P1|)

[hints]

t and u parameters can be obtained directly from intersection test so if the perpendicular vector to (P1-P0) is normalized to size = 1 then the abs(u) parameter of intersection point is the distance

[notes]

I am not familiar with mongodb so if you have no means to use own tests inside then this answer is of coarse obsolete.

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • +1. Nice answer. MongoDB only has basic spatial functionality, and lacks things like buffering a geometry. However, you can store Javascript functions on the server, run map reduce jobs, or run Javascript functions on the client (all with different cost/benefits). This would be easy to code up in JS. – John Powell Aug 08 '14 at 14:17
  • I have implemented the method you describe above in this [JSBin](http://jsbin.com/kalur/edit?css,js,output) – Christophe Marois Dec 15 '14 at 22:54
  • @Crunch the `u=(-inf,+inf)` means that `u ` goes from -infinity to +infinity (whole Real numbers range) range `(a,b)` means that `a,b` are not included range `` means that `a,b` are included – Spektre Mar 03 '15 at 10:03
0

Unfortunately, MongoDB provides very basic geospatial query, so you should create the buffer by your own. You can read how to do it here: Computing a polygon that surrounds a multi-point line

If you have longitude/latitude coordinates like WGS84 you must adjust this code; Read here how to calculate distance between point on a sphere https://en.wikipedia.org/wiki/Haversine_formula

Community
  • 1
  • 1
Serge
  • 2,574
  • 18
  • 26