The Mathematics

The process for finding a match in the routes is to loop through each point on the first segment and match it with every point on the second looking for a co-location. If the two roots have been encoded in a similar way, then it could be thought that just looking at the distance between the two points we would be able judge whether they are the same.

However, in practice, this is insufficient. Points on one line are often located between the points on the other and are close enough to the route that they a match.

I keep saying we comparing two points, but in practice, what this really means is that we are judging that point ${\displaystyle P_{0}}$ against the leg of the walk from one point ${\displaystyle P_{1}}$ to the next${\displaystyle P_{2}}$.

Distance from a point to line

In order to handle this second case, we need to be able to calculate the distance from a point to a line. This is covered in great detail on this wikapedia page and the equations shown below are all taken from here.

In coordinate geometry, any point ${\displaystyle P(x, y)}$ on straight line satisfies the formula ${\displaystyle ax+by+c=0}$ where a, b and c are constants.

If we know the location of two points on the line, ${\displaystyle P_{1}=(x_{1},y_{1})}$ and ${\displaystyle P_{2}=(x_{2},y_{2})}$ then we calculate the values of the constants in the equation

$$\begin{aligned} a&=y_{2}-y_{1} \\ b&=x_{1}-x_{2} \\ c&=x_{2}y_{1}-x_{1}y_{2} \end{aligned}$$

The distance from the point ${\displaystyle P_{0}=(x_{0},y_{0})}$ to the line is given by the formula

$${\displaystyle \operatorname {distance} (ax+by+c=0,(x_{0},y_{0}))={\frac {|ax_{0}+by_{0}+c|}{\sqrt {a^{2}+b^{2}}}}.}$$

False Positives

This in itself is in sufficient. The line is not limited to the segment between ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$ but extends to infinity in both directions. This means that the distance to this line could be small but the point itself is a long way from our route.

The point ${\displaystyle X}$ on this line that is closest to ${\displaystyle P_{0}=(x_{0},y_{0})}$ has coordinates:

$${\displaystyle x={\frac {b(bx_{0}-ay_{0})-ac}{a^{2}+b^{2}}}{\text{ and }}y={\frac {a(-bx_{0}+ay_{0})-bc}{a^{2}+b^{2}}}}$$

If ${\displaystyle X}$ lies between ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$ the following equation will hold

$${\displaystyle \operatorname {distance} (P_{1},X)+\operatorname {distance} (X,P_{2}))-\operatorname {distance} (P_{1},P_{2})=0}$$

and if not then the left hand side will return a positive value equal to twice the distance from X to the nearest point defining the leg.

Fallacy

It might be tempting to thing that we can work solely with the distance from the point to the leg of the segment that it lies on. There are two problems here

The solution is to work with both approaches at the same time. i.e. distance of ${\displaystyle P_{0}}$ to points ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$, and to the line between them.