Рассчитать расстояние между точкой и отрезком на эллипсоиде (или координаты WGS84)? - PullRequest
Новая
       33

Рассчитать расстояние между точкой и отрезком на эллипсоиде (или координаты WGS84)?

2 голосов
/ 01 апреля 2010

У меня есть отрезок AB между двумя координатами WGS84 на поверхности Земли (или, альтернативно, на эллипсоиде), и мне нужно вычислить расстояние между точкой P и ближайшей к P точкой, которая находится на отрезке AB. Как я могу это сделать?

Любая помощь очень ценится.

С уважением, Jochen

1 Ответ

1 голос
/ 04 апреля 2010

Я никогда не имел дела с координатами WGS84, и я в этом математике ржавый, но я дам вам то, что пришло в голову. На самом деле я не отвечаю на этот вопрос, но это было слишком много, чтобы добавить комментарий, и в нем есть псевдокод. Я просто подумал, что проблема интересная, и хотел немного поиграть с ней. Во всяком случае, здесь идет ...

Представьте множество всех сфер, центр которых - P.

Теперь только одна из этих сфер должна делить ровно 1 очко с AB. Если у вас есть уравнение, описывающее AB, тогда вы сможете найти сферу, центрированную в этой точке, которая будет точно равна одной точке с AB.

Возможно, существует более быстрый способ сделать это, чем метод проб и ошибок, но бинарный поиск - это то, что приходит на ум. Это должно найти расстояние по прямой линии до AB. Если вы хотите разногласия между P и AB, я расскажу об этом после кода. psudocode: 

   Radius_lo = 0
   Radius_hi = minimum( distance(P, A), distance(P, B) )
   Radius_test = Raduis_hi // you may want to add a miniscule amount to this to keep from floating point inprecision from effectively rounding down which could lead to no actual intersection
   while true
      intersections = intersection_points( sphere( P, Radius_test), AB )
      if ( count(intersections) == 1 ) // or close enough.  With floating pt math you'll likely need to recognize close enough or it will never exit.
            return  Radius_test
      if ( count(intersections) == 2 )
            // Here you may do one of two things, both of which are binary searches.
            // 1. The first and simplest would be to divide average _test with _lo and try again
            Radius_hi = Radius_test
            Radius_test = (Radius_test + Radius_lo) / 2
            Continue
            // 2. The second would be to attempt to divide the segment fromed by the two intersection points, which is more complicated, but would almost always result in fewer times through the loop
            X = midpoint(intersection[0], intersection[1]) // midpoint would have to know how to find the midpoint of them along the elipse that they live on
            Radius_test = distance( P, X)
            Continue
     if ( count(intersections) == 0)
           // Gone too far.  If you had done (1) above, then do
           Radius_lo = Radius_test
           Radius_test = (Radius_test + Radius_hi) / 2
           Continue
           // If on the otherhand you had done (2) above then you shouldn't ever have this case
           error("0 intersections!")
     // Now, this should be for any intersection count other than 0, 1, or 2.  This shouldn't happen so
     error("bad intersection count")
  endloop // while true

Это позволит найти расстояние по прямой линии между P и AB до тех пор, пока эллиптический сегмент AB ближе к P, чем любая другая часть эллипса, на которой лежит AB. Если это не так, то достаточно просто проверить это и просто использовать ближе A или B в качестве ближайшей точки.

Хорошо, значит, вы на самом деле хотели расстояние от поверхности до P и AB. Это сложнее, но вы можете изменить мой алгоритм для работы с этим.

...