Orthogonal Projection Method

Today, we’ll see how to find the intersection of 2 lines using orthogonal vectors. This is key to understanding the collaborative method of localization.

Imagine we have 2 lines that intersect.

These lines are assumed to go on in infinity. All we know about these lines is their starting point and what direction they go in. In our example, the starting points are x1 and x2, and the direction is given by v1 and v2, respectively. First, we find the vector that goes from x1 to x2. We will call this vector vd.

Next, we project this vector vd onto the line starting at x1. The projection becomes the new x1.

We notice that the new x1 is closer to our point of intersection than the old x1. The points x1 and x2 should be seen as estimates of the point of intersection. As we keep repeating this process, our estimates will get better and better:

Now, x2 is almost at the point of intersection. With another 2 rounds through this cycle, we should be able to estimate the intersection down to +/- 0.001 units. When the length of vd (the distance between x1 and x2) becomes small enough, we stop the process.

We can use this for lines that intersect in 3D space too. Here’s a picture.

A closeup shows the two estimates getting more and more refined.

These pictures come from a testbench I set up in MATLAB. Here’s the text report.

Initial

3.6228 2.1775 1.9881

Estimate

3.6228 2.1775 1.9881

Bias=1.627e-030

Bias is the difference between the actual intersection and my estimation.

As you can see, it’s pretty accurate, and it will work for any number of lines, too:

This is a simple way to collaboratively find the intersection of two points. All a cluster needs is a point on a neighboring line, and it can then project it onto its line. It can then pass its projected point onto the next line. The only problem is that when the lines don’t intersect, you will end up with something called ring convergence. In the picture above, the lines intersect perfectly, so the method will converge to a single point. However, with ring convergence, the method will converge to a ring of points:

As you can see, there is a ring convergence with 3 points.

This is the challenging part of the process, and I’m working on applying techniques to deal with this issue. Once I can get my simulator to account for this and converge to a single point, I’ll make a new post.