Prev: need help about xcorr
Next: genrate increment vector
From: Ben on 23 Mar 2010 05:04
I am doing a project for one of my classes and I am now stuck at the implementation of a triangulation algorithm. I have to find a point of intersection for three circles with only a radius and an unknown scaling factor. The device only returns a signal strength value.

I can manually change the scaling factor until the three circles barely overlap and it is very obvious where the minimum intersection point would be but I can't figure out where it is using Matlab.

I saw some articles about taking the two circle intersection points and drawing lines to the point where three circles intersect to create an intersection point where the minimum intersection point would be. The problem is implementing that...

Does anyone have suggestions that could point me in the right direction with this?
From: Walter Roberson on 23 Mar 2010 08:09
Ben wrote:
> I am doing a project for one of my classes and I am now stuck at the
> implementation of a triangulation algorithm. I have to find a point of
> intersection for three circles with only a radius and an unknown scaling
> factor. The device only returns a signal strength value.
>
> I can manually change the scaling factor until the three circles barely
> overlap and it is very obvious where the minimum intersection point
> would be but I can't figure out where it is using Matlab.

I notice you say that you can change the scaling factor, singular,
rather than the scaling factors, plural, so is it correct that the
scaling factor is the same for all three circles? And is it also correct
that all three circles have the same radius and that the scaling factor
works the same way on all three of them?

And is it also correct that you do not know where the origins of the
three circles are? Since you say that all you have is a radius and
scaling factor and signal strength feedback?

I must admit that I am having difficulty picturing what kind of
real-life situation that this is modeling.
From: Ben on 23 Mar 2010 13:23
Yeah I did leave out a couple important points...

This is modeling a RFID system which is sending tag signal strength from 0-140 to MATLAB. I making the normalized signal strength the radius of my circles then multiplying it by a single scaling factor in order to get the circles to all touch at some points.

I also know the coordinates of the center of the circles.
From: Roger Stafford on 23 Mar 2010 14:08
"Ben " <bealey.removethis(a)utk.edu> wrote in message <hoa066$o9k$1(a)fred.mathworks.com>...
> I am doing a project for one of my classes and I am now stuck at the implementation of a triangulation algorithm. I have to find a point of intersection for three circles with only a radius and an unknown scaling factor. The device only returns a signal strength value.
>
> I can manually change the scaling factor until the three circles barely overlap and it is very obvious where the minimum intersection point would be but I can't figure out where it is using Matlab.
>
> I saw some articles about taking the two circle intersection points and drawing lines to the point where three circles intersect to create an intersection point where the minimum intersection point would be. The problem is implementing that...
>
> Does anyone have suggestions that could point me in the right direction with this?
-------------
If I understand you correctly, you know the distances to an unknown point from three locations but only to some single unknown multiplicative scale factor. In other words, you only know the ratios between the three distances. You want to locate that unknown point. Do I state the problem correctly?

I can give you a little guidance. The locus of points whose distances from two fixed points have a certain ratio is a circle. For two different pairings among your three base points that would give you two different such locus circles. All you have to do is find the intersection of these two circles.

A little algebra will allow you to write the equations of each of these circles. Then find the simultaneous solution to these equations and you have the coordinates of your unknown point. Bear in mind that in general there will be two solutions (or perhaps none.)

Doing it in matlab should then be an easy exercise.

Roger Stafford
From: Roger Stafford on 23 Mar 2010 19:16
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <hob02n$qg5$1(a)fred.mathworks.com>...
> If I understand you correctly, you know the distances to an unknown point from three locations but only to some single unknown multiplicative scale factor. In other words, you only know the ratios between the three distances. You want to locate that unknown point. Do I state the problem correctly?
>
> I can give you a little guidance. The locus of points whose distances from two fixed points have a certain ratio is a circle. For two different pairings among your three base points that would give you two different such locus circles. All you have to do is find the intersection of these two circles.
>
> A little algebra will allow you to write the equations of each of these circles. Then find the simultaneous solution to these equations and you have the coordinates of your unknown point. Bear in mind that in general there will be two solutions (or perhaps none.)
>
> Doing it in matlab should then be an easy exercise.
>
> Roger Stafford
---------
I was a bit careless in that advice I gave you, Ben. Directly finding that "simultaneous solution" I described can lead you to some very messy expressions. I should have stated things as follows. You can divide up the problem into three steps.

Step one is to write the equations of the two circles I mentioned. By a process of completion of squares you can derive from them expressions for their centers and radii.

Step two is to multiply the two equations by the appropriate values and subtract them so as to cancel out all second degree terms in the unknowns, x and y, and obtain an expression which is linear in x and y (where x and y are the coordinates of the unknown point.) This linear equation defines a straight line which will run through the two possible positions of (x,y), and it is necessarily orthogonal to the line connecting the two circles' centers. By also writing the equation of the latter line, you can then find the intersection of these two lines.

Step three is then to use Pythagoras' theorem to find out how far out in either direction along this first line you need to go to attain the proper distance from either of the two circles' centers. This will finally give you the solution to (x,y).

You can write a matlab procedure that follows these steps. If you were to try to compute the solutions all in a single pair of expressions, they would be very complicated.

Roger Stafford
 | 
Pages: 1
Prev: need help about xcorr
Next: genrate increment vector