Trilateration where we have heading instead of distance to the known points

Question

I'm trying to do a form of trilateration, where the distances between the point of interest (POI) and the anchor points are not given, but instead the heading observed from the POI to each of the points is given.

The problem is as follows:

In a 2D plane, given N towers whose locations are known as P_t1, P_t2, .. P_tn, and a point X (X_x,X_y), and headings in degrees to each of the towers relative to point X - the headings may have a slight error and it is guaranteed that all the heading shall be unique, determine the approximate/exact location of point X

Initially i was thinking all one needs are two line equations derived from two of the headers in terms of X_x and X_y, however there's no guarantee that the other N-2 equations will align with the first model.

The other thing i was thinking of was to go through all unique pairs of headings, generate a solution for X and then compute the median over all the solution points as being "solution"

Was wondering if there's a better or more robust way to solve this problem given the over determined system of equations.

Answer 1

The “standard” solution to an overdetermined set of linear equations would be a least-squares solution. Depending on what language you are working in, there is probably a library that can do that for you (for example, numpy.linalg.lstsq in Python). If you need to do it yourself, you could solve the normal equation or, if you care about numeric accuracy, dive into a rabbit hole of matrix factorization methods.

Answer 2

In my opinion the downhill simplex algorithm (aka Nelder-Mead method) would work excellently for this problem and can also deal with the fact that there are errors. Also it will converge pretty fast for this problem and is easy to implement if you know vector calculations. As starting points you can just take 3 towers. The score of a point which has to be minimized is the sum of the (squared) shortest distances to all the lines. There is plenty of literature to be found on how to calculate the distance of a point to a line. Degrees can easily be converted to a vector with trigonometric functions, so that shouldn't be a problem either.

To make it converge faster you could first calculate 3 line intersections (not all on the same line, the points can't be colinear) and take those as starting points. Although on 2nd thought I would advise against that, it could be detrimental if the points are too close together.

What would work and garantees that the points are not colinear is to calculate one intersection (x, y) and for the other two points you take (x + d, y) and (x, y + d). If you know nothing just take d = 1, otherwise set it to the average expected distance from an intersection to the actual best point.