Talk:True-range multilateration/Archive 1

This is an archive of past discussions about True-range multilateration. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

2D/3D cofusion and general coordinates

In the introduction it seems to imply that 'trilateration' means only finding a point in three dimensions, and then in the section on errors it switches to talking about 2D without saying. Also, I think if it won't end up in a page long expression someone should spend a lazy afternoon solving the problem for general coordinates. It's the true the solution given can be transformed, but it would involve some pretty messy stuff with rotation matrices. UnexpectedTiger (talk) 10:23, 28 August 2009 (UTC)

Not

"Trilateration is most commonly used in GPS applications, where the distances from satellite transmitters (the reference points) are measured by a receiver (the subject point)."

Not precisely. What are measured are timing differences, so we are really intersecting hyperboloids of revolution. It would be trilateration if we already knew the exact time; but that's one of the things we are solving for. -- The Anome 11:59, 27 Aug 2004 (UTC)

locations at sea

For example, if the subject is known to be on land, or on the surface of the Earth, and one of the candidate locations is at sea or in space, that point may be disregarded.

Why the locations at sea are disregarded? A subject can be at sea or land at any given time.--Assu 14:01, 29 Dec 2004 (UTC)

At any time subject knows where he is. If one of the candidate points is on land and the other one is at sea, and the subject is on land - he can easily pick the correct point from the two. It works the other way as well. Furthermore, if the subject knows his approximate position from previous oservations, he can make a pick as well. Kender 00:46, 25 January 2006 (UTC)

C++ to do 2D trilateration

Just hand-derived this. It seems to work and might be useful to add to the article.

// Precondition: one center point (p1/p2/p3) must not be colinear with the other two.
Point Trilaterate(const Point &p1, float d1, const Point &p2, float d2, const Point &p3, float d3)
{
	double i1=p1.x,i2=p2.x,i3=p3.x;
	double j1=p1.y,j2=p2.y,j3=p3.y;
	double x,y;
~~
	x = (((2*j3-2*j2)*((d1*d1-d2*d2)+(i2*i2-i1*i1)+(j2*j2-j1*j1)) - (2*j2-2*j1)*((d2*d2-d3*d3)+(i3*i3-i2*i2)+(j3*j3-j2*j2)))/
		((2*i2-2*i3)*(2*j2-2*j1)-(2*i1-2*i2)*(2*j3-2*j2)));
	y = ((d1*d1-d2*d2)+(i2*i2-i1*i1)+(j2*j2-j1*j1)+x*(2*i1-2*i2))/(2*j2-2*j1);

	return Point(x,y);
}

Hey, this is really great (and pretty helpful), have you thought of adding it to the "List of Algorithms"? 75.153.121.178 (talk) 04:39, 31 October 2008 (UTC)

Math error?

I'm no math wizard, but shouldn't the last term of the equation for y be:

${\frac {(r_{1}^{2}-r_{2}^{2}+d^{2})^{2}}{8d^{2}j}}$

The equation given didn't spit back the expected results for me, but using 8 instead of 4 in the denominator yields the expected result. I'm not confident enough in my algebra to change the actual article based on just my conclusions, so if someone else checks my work and finds it to be right please fix this on the main article.

I checked the formulas and all are rights —Preceding unsigned comment added by 62.101.100.5 (talk) 14:34, 11 March 2009 (UTC)

Merge

Note: following all the discussion below, I have clarified both Trilateration and Multilateration articles to hopefully address the points below and remove the need for any merging. If the original proposer for the merge, Frelke, is happy with the changes, I suggest the merge tag is removed from the articles --Paul 18:48, 25 January 2006 (UTC)

Just done it. Are we all happy ? Frelke 20:45, 25 January 2006 (UTC)

Yep! It doesn't seem to be confusing any more. Kender 03:47, 26 January 2006 (UTC)

Phew! --Paul 11:32, 26 January 2006 (UTC)

I am proposing to merge this page with multilateration, it being the more general case. I think that this article is actually the better article and so would intend to keep the vast majority of it.— Preceding unsigned comment added by Frelke (talk • contribs) 07:40, 19 January 2006 (UTC)

Agree

Strong agree Frelke 07:40, 19 January 2006 (UTC)
I agree but I'm unsure whether to move it to multilateration or keep it at trilateration. The latter is more familiar to laymen while the former is more used in research papers and such. Deco 08:27, 19 January 2006 (UTC)
Agree. This will clarify discussion of the remainer of the issues. I don't know which one should be the main article, but do note for interest that the Encyclopædia Britannica has an article for trilateration, but not for multilateration. --SC 21:47, 19 January 2006 (UTC)

Disagree

Following the discussions in this section, I now change my vote to disagree as it seems the two concepts are better kept distinct, although I do think we should keep a "See also" in each article, linking to the other. --Paul 12:27, 25 January 2006 (UTC)
I did agree at some point. I've changed my mind. But please stop the confusion. Somebody draws a picture for the TOA positioning, which is rightfully called trilateration, but then talks about the hyperbolic systems and intersection of two hyperboloids. We have to figure out whether tri- and multi-lateration and hyperbolic positioning are the same things. Which ones are TOA and which ones are TDOA? Who and why have coined the term "multilateration", and what sense does it make at all? Any takers? Kender 07:19, 23 January 2006 (UTC) Stanford, CA

See my comments below in "Multilateration vs. Triangulation" Paul 11:47, 23 January 2006 (UTC)

The first picture at the top-right of the page is wrong. The picture shows a particular case where there is a solution with z=0. —Preceding unsigned comment added by 62.101.100.5 (talk) 14:02, 11 March 2009 (UTC)

Discussion on Multilateration vs. Trilateration

It's probably worth trying to come to some agreed position on the relationship between multilateration and trilateration before merging the two articles. To that end, I suggest we use this section. Here is my input for a start! I think points of initial agreement are that "trilateration" normally means using TOA and three sites; similarly "multilateration" normally means three or more sites using TDOA. Also, hyperbolic positioning clearly refers to the use of TDOA and is ambiguous regarding the number of sites. Also, both terms are in common usage (Google on either). The issue really comes down to: "is trilateration synonymous with TOA and multilateration with TDOA, or is trilateration synonymous with 3 sites and multilateration synonymous with multiple sites?". If we can resolve that, then the problem is resolved. It is clear that in normal use, "multi" is used as the general case of "tri" - eg. "trilateral agreement", "multilateral agreement". By extension, it seems illogical to describe a system with more than 3 sites using TOA as "trilateration", or (to a lesser extent) a system with exactly 3 sites as "multilateration". It also seems clear to me that even given the usual definitions of trilateration (3 sites, TOA) and multilateration (multiple sites, TDOA), the two approaches are mathematically equivalent and hence the same thing. For instance, if my classical trilateration system measures three distances, d1, d2, d3 to computer the location by the intersection of three circles, I could equally well solve the problem by taking (d2-d1) and (d2-d3) and solving for the intersection of the two resulting hyperbolae. It's simply a matter of how I choose to code up the algorithm - to the end user, nothing is different. My personal opinion is that we should explicitly address this confusion by structuring the article as I recommend below. Within the "Definition" section we could state that the most common usage of trilateration is in the context of TOA measurements, and the most common usage of multilateration is in the context of TDOA measurements. Comments? Paul 11:47, 23 January 2006 (UTC)

Re: "it seems illogical to describe a system with more than 3 sites using TOA as "trilateration". Is this really the case? Is Triangulation only triangulation when 3 angles are in use? --SC 21:00, 24 January 2006 (UTC)

Most TOA systems, deployed to date, use more then 3 sites for position fixing. In the perfect world 3 would be enough, but in the real world TOA is estimated with errors, which are caused by phenomena such as clock drifts, unknown clock biases and unknown propagation parameters. In a 2-D case with no errors in a system with 4 TOA the LOP circles would intersect in one point, and the system would be overdefined. However, in the real 2-D case with errors all 4 LOP circles normally do not intersect at one point, because errors are different for each TOA, and they would not necessarily cancel. The user would use the least-squares method (may be with a Kalman filter) to estimate her position, and the more TOAs she gets – the more accurate is her estimate. The most prominent example is the GPS, which is a TOA system, where user typically sees 5-12 satellites at the same time.

Adding to the confusion:

To make position fix in 3-D one needs 4 TOA in the general case.
One can do hyperbolic positioning with just three sites, which are arranged in three distinct pairs.

So, here’s my take on resolving this confusion:

Trilateration – TOA position fixing with any number of sites. We call it tri-lateration, because 3 is the minimum number of sites for the 2-D case.
Hyperbolic – TDOA position fixing with any number of sites.
Multilateration – stillborn and confusing term. No wonder that Britannica doesn’t have it. We should just warn the readers.

Kender 21:59, 24 January 2006 (UTC) Stanford, CA

To correct something above - you *can* do 2D hyperbolic positioning with 3 sites, as you you get 2 hyperboloids. However, you *can't* regard them as three distinct pairs as the TDOA of the third pair is always dependent on that from the other two. However, to describe multilateration as a "stillborn and confusing term" is utterly wrong. It may not be a term that *you* are familiar with, or used in whatever your area of expertise is, but it is in widespread use in the area of surveillance systems. Just Google and see. Hyperbolic positioning is never used in this context - even though it is describing the same concept - so I might equally well describe that as "stillborn and confusing". Whether Britannica uses it, or not, is immaterial - Wikipedia already has many more articles than Britannica and so this should not be the measure of what is included. The surveillance literature deos use the term, and that is a more important measure than Britannica (encyclopedias should never be regarded as primary sources of information). Given the obvious different usage of terms in different areas here, I suggest we stick with my suggestion below and simply state which domains most commonly use each term. Using emotive language like above is just inserting personal prejudices into a factual article. Incidentally, a large part of my day job is working with multilateration systems. They are in widespread use in civil ATC and military surveillance and are always referred to as multilateration. I'm therefore arguing this from a position of current and professional knowledge. Once again, I suggest we use my structure below and can use the "definition" and "example uses" sections to indicate which terms are in common use in each domains. Without further comment on whether we believe that domain is correct or not. Paul 06:38, 25 January 2006 (UTC)

I have also searched for "multilateration" on the IEEE site, and got 46 hits ("trilateration" 25, "hyperbolic position" 9). They seem to employ Paul's definition of multilateration. So, I take "stillborn" back. But I keep the "confusing". We should not merge the articles, and add the phrase "Mutilateration, which is based on TDOA measurements, should not be confused with trilateration, which is based on TOA measurements." to the multilateration article and remove the references to the TOA systems (such as GPS and Galileo). By the way, I work with GPS, Loran and Galileo, and, as you can see, I've never encountered the term "multilateration", so it could quite specific to the surveillance area. Kender 09:09, 25 January 2006 (UTC)

I agree with Kender - and have now changed my vote above to disagree. We should just aim to clarify both articles in light of the discussions above, and ensure the two cross-reference each other. --Paul 12:29, 25 January 2006 (UTC)

Incidentally, if we can't resolve this issue over the relation between trilateration and multilateration, I propose we abandon the proposal to merge the two articles, but simply include a "see also" at the bottom of each article. It seems that there are only three of us interested in a merge anyway... Paul 06:58, 25 January 2006 (UTC)

Proposal for Structure of Merged Articles

I propose that the two articles are merged as follows:

Definition (define multilateration, trilateration)
Principle of operation
- Reciprocity (discussion of equivalence of multiple receivers and one transmitter, and vice versa)
- Time of Arrival
  - Description of approach
  - Mathematics of estimation using TOA (based on existing trilateration article, but perhaps in 3D rather than 2D)
- Time Difference of Arrival
  - Description of approach
  - Mathematics of estimation using TDOA (based on [1])
- Phase Difference
  - Brief mention that this is equivalent to TDOA for narrowband sources
- Multilateration accuracy (merge existing section of same name, and error model in trilateration)
Example applications
See also
External links

Paul 12:08, 19 January 2006 (UTC)

Propose link structures as follows:

Main page as Multilateration
Redirect Trilateration to Multilateration

Frelke 23:04, 19 January 2006 (UTC)

Separating Math from Measurement

I would argue that the terms trilateration and multilateration refer to the mathematical techniques used to solve for position using range or distance data - regardless of how these distances are measured. For example, what do you call the technique when it is performed with distances provided by laser range finders? With these types of measurements the concepts of TDOA and TOA are not applicable but the terms trilateration and multilateration are still used. My opinion is that multilateration is merely an extension of trilateration from the 2D case to the 3D case (as well as to situations where the localisation problem is over constrained). In my experience, these terms refer to different versions of the same technique that uses the Pythagorean theorem to form a set of non-linear equations. I think that the terms TOA and TDOA are only relevant when discussing particular positioning systems that use the time-of-flight of signals to measure distances (which includes GPS and ultrasound based systems). --Michael 17:27, 21 April 2006 (UTC)

Trilateration as described in the article can not be used for GPS purposes

This text was first put in the main article, but it was considered odd and therefore removed.

Additional, if the description of trilateration in the main article is correct, trilateration can not be used for GPS. A GPS clock (quartz clock) can be used for TDOA (Time Difference Of Arrival), but can not be used for TOA (Time Of Arrival) calculations. Trilateration as described above needs a better clock than the quartz clock available in a gps receiver. Pseudorange calculation [2][3](Pseudo-Range Navigation Solution Example), needs only a clock good enough to determine the TDOA between the different signals to calculate the position the actual time is not used. For Pseudorange calculations the signals of four satelites are needed, or the signal of tree satelites and a known hight is needed.

Comment: Only after a GPS device has made a fix and knows what it's location is, can it determine what the distances to the satellietes is. The reception of 3 satellietes allone is not enough to determine location or distances.

The quartz clock.
A clock drift of only one second a year will result in an error af about 10 meters/second so after a minute the error is as large as 600 meters. A clock drift of one second a week (more realistic) will result in 500 meters/second, this is about 100 miles per hour. This is often more than the speed we are traveling in. So if the clock can not be corrected very often, it can not be used for the positioning because the error would be larger than if the GPS device would just 'stick' to the last correct position. The clock is used for measuring the Time Difference Off Arrival (TDOA) and the accuracy of the clock is still importent, but the drift is not a problem. Crazy Software Productions 11:31, 5 September 2007 (UTC)

Why "Z" ?

Hello, I've been reading through the article because i wanted to know more about his technique. The explanatory calculus seems too complicated using 3coordinated when the article excplicitly says it is for 2D (x & y) and that z=0, would removing the Z make things clearer and more understandable ? 85.168.232.38 (talk) 03:40, 7 March 2008 (UTC)

I understand your doubts. It is not clear in article why we use z=0. I can't explain you why, but I can tell you that consideration of 3D centers of spheres with z=0 is different than considering 2D centers of circles - When 3D then solutions is 3D. When 2D then solution is in 2D:

When we have 3 spheres (3D) then we have: no solution (usually error in measurement) or one solution (very rare) or two solutions. In case of two solutions there must be used some technique for eliminating one of them (for example when we have three GPS measurement from three satellites then we have two points as the solution: one point is on the earth (good), other is beyond GPS satellites orbit (wrong or we are flying to moon))
When we have 3 circles (2D) then we have: no solution or one solution.
When we have 2 spheres (3D) then we have: no solution or one solution or infinitely more pints in solution
When we have 2 circles (2D) then we have: no solution (no intersection) or one solution (touch each other) or two solutions (two intersections).

As you see considering 3D centers of spheres with z=0 is different than considering 2D centers of circles in this case. CoperNick (talk) 08:02, 1 December 2008 (UTC)

Trilateration is certainly a 3 dimensional problem. The choice of z=0 is for simplification of the 3 dimensional problem, not a conversion to a 2 dimensional problem. I think the solution provided is straightforward and concise because of the simplification provided by choosing z=0. RHB100 (talk) 21:49, 11 February 2010 (UTC)

Equations including the error measurement?

This article has the equations for when all distances are precise, but what are the equations for finding the centre, shape, and size of the solution when all distances have error measurements? Ojw (talk) 14:45, 15 October 2009 (UTC)

The question you are asking is beyond the scope of the article and involves a considerably more difficult problem. RHB100 (talk) 21:35, 11 February 2010 (UTC)

Not a good figure

Standing at B, you want to know your location relative to the reference points P1, P2, and P3 on a 2D plane. Measuring r1 narrows your position down to a circle. Next, measuring r2 narrows it down to two points, A and B. A third measurement, r3, gives your coordinates at B. A fourth measurement could also be made to reduce and estimate error.

I think the existing illustration, Image:Trilateration.svg, is very misleading. It looks like the center P3 is exactly "below" (same first coordinate as) the points A and B. This corresponds to a special case where the parameter i is equal to the first coordinate x_solution of the two solutions. I think the illustration should show the general case. If one makes the radii of all balls bigger, the two solution points will not fall in the xy plane, but their common projection onto that plane could be shown easily. /JeppeSN (talk) 18:04, 10 March 2009 (UTC)

The figure has been updated. RHB100 (talk) 21:32, 11 February 2010 (UTC)

Another Figure Problem

The 2d figure shows three circles and the "intersections" is labeled as the area where the 3 all overlap. In a good introductory figure I think there should be no error and the intersection would be the one point that all the edges of the circles meet; There is no mention of error in this section. I think the circles should be moved so that the intersection exists at only one point. Also the text refers to a plane and spheres, shouldn't it say circles instead of spheres? If a figure later in the article intends to show error in the r measurements, this error would likely be a plus or minus type error best illustrated as 3 circles drawn with error bands instead of lines. The error bands could still meet in one point instead of 3, and the intersection would be within the error band overlap area. Now can you see how the figure is currently saying that the r measurements are "less than" some number instead of "equaling" some number? Broecher (talk) 02:33, 29 April 2010 (UTC)

I actually think the previous picture (shown above) was much better. More professional look, all circles intersecting in one point. The comment above about the non-general case is valid, but can be met by stating that the coice of coordinate system can be based on the known points. The result can then be transformed into the required coordinate system. The caption would need to reflect that and talk about spheres. Cartesian coordinates are not very suitable anyway, since the application is mainly in spherical coordinates. −Woodstone (talk) 05:34, 29 April 2010 (UTC)

Snellus plaque and work on trilateration

A verification that the plaque on Snellus home is specifically for trilateration not Snell's Law or other work by Snellus. An English translation of the plaque is needed. A description of the plaque is needed since the photo does not provide adequate clarity. RHB100 (talk) 22:13, 8 February 2010 (UTC)

Also a verification that Snellus was the first to solve the trilateration problem is needed. RHB100 (talk) 22:13, 8 February 2010 (UTC)

The plaque:

hier woonde

Willebrord Snel van Royen

(Snellius 1580-1626)

Op deze plaats bepaalde hij omstreeks 1615 als eerste in de geschiedenis van de landmeetkunde een punt door achterwaartse insnijding.

Pieterskerk Stadhuis hooglandsekerk

Translated

Here lived

Willebrord Snel van Royen

(Snellius 1580-1626)

At this place he determined around 1615 for the first time in history of country geometry a point by backwards intersection.

Sint Peters churh Townhall 'hooglandse'-church (High ground church).

In the translation the order of words is preserved as much as possible.

Crazy Software Productions (talk) 19:09, 30 April 2010 (UTC)

Definition of trilateration should conform to method of solution

Trilateration is a method for determining the intersections of three sphere surfaces given the centers and radii of the three spheres.

Above is the definition which I say should be used for trilateration and it was the definition that was used until Woodstong started changing it. It is simple, straightforward and to the point. It is in conformance with the method of solution that is provided.

Woodstone has claimed that trilateration is the process of deriving the position of a point from the distances to points of known location.

This is vague, ambiguous, and does not conform to the method of solution in the article. This appears to be a made up definition inspired by vandalism.

RHB100 (talk) 19:40, 11 April 2010 (UTC)

You might have a look at this, stating

"A node N has determined the distances from itself to each of three (or more) other nodes A, B, C, and so on. The other nodes' geographic locations (coordinates) are known ... The trilateration problem is to find the coordinates of node N ... from the given information. A complicating factor is that the known nodes' coordinates and distances typically include measurement errors. Two methods of solving the trilateration problem are nonlinear least squares and circle intersections with clustering."

−Woodstone (talk) 04:35, 12 April 2010 (UTC)

This paper referred to above appears to be a two dimensional application and in that sense is less comprehensive than the Wikipedia trilateration article. This paper does not make any reference to Wikipedia and Wikipedia should not change the definition of trilateration because of this paper. The most Wikipedia should do is perhaps make a brief mention of a different usage of trilateration in other papers. It is important that the Wikipedia definition of trilateration conform to the problem solved in the Wikipedia article. RHB100 (talk) 19:13, 12 April 2010 (UTC)

One other point should be made with regard to links. There is a link to the Wikipedia article on the sphere. This article on the sphere adequately covers the sphere surface, radius, and center. We do not need additional links to the article on surfaces, the article on radius, or the article on centers. The article on surfaces considers surfaces as a topological concept. This serves more to distract and confuse the reader than for enlightenment. Similar remarks could be made with regard to the articles on radius and center. Therefore we need only the link to the sphere. RHB100 (talk) 19:38, 12 April 2010 (UTC)

The definition of trilateration that Woodstone has recently (01:47, 7 May 2010) forced upon us is not a rephrase of the source provided as he claims. It is a completely new definition that has practically nothing to do with the source provided. It is something that he has made up and appears to be deliberately designed to confuse. It is vague, confusing, and ambiguous. It certainly does not conform to the problem that is solved. Woodstone appears to be determined to engage in vandalism. There are some of us who have labored to make trilateration an interesting and useful article for the readers. Now we have this vandal, Woodstone, who attempts to ruin everything. RHB100 (talk) 20:29, 7 May 2010 (UTC)

I resent being called a vandal. That does not enable a serious discussion. My intentions are fully serious. I added a very respectable source that backs up my understanding of the concept. Instead, you narrow down the subject to one specific solution method for a basic case. The heading here says "definition ... should conform to method of solution". Yes, but it's the other way around: "method of solution ... should conform to definition". You cannot change the definition of a concept, just because the article describes only a part of it. You do not cite a source for your interpretation. I have a perfect one for mine. My rephrasing is definitely a valid reflection of the source. But if you insist on a closer one, I will do that. Trilateration is an originally geodetic process, in which relative locations of points are determined by measurement of their distances. If some points are known, other ones can be derived. The intersection of spheres (circles) plays a role in the algorithms, but is not the whole thing. By the way, my definition in the article was the one before you started restricting it to your liking. −Woodstone (talk) 00:31, 8 May 2010 (UTC)

Woodstone has no source for his vague, ambiguous, and confusing remarks. He makes up his writing. The sentence, "The remainder of this article describes a method for the simplest case of determining the intersections of three sphere surfaces given the centers and radii of the three spheres." has no source. It is just Woodstone's idiotic nonsense which has no basis in fact. RHB100 (talk) 04:20, 8 May 2010 (UTC)

What exactly is vague in that phrase? It is the very content you want to be the lead section. Do you agree that determining the intersection of 3 spheres is a special case of determining the relative positions of points based on their distances? −Woodstone (talk) 07:02, 8 May 2010 (UTC)

Well I think the first paragraph should tell what is in the article even if it does not define trilateration. In defining trilateration methods, we must say that they include both spheres and triangles. A few other editing changes may eliminate the vagueness while leaving most of this definition. I do think it may be possible to work out our differences. RHB100 (talk) 21:38, 8 May 2010 (UTC)

Starting by talking about triangles has the benefit of explaining the word. A trilateral is another word for triangle (compare quadrilateral), used in several branches of science. It shifts thinking about the same triangle from angles to sides (compare lateral=sideways). In 3D this would become a tetrahedron as the most basic form, bounded by four adjoining triangles. A tetrahedron is fully defined (apart from reflection) by its side lengths. The most elementary problem is posed by knowing the location of 3 corners of a tetrahedron, plus their distances to the fourth corner and then computing the location of the fourth corner. You will readily see that this is an equivalent problem to the intersection of three spheres of known radius around the first three corners. So yes, it involves triangles or spheres, but the name is reminiscent of triangles, so that is the best choice for the first definition line. I think we should use the general definition as primary meaning. It is justified to explain in detail only the most fundamental case (3 spheres as is), on which more complicated cases are based. −Woodstone (talk) 04:55, 9 May 2010 (UTC)

As I recall a tetrahedron has 4 triangular faces, 4 vertices, and 6 edges. I understand that if you know the location of 3 vertices and the distance from each of these vertices to the fourth vertex, you could regard these distances as the radii of 3 spheres. You could then compute the intersections of these 3 sphere surfaces by the methods discussed in the article. One of the intersections would be the fourth vertex of the tetrahedron. The other intersection would define the fourth vertex of another tetrahedron which has the same distances from the first three but in a different direction. RHB100 (talk) 20:40, 10 May 2010 (UTC)

So on the basis of this and to explain the etymology of trilateration better you want to change "geometry of spheres or triangles" to "geometry of triangles". Is that what you want to do? RHB100 (talk) 20:49, 10 May 2010 (UTC)

That is right. The definition can be fully expressed in triangles. It explains the word. The symmetry of the solution is indeed easy to see that way. The spheres are part of a particular way of looking at the problem and can be stated after the definition. We can point out the equivalence. −Woodstone (talk) 22:41, 10 May 2010 (UTC)

I think the sentence "Trilateration is mainly used in surveying and navigation, including global positioning systems (GPS)." should be moved to the application section. RHB100 (talk) 20:12, 10 May 2010 (UTC)

It is usual that the lead not only contains the definition, but also a summary of the content. So application and how many reference points are needed belongs there as well. −Woodstone (talk) 22:41, 10 May 2010 (UTC)

Well the applications certainly do not form a significant part of the contents. There is only a single sentence in the applications section, so that is certainly not enough to justify inclusion in a summary. RHB100 (talk) 23:42, 10 May 2010 (UTC)

We should consider that section a stub, for expansion later. Information on application ought to be there. −Woodstone (talk) 03:22, 11 May 2010 (UTC)

What is it that should be in the Application section other than surveying and navigation based on current knowledge of the uses of trilateration? RHB100 (talk) 19:45, 11 May 2010 (UTC)

I think something of the history could be added. Who started applying it. How is the relative usage frequency developing compared to triangulation. What made it possible (laser, gps). I'm personally not much of a historian and am not going to dig into this. A single person does not have to make an article complete. That's the beauty of WP, other people may come in and add things. −Woodstone (talk) 02:13, 12 May 2010 (UTC)

More than 3 points

Another point. We may want to add some information on errors and redundancy. Using more than 3 (in 3D) reference points leads to an overdetermined system. Possible methods to reconcile are:

one dimensional goal seek over clock error (RHB100's favorite); only for 4 points
newton raphson, with clock error variable; only for 4 points; perhaps not always stable
clustering (mentioned higher up); several combinations of 3 points will lead to a cluster around the intended solution and a few points scattered over space (the reflections); difficult to generalise
least squares plus newton raphson; probably the most common
what else?

Or do you think it's better to expand the sections in GPS dealing with that. −Woodstone (talk) 02:13, 12 May 2010 (UTC)

I made a minor upgrade to the Application leaving the rest unchanged. I am reasonably well satisfied with the article as it is right now. There are probably ways that it could be improved, but as far as I am concerned, it is good enough for now. RHB100 (talk) 19:06, 12 May 2010 (UTC)

Wouldn't Multilateration be the "solution" for an overdetermind system? I've never managed to get a good hold on why Multilateration is so strongly connected to TDOA on wikipedia, it doesn't make any sense to me... Haakoo (talk) 09:05, 7 June 2010 (UTC)

Simplified solution without extra assumptions

Because I have not contributed to other articles, I did not dare replace most of the article; I only added a short version as an alternative. The current solution is unnecessarily complex and hard to follow, and I think something like below would be much clearer. Since there have been no opinions on this at all, I'm really inclined to just go ahead and edit the article.

Note that this solution is applicable to any 3D coordinates. No trigonometric functions are needed, only addition, substraction, multiplication, division and square root.

The method uses three-component vectors, their Euclidean norm, and dot and cross products:

{\bar {a}}=(x_{a},\ y_{a},\ z_{a})

\lVert {\bar {a}}\rVert ={\sqrt {x_{a}^{2}+y_{a}^{2}+z_{a}^{2}}}

{\bar {a}}\cdot {\bar {b}}=x_{a}x_{b}+y_{a}y_{b}+z_{a}z_{b}

{\bar {a}}\times {\bar {b}}=(y_{a}z_{b}-z_{a}y_{b},\ z_{a}x_{b}-x_{a}z_{b},\ x_{a}y_{b}-y_{a}x_{b})

These are of course described in detail elsewhere in Wikipedia. Notation is not important, but for the sake of clarity, bar ( ${\bar {p}}$ ) indicates any vector, and hat ( ${\hat {p}}$ ) indicates a unit vector. (Unit vectors have length 1, i.e. $\lVert {\hat {p}}\rVert =1$ .)

To the problem at hand:

In general coordinates, three spheres intersect at $(x,\ y,\ z)$ if

(x-x_{1})^{2}+(y-y_{1})^{2}+(z-z_{1})^{2}=r_{1}^{2}

(x-x_{2})^{2}+(y-y_{2})^{2}+(z-z_{2})^{2}=r_{2}^{2}

(x-x_{3})^{2}+(y-y_{3})^{2}+(z-z_{3})^{2}=r_{3}^{2}

but it is rather hard to solve these three equations directly.

To simplify the problem, define basis vectors

{\hat {e}}_{x}={\frac {{\bar {p}}_{2}-{\bar {p}}_{1}}{\lVert {\bar {p}}_{2}-{\bar {p}}_{1}\rVert }},\ {\hat {e}}_{y}={\frac {({\bar {p}}_{3}-{\bar {p}}_{1})-{\hat {e}}_{x}({\hat {e}}_{x}\cdot ({\bar {p}}_{3}-{\bar {p}}_{1}))}{\lVert ({\bar {p}}_{3}-{\bar {p}}_{1})-{\hat {e}}_{x}({\hat {e}}_{x}\cdot ({\bar {p}}_{3}-{\bar {p}}_{1}))\rVert }},\ {\hat {e}}_{z}={\hat {e}}_{x}\times {\hat {e}}_{y}

to represent the axes of a new coordinate system. (Because there are only three points, the system is essentially planar, and we do not need the third axis, ${{\hat {e}}_{z}}$ , yet.)

In this new coordinate system, you can write the three points as

{\bar {p}}_{1}=(x_{1},y_{1},z_{1})

{\bar {p}}_{2}=(x_{2},y_{2},z_{2})={\bar {p}}_{1}+{\hat {e}}_{x}h

{\bar {p}}_{3}=(x_{3},y_{3},z_{3})={\bar {p}}_{1}+{\hat {e}}_{x}i+{\hat {e}}_{y}j

where

h={\hat {e}}_{x}\cdot ({\bar {p}}_{2}-{\bar {p}}_{1})=\lVert {\bar {p}}_{2}-{\bar {p}}_{1}\rVert

i={\hat {e}}_{x}\cdot ({\bar {p}}_{3}-{\bar {p}}_{1})

j={\hat {e}}_{y}\cdot ({\bar {p}}_{3}-{\bar {p}}_{1})

If $h=0$ , the first two spheres are concentric, and there can be no solution. (If the two first spheres have different radii, they cannot intersect at all. If they have the same radii, they are the same sphere.)

If $j=0$ , the three spheres are in line. (Oops, I guess there are two possible intersection points, ${\bar {p}}_{1}\pm r_{1}{\hat {e}}_{x}$ , one of which may be a valid solution. I overlooked this earlier, and the test program below does not check these.)

One should probably reorder the spheres to maximize $min(h,|j|)$ to get a good numerical stability and accuracy. See the end of this section for the reasoning. Note that reordering the spheres does not change the result (other than via numerical stability and accuracy); just remember to reorder both the points and the radii the same way.

Using the three variables $h$ , $i$ , and $j$ , with ${\bar {p}}_{1}$ at the origin, the system of three equations can now be written as

X^{2}+Y^{2}+Z^{2}=r_{1}^{2}

(X-h)^{2}+Y^{2}+Z^{2}=r_{2}^{2}

(X-i)^{2}+(Y-j)^{2}+Z^{2}=r_{3}^{2}

and the point we are looking for is $(x,y,z)={\bar {p}}_{1}+{\hat {e}}_{x}X+{\hat {e}}_{y}Y+{\hat {e}}_{z}Z$ in this coordinate system.

As promised, the above system of three equations is easy to solve. Substract the second equation from the first, and solve for $X$ to get

X={\frac {r_{1}^{2}-r_{2}^{2}+h^{2}}{2h}}

Then, substract the third equation from the first, and solve for $Y$ to get

Y={\frac {r_{1}^{2}-r_{3}^{2}+i^{2}+j^{2}-2iX}{2j}}

and then, using the first equation, solve for $Z$ to get

Z=\pm {\sqrt {r_{1}^{2}-X^{2}-Y^{2}}}

In the original coordinates, the solution is

{\bar {p}}={\bar {p}}_{1}+{\hat {e}}_{x}X+{\hat {e}}_{y}Y\pm {\hat {e}}_{z}Z

Some considerations for when solutions may not exist, and when errors are large:

If $h=0$ , the first two spheres are concentric. If $r_{1}=r_{2}$ , they are the same sphere, so there are really just two spheres.

If ${\bar {p}}_{1}$ and ${\bar {p}}_{2}$ are very close to each other, $h$ is very small, and any errors in the input values are magnified in $X$ .

If ${\bar {p}}_{1}$ , ${\bar {p}}_{2}$ and ${\bar {p}}_{3}$ are on the same line, $j$ will be zero. One of ${\bar {p}}_{1}\pm {\hat {e}}_{x}r_{1}$ might be a solution. If angle ${\bar {p}}_{2}{\bar {p}}_{1}{\bar {p}}_{3}$ is small or near 180 degrees, the correction term for basis vector ${\hat {e}}_{y}$ is large, and therefore $j$ very small compared to $i$ ; any errors in the input values are magnified in $Y$ .

Because the order of the spheres is the only free variable (to maximize accuracy and stability with), and there are only six possible combinations, it should be enough to make sure neither $h$ nor $|j|$ are very small; selecting the order which gives the largest $min(h,|j|)$ does that. Error analysis on the equations above would show if maximizing $min(h,|j|)$ gives the best accuracy and numerical stability; in any case, that choice is never particularly susceptible to numerical errors because neither $h$ nor $|j|$ are small.

(Edited my own text for clarity, to fix a missing $\rVert$ , and forgot to login. Several times. Sorry.) Nominal animal (talk) 16:46, 14 June 2010 (UTC)

Although I did not check all details, the concept is clear and a good improvement on the current article. Generality and avoidance of trigonometry make the solution cleaner. You would need to point out where the pathological cases are sidestepped. −Woodstone (talk) 17:10, 14 June 2010 (UTC)

The method is only generic, it does not really sidestep the pathological cases. The pathological cases are fortunately very easy to detect. One can only work around the pathological cases by reordering the spheres; for three spheres, there are only 6 possibilities: 123, 132, 213, 231, 312, and 321. I added a couple of paragraphs on the pathological cases into the middle, and expanded a bit on the problems at the very end. To verify the math and the method, compile and run the example C code I added to the next section. Nominal animal (talk) 21:55, 14 June 2010 (UTC)

Real improvement to preliminary computation section by User:Nominal animal

Nominal animal's recent edit to the Preliminary computation section of the trilateration article appears to be a very good simplification. Thank you for a useful contribution. RHB100 (talk) 21:54, 17 June 2010 (UTC)

Thanks! Also, thank you for the language cleanup; English is obviously not my native language. Nominal animal (talk) 16:04, 19 June 2010 (UTC)

Example C program

This is an enhanced version of the example program I submitted earlier. It is a lightly-tested implementation of the trilateration algorithm.

The program reads the coordinates and the radius for each sphere from standard input, then calculates the intersection point, if any.

This version handles correctly the situation where the three spheres are colinear. For example,

{\bar {p}}_{1}=(0,\ 0,\ 0),\ r_{1}=1

{\bar {p}}_{2}=(3,\ 0,\ 0),\ r_{2}=2

{\bar {p}}_{3}=(9,\ 0,\ 0),\ r_{3}=8

which intersect at $(1,\ 0,\ 0)$ .

(I tested the function with six billion intersecting but otherwise random spheres, and $maxzero=0.000000000001\ min(r_{1},r_{2},r_{3})$ . All solutions were found, no false negatives were reported. The maximum relative error in the distances (compared to radii) in the solutions was less than 0.0000000001. The tests did not include any non-intersecting sphere configurations. Nominal animal (talk) 16:09, 19 June 2010 (UTC))

#include <stdio.h>
#include <math.h>

/* No rights reserved (CC0, see http://wiki.creativecommons.org/CC0_FAQ).
 * The author has waived all copyright and related or neighboring rights
 * to this program, to the fullest extent possible under law.
*/

/* Largest nonnegative number still considered zero */
#define   MAXZERO  0.0

typedef struct vec3d	vec3d;
struct vec3d {
	double	x;
	double	y;
	double	z;
};
 
/* Return the difference of two vectors, (vector1 - vector2). */
vec3d vdiff(const vec3d vector1, const vec3d vector2)
{
	vec3d v;
	v.x = vector1.x - vector2.x;
	v.y = vector1.y - vector2.y;
	v.z = vector1.z - vector2.z;
	return v;
}
 
/* Return the sum of two vectors. */
vec3d vsum(const vec3d vector1, const vec3d vector2)
{
	vec3d v;
	v.x = vector1.x + vector2.x;
	v.y = vector1.y + vector2.y;
	v.z = vector1.z + vector2.z;
	return v;
}
 
/* Multiply vector by a number. */
vec3d vmul(const vec3d vector, const double n)
{
	vec3d v;
	v.x = vector.x * n;
	v.y = vector.y * n;
	v.z = vector.z * n;
	return v;
}
 
/* Divide vector by a number. */
vec3d vdiv(const vec3d vector, const double n)
{
	vec3d v;
	v.x = vector.x / n;
	v.y = vector.y / n;
	v.z = vector.z / n;
	return v;
}
 
/* Return the Euclidean norm. */
double vnorm(const vec3d vector)
{
	return sqrt(vector.x * vector.x + vector.y * vector.y + vector.z * vector.z);
}
 
/* Return the dot product of two vectors. */
double dot(const vec3d vector1, const vec3d vector2)
{
	return vector1.x * vector2.x + vector1.y * vector2.y + vector1.z * vector2.z;
}
 
/* Replace vector with its cross product with another vector. */
vec3d cross(const vec3d vector1, const vec3d vector2)
{
	vec3d v;
	v.x = vector1.y * vector2.z - vector1.z * vector2.y;
	v.y = vector1.z * vector2.x - vector1.x * vector2.z;
	v.z = vector1.x * vector2.y - vector1.y * vector2.x;
	return v;
}

/* Return zero if successful, negative error otherwise.
 * The last parameter is the largest nonnegative number considered zero;
 * it is somewhat analoguous to machine epsilon (but inclusive).
*/
int trilateration(vec3d *const result1, vec3d *const result2,
                  const vec3d p1, const double r1,
                  const vec3d p2, const double r2,
                  const vec3d p3, const double r3,
                  const double maxzero)
{
	vec3d	ex, ey, ez, t1, t2;
	double	h, i, j, x, y, z, t;
 
	/* h = |p2 - p1|, ex = (p2 - p1) / |p2 - p1| */
	ex = vdiff(p2, p1);
	h = vnorm(ex);
	if (h <= maxzero) {
		/* p1 and p2 are concentric. */
		return -1;
	}
	ex = vdiv(ex, h);
 
	/* t1 = p3 - p1, t2 = ex (ex . (p3 - p1)) */
	t1 = vdiff(p3, p1);
	i = dot(ex, t1);
	t2 = vmul(ex, i);
 
	/* ey = (t1 - t2), t = |t1 - t2| */
	ey = vdiff(t1, t2);
	t = vnorm(ey);
	if (t > maxzero) {
		/* ey = (t1 - t2) / |t1 - t2| */
		ey = vdiv(ey, t);
 
		/* j = ey . (p3 - p1) */
		j = dot(ey, t1);
	} else
		j = 0.0;

	/* Note: t <= maxzero implies j = 0.0. */
	if (fabs(j) <= maxzero) {
		/* p1, p2 and p3 are colinear. */

		/* Is point p1 + (r1 along the axis) the intersection? */
		t2 = vsum(p1, vmul(ex, r1));
		if (fabs(vnorm(vdiff(p2, t2)) - r2) <= maxzero &&
		    fabs(vnorm(vdiff(p3, t2)) - r3) <= maxzero) {
			/* Yes, t2 is the only intersection point. */
			if (result1)
				*result1 = t2;
			if (result2)
				*result2 = t2;
			return 0;
		}

		/* Is point p1 - (r1 along the axis) the intersection? */
		t2 = vsum(p1, vmul(ex, -r1));
		if (fabs(vnorm(vdiff(p2, t2)) - r2) <= maxzero &&
		    fabs(vnorm(vdiff(p3, t2)) - r3) <= maxzero) {
			/* Yes, t2 is the only intersection point. */
			if (result1)
				*result1 = t2;
			if (result2)
				*result2 = t2;
			return 0;
		}

		return -2;
	}
 
	/* ez = ex x ey */
	ez = cross(ex, ey);
 
	x = (r1*r1 - r2*r2) / (2*h) + h / 2;
	y = (r1*r1 - r3*r3 + i*i) / (2*j) + j / 2 - x * i / j;
	z = r1*r1 - x*x - y*y;
	if (z < -maxzero) {
		/* The solution is invalid. */
		return -3;
	} else
	if (z > 0.0)
		z = sqrt(z);
	else
		z = 0.0;
 
	/* t2 = p1 + x ex + y ey */
	t2 = vsum(p1, vmul(ex, x));
	t2 = vsum(t2, vmul(ey, y));
 
	/* result1 = p1 + x ex + y ey + z ez */
	if (result1)
		*result1 = vsum(t2, vmul(ez, z));
 
	/* result1 = p1 + x ex + y ey - z ez */
	if (result2)
		*result2 = vsum(t2, vmul(ez, -z));
 
	return 0;
}

int main(void)
{
	vec3d	p1, p2, p3, o1, o2;
	double	r1, r2, r3;
	int	result;
 
	while (fscanf(stdin, "%lg %lg %lg %lg %lg %lg %lg %lg %lg %lg %lg %lg",
	                     &p1.x, &p1.y, &p1.z, &r1,
	                     &p2.x, &p2.y, &p2.z, &r2,
	                     &p3.x, &p3.y, &p3.z, &r3) == 12) {
		printf("Sphere 1: %g %g %g, radius %g\n", p1.x, p1.y, p1.z, r1);
		printf("Sphere 2: %g %g %g, radius %g\n", p2.x, p2.y, p2.z, r2);
		printf("Sphere 3: %g %g %g, radius %g\n", p3.x, p3.y, p3.z, r3);
		result = trilateration(&o1, &o2, p1, r1, p2, r2, p3, r3, MAXZERO);
		if (result)
			printf("No solution (%d).\n", result);
		else {
			printf("Solution 1: %g %g %g\n", o1.x, o1.y, o1.z);
			printf("  Distance to sphere 1 is %g (radius %g)\n", vnorm(vdiff(o1, p1)), r1);
			printf("  Distance to sphere 2 is %g (radius %g)\n", vnorm(vdiff(o1, p2)), r2);
			printf("  Distance to sphere 3 is %g (radius %g)\n", vnorm(vdiff(o1, p3)), r3);
			printf("Solution 2: %g %g %g\n", o2.x, o2.y, o2.z);
			printf("  Distance to sphere 1 is %g (radius %g)\n", vnorm(vdiff(o2, p1)), r1);
			printf("  Distance to sphere 2 is %g (radius %g)\n", vnorm(vdiff(o2, p2)), r2);
			printf("  Distance to sphere 3 is %g (radius %g)\n", vnorm(vdiff(o2, p3)), r3);
		}
	}
 
	return 0;
}

Note that the trilateration() function takes an extra parameter, $maxzero$ , which is the largest nonnegative number still considered zero.

By default $maxzero=0$ , which is too small to find the solution in some cases. Something like $min(r_{1},r_{2},r_{3})\cdot 0.0000001$ should work well with double precision floating-point numbers.

If best precision is desired, the trilateration() function should be modified to return min(h,fabs(j)) instead of zero when successful. Call the function with each of the six sphere order permutations, with $maxzero=0$ , and select the result which corresponds the largest return value; this should have the least numerical instability.

If all six calls return negative, set maxzero to, say, $maxzero=min(r_{1},r_{2},r_{3})/100$ , and retry. If these calls also fail, there is no solution. Otherwise, use e.g. binary search (halving $maxzero$ each round) to find the smallest working maxzero. Select the result with corresponds to the largest return value (using the smallest working maxzero).

The function is unoptimized, but still rather cheap: on an Athlon64, each call to the trilateration() function takes roughly 2000 - 6000 clock cycles. Nominal animal (talk) 18:58, 18 June 2010 (UTC)

Substitution

Just a minor point, shouldn't rather

z^{2}=r_{1}^{2}-x^{2}-y^{2}

than

y^{2}+z^{2}=r_{1}^{2}-x^{2}

be substituted in the third equation? 129.247.247.238 (talk) 10:47, 19 November 2012 (UTC)

Since there were no objections, I will change the respective line. 129.247.247.238 (talk) 13:50, 28 November 2012 (UTC)

Statistical Lateration

This has probably been addressed before, but I think it is worth reconsidering: the statistical (i.e. in presence of noise) use of (tri)lateration should be emphasized and I think it will greatly improve the article. The current "multilateration" page is essentially a TDOA article (a bit too much, in fact). But the problem of lateration is slightly more abstract (it doesn't concern itself from where the measurements come from, in fact it is also heuristically used in RSS-based localization). I am no expert on the field, thus I can't write about it, but I think the general problem should (at least) be cited. In its statistical usage, "tri" (in the word "trilateration") is omitted, since you usually have $N$ nodes (centers of the spheres), with $N$ sufficiently high, and the radii are known within a plus or minus "delta" (note that, inside this delta, there are also included the uncertainties in the coordinates of the centers, leaving the centers error-free; in other words, all the errors are put in the radii's uncertainties, simplifying the notation). Note that the $\delta _{i}$ , with $i=1,\dots ,N$ , are generally different (it cannot be assumed $\delta _{i}=\delta$ for all $i$ ). The "spheres" (spherical shells: $r_{i}-\delta _{i}$ , $r_{i}+\delta _{i}$ ) typically intersects in a region (the "grey zone" or something like that) and then, for example, the centroid (center of mass) is taken. Obviously, the algorithm discards the "spheres" which do not intersect at all. Can someone with more expertize write about this or is there already an article (except multilateration/TDOA) regarding these topics? — Preceding unsigned comment added by 93.148.154.1 (talk) 13:57, 2 April 2014 (UTC)

Wrong generalisation that 3/4 spheres are enough?

The article states that:

"If it is known that the point lies on the surface of a fourth sphere then knowledge of this sphere's center along with its radius is sufficient to determine the one unique location."

I'm fairly sure that this need not always be true. If you have found 2 points, that all lie on the first three spheres, then there still is an infinite number of other spheres, that also have both points on their surface. Knowing the position and radius of one of these spheres would not help to discriminate between one of the two points. To visualize: take any 4th sphere and rotate it around the axis that is defined by the two points. All spheres that are thus generated do not provide any further information. So, a 4th sphere CAN help, but it need NOT ALWAYS be enough. Or, even: there is no number N such that N spheres are guaranteed to define a single point in space via the intersection of their surfaces. One needs additional constraints as to how the spheres are positioned relative to each other. At the very least the sentence in question should be weakened to something like "is usually sufficient", if that is the case in real-world-scenarios (e.g. GPS). — Preceding unsigned comment added by 94.198.62.204 (talk) 15:21, 18 June 2013 (UTC)

When I think about it, even the statement about 3 spheres narrowing down the position to 2 points in 3D, is not correct:

"In three-dimensional geometry, when it is known that a point lies on three surfaces such as the surfaces of three spheres then the centers of the three spheres along with their radii provide sufficient information to narrow the possible locations down to no more than two."

There is actually an infinity number of different spheres in 3D that share a common "boundary-intersection-circle" (their centers lie on a straight line). I will delete the whole paragraph, because it is factually wrong and I'm not sure what it is supposed to say. --94.198.62.204 (talk) 12:41, 15 July 2013 (UTC)

The generalization holds as long as no more than 2 reference points are colinear and no more than 3 are coplanar.--Jmknaup (talk) 11:55, 30 May 2014 (UTC)

References

No citation for the proposed method for triangulation is given. Is there an evaluation that the proposed method is "good" or even "optimal" in terms of computational efficiency and/or accuracy? Is there an evaluation of the numerical stability of the proposed algorithm? Are there any comparisons with other algorithms for triangulation? — Preceding unsigned comment added by 194.138.39.52 (talk) 11:54, 16 February 2016 (UTC)