2d trilateration

I am writing some code to participate in an AI challenge. The main objective for the AI challenge is to take a simulated robot and navigate it through a maze to a destination zone. The secondary objective which is optional is to find a recharger placed in the maze at an unknown location. This is all done in a 2D grid.

My program can call a method to get a distance measurement from the recharger. So using trilateration I should be able to locate the recharger by calling this method, recording my ai's current position and the distance the recharger is away from that point 3 times over.

I found this example of trilateration on wikipedia http://en.wikipedia.org/wiki/Trilateration but this applies to a 3d space. I'm only dealing with a 2D space. Also I don't understand how to use the formula shown in Wikipedia, searching the web for a working example with numbers plugged in and boiling down to the final coordinates is scarce with Google searches.

I'm not a math major; I am just an enthusiast exploring AI problems.

An explanation and step by step example of how to calculate the problem is what I need as mathematics are not my strong point. Below is some sample data:

  • Point 1: x=39, y=28, distance=8
  • Point 2: x=13, y=39, distance=11
  • Point 3: x=16, y=40, distance=8
  • Any example using my sample data would be greatly appreciated. The programming to this will be very straight forward once I can wrap my head around the mathematics.


    As the Wikipedia trilateriation article describes, you compute (x,y) coordinates by successively calculating: ex, i, ey, d, j, x, y. You have to be familiar with vector notation, so, for example, ex = (P2 - P1) / ‖P2 - P1‖ means:

  • ex,x = (P2x - P1x) / sqrt((P2x - P1x)2 + (P2y - P1y)2)
  • ex,y = (P2y - P1y) / sqrt((P2x - P1x)2 + (P2y - P1y)2)
  • Your data is:

  • P1 = (39, 28); r1 = 8
  • P2 = (13, 39); r2 = 11
  • P3 = (16, 40); r3 = 8
  • The calculation steps are:

  • ex = (P2 - P1) / ‖P2 - P1‖
  • i = ex(P3 - P1)
  • ey = (P3 - P1 - i · ex) / ‖P3 - P1 - i · ex‖
  • d = ‖P2 - P1‖
  • j = ey(P3 - P1)
  • x = (r12 - r22 + d2) / 2d
  • y = (r12 - r32 + i2 + j2) / 2j - ix / j
  • 链接地址: http://www.djcxy.com/p/84952.html

    上一篇: 三边测量代码Matlab中的错误

    下一篇: 二维三角测量