Triangulation Experiment

[C5B]

I had an idea while driving to work today... Geocaching via triangulation.

 

It works like this: select a target cache from the list, but don't look at it's cache page. Instead, choose 3 caches around the target cache. From those caches, using the geocaching website, its possible to get a known distance from each of the chosen caches to the target cache (without looking at the target cache's page)

 

With 3 known distances, we can then triangulate the location of the target cache by plotting on a map.

 

Seems easy enough? Probably is with a good map... except, here's the part where I'm stuck and need some expert help. I'd like to calculate the coords of the plot (target cache). My intuition tells me its possible as long as I know a distance and azmuth from 3 known points. Anybody know how to make this calculation?

 

Anybody else want to jump in on this experiment and give this a try?

[DisQuoi]

I have two caches here and here that requires the finder to triangulate (one mathematically and one with a map). I provide a spreadsheet to those who are unable to do it. The simplest way is to assume that the three reference coordinates are on a flat plane (close enough that the curvature of the earth is negligible) and convert to UTM. From here it's just an exercise in geometry/trigonometry.

 

I had started a similar thread on the subject and there were many good sources of help on doing this.

 

Keep this in mind ... the distances provided by the cache pages is only to 0.01 miles ... about 50 feet. Using UTM coordinates and the Pythagorean theorem, you can get exact distances. Of course you'de have to view the coordinates of the cache you're interterested in triangulating.

[+Markwell]

There are actually some multi-stage caches out there that use three (or four) first stages and the bearing and distance from each of those to find the last stage.

 

Here's a thread where a few of us kicked it around for a while and some caches were posted.

 

Markwell

My Geocaching Page

[+Markwell]

First - DisQuoi: did you hurt your mouse finger when we bumped like that in posting?

 

Second - THANK YOU! - that was the thread I was thinking about, but I couldn't find.

 

Markwell

My Geocaching Page

[DisQuoi]

quote:

---

Originally posted by Markwell:

First - DisQuoi: did you hurt your mouse finger when we bumped like that in posting?

---

No, I wear a protective foam helmut on my mouse finger for safety reasons.

[DisQuoi]

quote:

---

Originally posted by Markwell:

First - DisQuoi: did you hurt your mouse finger when we bumped like that in posting?

---

No, I wear a protective foam helmut on my mouse finger for safety reasons.

[+parkrrrr]

It's actually possible with just the three distances, and if you assume the coordinates are on a plane, there's no geometry or trig required, just plain ol' algebra. I won't go through the derivation, but here's some Perl code that will calculate the coordinates of an unknown point if you give it the coordinates of three points and the distances from those points. It should be easy enough to read as plain math if you wanted to do it on a calculator:

 

# Coordinates are in ($x0,$y0), ($x1,$y1), ($x2,$y2)# Distances are in $d0, $d1, $d2.my $c0 = ($d0**2-$x0**2-$y0**2)/2;my $c1 = ($d1**2-$x1**2-$y1**2)/2;my $c2 = ($d2**2-$x2**2-$y2**2)/2;my $y = (($x1-$x0)*($c2-$c1)-($x1-$x2)*($c0-$c1))/(($x1-$x0)*($y1-$y2)-($y1-$y0)*($x1-$x2));my $x = ($c2-$c1-$y*($y1-$y2))/($x1-$x2);# Results are in ($x, $y)

 

[+parkrrrr]

Experimenting with the above code and the closest three caches to GeoOtter's PEZ Cache (which is, in turn, the closest cache to me...) gives me results of

 

N 41° 6.497' W 85° 9.323'

 

which are in the same park as the cache, but in the middle of the lake, at least a hundred meters away. That little 50-foot error can get pretty big when you have to square it.

 

Remember, kids, if you're trying this at home you have to do it in UTM and convert the miles to meters.

 

[DisQuoi]

quote:

---

Originally posted by Warm Fuzzies - Fuzzy: Here's some Perl code that will calculate the coordinates of an unknown point if you give it the coordinates of three points and the distances from those points.

---

That's pretty cool. I'd actually like to see the derivation. Is there code available that will compute two intersections of two arcs?

[+parkrrrr]

quote:

---

Originally posted by DisQuoi:

That's pretty cool. I'd actually like to see the derivation.

---

 

You asked for it...

 

The equation for a circle of radius d0 centered on (x0,y0) is (x-x0)**2+(y-y0)**2=d0**2. From this, we have that:

x**2-2*x0*x+x0**2+y**2-2*y0*y+y0**2=d0**2

which is equivalent to

X**2-2*x0*x+y**2-2*y0*y = d0**2-x0**2-y0**2

We'll call the right side of that 2*c0 for the sake of simplicity down the road. Doing the same thing for (x1,y1) and (x2,y2) gives us three equations:

X**2-2*x0*x+y**2-2*y0*y = 2*c0X**2-2*x1*x+y**2-2*y1*y = 2*c1X**2-2*x2*x+y**2-2*y2*y = 2*c2

Subtracting each of the first and third equations from the second (don't ask me why I did it this way...) gives us

(x1-x2)*x+(y1-y2)*y=c2-c1(x1-x0)*x+(y1-y0)*y=c0-c1

which is a simple linear system. The solution of that linear system for x and y is left as an exercise for the reader, but the answer is given in the code above.

 

[+parkrrrr]

quote:

---

Originally posted by DisQuoi:

That's pretty cool. I'd actually like to see the derivation.

---

 

You asked for it...

 

The equation for a circle of radius d0 centered on (x0,y0) is (x-x0)**2+(y-y0)**2=d0**2. From this, we have that:

x**2-2*x0*x+x0**2+y**2-2*y0*y+y0**2=d0**2

which is equivalent to

X**2-2*x0*x+y**2-2*y0*y = d0**2-x0**2-y0**2

We'll call the right side of that 2*c0 for the sake of simplicity down the road. Doing the same thing for (x1,y1) and (x2,y2) gives us three equations:

X**2-2*x0*x+y**2-2*y0*y = 2*c0X**2-2*x1*x+y**2-2*y1*y = 2*c1X**2-2*x2*x+y**2-2*y2*y = 2*c2

Subtracting each of the first and third equations from the second (don't ask me why I did it this way...) gives us

(x1-x2)*x+(y1-y2)*y=c2-c1(x1-x0)*x+(y1-y0)*y=c0-c1

which is a simple linear system. The solution of that linear system for x and y is left as an exercise for the reader, but the answer is given in the code above.

 

[+parkrrrr]

quote:

---

Originally posted by DisQuoi:

Is there code available that will compute two intersections of two arcs?

---

 

That one's a bit harder and requires some geometry. Consider the point that lies on the line between the two solution points and on the line between the two centers. Let's say that that point's distance from (x0,y0) is s0, and its distance from (x1,y1) is s1. In addition, let's say that d is half the distance between the two solution points, and is unknown. The Pythagorean Theorem and a little common sense can be applied to determine that

d0**2-d**2=s0**2d1**2-d**2=s1**2

which means that

d0**2-s0**2=d**2=d1**2-s1**2

In addition, we know the distance between the two centers; let's call it s.

s0+s1=s

Shuffling terms around, we get this:

d0**2-d1**2=s0**2-s1**2=s0**2-(s-s0)**2=s0**2-s**2+2*s*s0-s0**2=s**2+2*s*s0.

A little more shuffling to get all the constant terms on one side:

s0=(d0**2-d1**2-s**2)/(2*s)

Now we know the point that lies halfway between the two solutions:

xh=x0+(s0/s)*(x1-x0)yh=y0+(s0/s)*(y1-y0)

We can also get d:

d=sqrt(d0**2-s0**2)

A little vector algebra, trig, and hocus-pocus later:

dx=(y1-y0)/s*ddy=(x0-x1)/s*d

And our final code is

s=sqrt((x0-x1)**2+(y0-y1)**2)s0=(d0**2-d1**2-s**2)/(2*s)xh=x0+(s0/s)*(x1-x0)yh=y0+(s0/s)*(y1-y0)d=sqrt(d0**2-s0**2)dx=(y1-y0)/s*ddy=(x0-x1)/s*dxa=xh+dxya=yh+dyxb=xh-dxyb=yh-dy

All of this is untested, so it's possible a sign or other error creeped in somewhere, but I think it's right.

 

[+erik88l-r]

I posted one in the midst of six other caches but gave no distance information whatsoever. For that you had to find the other caches and read the distance written in that cache's log book. You find at least one, but the more you find the better you can zero in on where the seventh cache is. Some of the caches are so obtuse in their own right it can be a real adventure. The distances range from a third of a mile to about three quarters of a mile.

 

http://www.geocaching.com/seek/cache_details.asp?ID=20928

 

~erik~

[DisQuoi]

Your derivation of the intersection is the same I used in my spreadsheet that I provide finders when they need help with my YOU ARE THE GPS cache. Unlike your first solution, it only provided two intersections for two arcs. In that case, it's up to the finder to figure out which of 4 possible intersections is the correct one (the one common to all three combination of the three arcs). That way, they still need to understand the relationship between the locations of the satellites and the distances I provide in them. I'll definately hold on to your three-arc solution for my own future use, though.

 

(It might be worth pointing out that when using Warm Fuzzies' solutions, x**2 would mean x^2 or x-squared)

 

By the way ... some are saying that this is a way to locate members only caches. I tried this to locate Moonshine Mountain by OUTSID4EVR & MAJELLIN in Virginia and the error was 131 feet.

 

[This message was edited by DisQuoi on May 14, 2002 at 10:54 AM.]

[jfitzpat]

quote:

---

Originally posted by Warm Fuzzies - Fuzzy:

 

All of this is untested, so it's possible a sign or other error creeped in somewhere, but I think it's right.

---

 

Seems correct. All the old navigational and astronomy texts I have generally solve this as a spherical triangle. But, as long as you are confined to one zone, it seems that a linear solution on a UTM projection is about as accurate, and less computationally intensive.

 

-jjf

[+unclerojelio]

This triangulation cache was recently posted my area. Instead to doing the math I simply used my GPSr to give me the distances (a little more accurate than the GC.com distance) and then used a CAD program to work out the angles. Then back to the GPSr to project a waypoint. By the time I had done this for all three combinations I ended up within about 25ft of the cache.

 

... Two roads diverged in a wood, and I--

I took the one less traveled by, ...

 

unclerojelio

[+unclerojelio]

This triangulation cache was recently posted my area. Instead to doing the math I simply used my GPSr to give me the distances (a little more accurate than the GC.com distance) and then used a CAD program to work out the angles. Then back to the GPSr to project a waypoint. By the time I had done this for all three combinations I ended up within about 25ft of the cache.

 

... Two roads diverged in a wood, and I--

I took the one less traveled by, ...

 

unclerojelio

[evilC]

Geometry of Owhango is one cache I've set up requiring "triangulation".

 

Another person used the same idea in Geometry Experiment.

 

The basic yellow eTrex that I use has the nearest waypoints screen which works well with this kind of cache over shorter distances at least.

[+MrGigabyte]

The best way to solve the overdetermined solution of a distance/distance/distance intersection is to use a least squares transformation.

 

This is commonly done in the geomatics world by using a Helmert's Similarity Transformation. Helmerts is built in to most Survey grade GPS data collectors and also most handheld calculators that have Surveying modules (i.e (HP/TDS).

[+parkrrrr]

quote:

---

Originally posted by MrGigabyte:

The best way to solve the overdetermined solution of a distance/distance/distance intersection is to use a least squares transformation.

---

 

MrGigabyte has a good point: while two distances from two centers is an underdetermined system, three distances from three centers is overdetermined on a plane. There is no point that precisely matches the initial conditions.

 

Interestingly enough, the method I gave above gives an exact solution when all three distances are exact, but the solution it gives when the distances are not exact is rather strange: it doesn't satisfy ANY of the initial conditions. Check this out:

 

x0 656359.15007985 y0 4549719.96361227 d0 3266.96832 D0 3074.86090832711 R0 0.94119703870502x1 656534.286469762 y1 4549782.9436096 d1 3299.1552 D1 3109.03725260592 R1 0.942373748469281x2 652934.21388879 y2 4549134.85474775 d2 3975.07968 D2 3818.76237384044 R2 0.960675679799315x 654884.412228415 y 4552418.09590612

These are the numbers for the closest three caches to GeoOtter's PEZ Cache, which I mentioned above. D0, D1, and D2 are the distances from the "solution point" to each of the three centers. R0, R1, and R2 are the ratios between those distances and the given distances d0, d1, and d2. Interestingly, none of the distances was precisely matched, but they were all reduced by about the same amount. Maybe if all of my reference points weren't south of the final location I would get better numbers. As it is, that reduction seems to drag the solution point south.

 

[+Markwell]

 

Markwell

My Geocaching Page

[jfitzpat]

quote:

---

Originally posted by MrGigabyte:

[snip] This is commonly done in the geomatics world by using a Helmert's Similarity Transformation. Helmerts is built in to most Survey grade GPS data collectors and also most handheld calculators that have Surveying modules (i.e (HP/TDS).

---

 

Off the top of my head, I was only familiar with Helmert's 'gravity' (Helmert's 2nd Condensation, etc.). I walked over to the library (its just a couple blocks from our downtown office) and did a search.

 

When I came across: "Martinec, Z.,The Static, Potential Free Love Numbers for a Homogeneous Earth Model Bounded by an Irregular Surface, - V.17, pp.186-200, 1992."

 

I decided that, like Markwell, my brain is full...

 

-jjf