1

I am trying to use trilateration in a program to simulate how it would be in real life. I have 3 transmitters which send out a signal that gets weaker after each square that the signal moves. I am using a 2D array and code that generates a crude circle of numbers. This shows one of the transmitters

00000000000000000000
00000000000000000000
00000000000000000000
00000000001000000000
00000000112110000000
00000001223221000000
00000001234321000000
00000012344432100000
00000001234321000000
00000001223221000000
00000000112110000000
00000000001000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

My question is, how do I find the location of the receiver in the grid? How do I find where all three circles intersect? I tried setting the equations of the circles equal to each other and solving but that didn't give me anything, it gave me imaginary numbers.

I can also edit the code to make the circles unfilled if that helps. The radius of each circle can be changed

The signal strength of each transmitter is known in advance by the receiver and the strengths can also be changed (in the 100, 200, or 300 range or any other range)

4

1 回答 1

0

You basically have 2 problems

  1. Finding the location of the transmitters
  2. Calculating the intersection

Point 1:

Point 1 can be solved by checking specific points in the grid in a brute force manner. However there are a couple of optimalisations possible while trying to find the first. As soon as you find one, you can make educated guesses about the locations of the others based on the radius of the transmitter you just found and the ones you need to find.

I would recommend probing the grid on intervals that are close to that of the biggest known radius. Assuming all transmitters are fully within the grid you can probe as like in the following figure (assuming the biggest radius you have is 5) - A's mark the probing points:

00000000000000000000
00000000000000000000
00000000000000000000
00000000001000000000
0000A00011211A000000
00000001223221000000
00000001234321000000
00000012344432100000
00000001234321000000
00000001A23221000A00
00000000112110000000
00000000001000000000
00000000000000000000
00000000000000000000
0000A00000000A000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000A00000000A00

With this you could probe your current grid with 8 probes tops. This can be reduced further with some extra checks when it comes to distance to the edges of your grid. But in your case you would notice that your third probing point falls within a radius. From there on you can break off the probing and look for the center of the found transmitter.

Now that you have at least 1 center of a transmitter found, you can make educated guesses about the location of the other transmitters since you know the ranges of each transmitter and you have the knowlegde that the distance to the next transmitter will be less than the range of the biggest + the smallest range. Again you can probe around at decent intervals within your grid to find the second transmitter fast. Again calculate the exact center of your second transmitter.

The third transmitter is easy to calculate. Calculate the point that is at the center of the line between the 2 found transmitters (easy to do in a coordinate system or in a grid). The missing point should be on the either side of the imaginary line you've drawn between the 2 found transmitters at a maximum distance of the transmitter's range you haven't found yet from the center point of that line.

Point 2:

The answer can be found in this post

An alternative could be the TULIP Algorithm

于 2013-05-27T18:00:50.827 回答