Which points are co-linear & in sequence (i.e. which two points I am between)

Question

I have longitude and latitude of my position, and I have a list of positions that is ordered as a list of points(long/lat)) along a road. How do I find out which two points I am between?

If I just search for the two nearest points I will end up with P2 and P3 in my case in the picture. I want to know how to find out that I'm between point p1 and p2.

The list of points I will search will be database rows containing latitude and longitude so pointers to how to build the sql-query, linq-query or pseudo code, everything that points me to the best solution is welcome. I'm new to geolocation and the math around it so treat me as an newbie. ;)

(The list of points will be ordered so P1 will have an id of 1, p2 will have an id of 2 and so on. )

enter image description here

score 1 · Accepted Answer · edited May 23 '17 at 12:30

Bear in mind that what you propose might become really complex (many points under equivalent conditions) and thus delivering an accurate algorithm would require (much) more work. Taking care of simpler situations (like the one in your picture) is not so difficult; you have to include the following:

Convert latitude/longitude values into cartesian coordinates (for ease of calculations; although you might even skip this step). In this link you can get some inspiration on this front; it is in C#, but the ideas are clear anyway.
Iterate through all the available points "by couples" and check whether the point to be analysed (Mypos), falls in the line formed by them, in an intermediate position. As shown in the code below, this calculation is pretty simple and thus you don't need to do any pre-filtering (looking for closer points before).

.

Dim point1() As Double = New Double() {0, 0} 'x,y
Dim point2() As Double = New Double() {0, 3}
Dim pointToCheck() As Double = New Double() {0.05, 2}

Dim similarityRatio As Double = 0.9
Dim minValSimilarDistance As Double = 0.001
Dim similarityDistance As Double = 0.5

Dim eq1 As Double = (point2(0) - point1(0)) * (pointToCheck(1) - point1(1))
Dim eq2 As Double = (point2(1) - point1(1)) * (pointToCheck(0) - point1(0))
Dim maxVal As Double = eq1
If (eq2 > eq1) Then maxVal = eq2

Dim inLine = False
Dim isInBetween As Boolean = False

If (eq1 = eq2 OrElse (maxVal > 0 AndAlso Math.Abs(eq1 - eq2) / maxVal <= (1 - similarityRatio))) Then
    inLine = True
ElseIf (eq1 <= minValSimilarDistance AndAlso eq2 <= similarityDistance) Then
    inLine = True
ElseIf (eq2 <= minValSimilarDistance AndAlso eq1 <= similarityDistance) Then
    inLine = True
End If

If (inLine) Then
    'pointToCheck part of the line formed by point1 and point2, but not necessarily between them
    Dim insideX As Boolean = False
    If (pointToCheck(0) >= point1(0) AndAlso pointToCheck(0) <= point2(0)) Then
        insideX = True
    Else If (pointToCheck(0) >= point2(0) AndAlso pointToCheck(0) <= point1(0)) Then
        insideX = True
    End If
    if(insideX) Then
        If (pointToCheck(1) >= point1(1) AndAlso pointToCheck(1) <= point2(1)) Then
            isInBetween = True
        ElseIf (pointToCheck(1) >= point2(1) AndAlso pointToCheck(1) <= point1(1)) Then
            isInBetween = True
        End If
    End If
End If

If (isInBetween) Then
    'pointToCheck is between point1 and point2
End If

As you can see, I have included various ratios allowing you to tweak the exact conditions (the points will, most likely, not be falling exactly in the line). similarityRatio accounts for "equations" being more or less similar (that is, X and Y values not exactly fitting within the line but close enough). similarityRatio cannot deal properly with cases involving zeroes (e.g., same X or Y), this is what minValSimilarDistance and similarityDistance are for. You can tune these values or just re-define the ratios (with respect to X/Y variations between points, instead of with respect to the "equations").

score 1 · Answer 2 · answered May 27 '15 at 23:21

An equivalent solution in Scala for clarity:

def colinearAndInOrder(a: Point, b: Point, c: Point) = {

  lazy val colinear: Boolean =
    math.abs((a.lng - b.lng) * (a.lat - c.lat) - 
      (a.lng - c.lng) * (a.lat - b.lat)) <= 1e-9

  lazy val bounded: Boolean =
    ((a.lat < b.lat && b.lat < c.lat) || (a.lat > b.lat && b.lat > c.lat)) &&
      ((a.lng < b.lng && b.lng < c.lng) || (a.lng > b.lng && b.lng > c.lng))

  close(a,b) || close(b,c) || (colinear && bounded)
}

def close(a: Point, b: Point): Boolean = {
  math.abs(a.lat - b.lng) <= 1e-4 && math.abs(a.lat - b.lng) <= 1e-4
}

Which points are co-linear & in sequence (i.e. which two points I am between)

2 Answers2