Окружность по трем гео-координатам?

Question

[zaartix]

Имееются координаты трех точек на карте.

Надо найти координаты центра описанной вокруг получившегося треугольника окружности.


Классическое геометрическое решение через перпендикуляры не подходит, без полиноминального преобразования, выполнять последнее очень не хочется (да и если честно не совсем понятно как его производить).


Нет ли идей как более простым способом найти центр?


расчет ведется на php




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


задача вцелом (из риэлторской тематики):

Яндекс-карты не умеют определять пересечения улиц (

Мы придумали такой способ: есть база с домами (находящихся на улицах) и координатами этих домов. Надо найти перекресток двух заведомо пересекающихся улиц.

Выбираем все дома по этим улицам и ищем дома, находящиеся к примеру в пределах 200 метрах друг от друга (но на разных улицах ес-но, т.е. каждый дом с одной улицы сравниваем с каждым домом на другой улице). По-сути на картинке именно это и изображено (разные улицы = разные иконки). Дальше уже надо определить примерную область, в которой будет находится дом, указанный в объявлении как «перекресток улиц Тухачевского и Магнитогорской». Примерная область = окружность

Comments

[Sannis]

А почему вы хотите избежать полиномиальных преобразований?

[zaartix]

ну как вам сказать… В общем я не смог разобрался как его произвести, хотя много разных статей прочитал, но они подразумевают наличе некоторого базиса, которого у меня нет (
вот и подумал, что наверняка можно обойтись без него, ведь расстояния-то небольшие.

А вообще после нескольких дней экспериментов решили, что построить окружность по двум точкам будет достаточным, с тремя точками решили не связываться, потому как вычисления на порядок проще, а обсчитывать планиурется не мало. Другими словами предпочли сделать ставку на скорость, чем на точность (хотя в 90% случаев окружности по двум точкам вполне достаточно для покрытия всего множества).

Answer 1

[Horse]

C помощью метода координат. Например по 1 и 2 точке строите уравнение прямой равноудаленной от этих двух точек. Потом тоже самое, например, для 2 и 3 точки. Пересечение этих двух прямых будет центром окружности. Радиус — очевидно, расстояние от центра до любой из точек.

Comments

[zaartix]

вы предлагаете как раз через перпендикуляры, если я вас правильно понял. Результат этого вычисления я и привел выше в виде скриншота, оно так не работает.
заранее прошу прощения, если вдруг вы писали свой комментарий до того, как я обновил топик.

[Horse]

________________________________________________
(x — x1)^2 + (y — y1)^2 = r^2
(x — x2)^2 + (y — y2)^2 = r^2
(x — x3)^2 + (y — y3)^2 = r^2
________________________________________________
x^2 -2*x*x1 + x1^2 + y^2 — 2*y*y1 + y1^2 = r^2
x^2 -2*x*x2 + x2^2 + y^2 — 2*y*y2 + y2^2 = r^2
x^2 -2*x*x3 + x3^2 + y^2 — 2*y*y3 + y3^2 = r^2
________________________________________________
(- 2*x1 + 2*x2)*x + (- 2*y1 + 2*y2)*y = (-x1^2 + x2^2) + (-y1^2 + y2^2)
(- 2*x2 + 2*x3)*x + (- 2*y2 + 2*y3)*y = (-x2^2 + x3^2) + (-y2^2 + y3^2)
________________________________________________
a1 = — 2*x1 + 2*x2
a2 = — 2*x2 + 2*x3
b1 = — 2*y1 + 2*y2
b2 = — 2*y2 + 2*y3
c1 = (-x1^2 + x2^2) + (-y1^2 + y2^2)
c2 = (-x2^2 + x3^2) + (-y2^2 + y3^2)
… ищем пересечение двух прямых
a1*x+b1*y = c1
a2*x+b2*y = c2
________________________________________________
y = (c2 * a1 — c1 * a2) / (a1 * (b2 — b1))
x = (c1-b1*y) / a1;

Надеюсь нигде не ошибся)… Вас осталось только проверить частные случаии (чтобы на 0 не делить) и можно использовать уже готовые формулы)

[zaartix]

координаты получаются весьма странными, видимо причина как раз в том, что:
в координатах на плоскости, условно говоря 1x = 1y, а в геокоординатах совершенно не так, только на экваторе 1x будет равен 1y, а дальше, чем ближе к северу, тем больше, т.е. у нас в самаре 1 градус по x примерно равен 1.8 градусам по Y, отсюда и проблемы при использовании координат

[Horse]

Для карт такого размера 1x — 1y < epsilon. Может я где-то и в вормулах ошибсся, либо там значения слишком большие/ маленькие и теряется точность…

Answer 2

[Horse]

Еще раз… Правильно ли я понимаю… Нужна окружность которая которая проходит через 3 заданные точки (что однозначно определяют окружность)?

Comments

[Horse]

И Множество точек — это сколько? Если больше 20 и важна скорость — алгоритм уже может быть не тривиальным.

[zaartix]

ну смотрите, есть большая куча точек. Надо описать такую минимальную окружность, чтобы она «закрыла» все точки. Очевидно, что надо строить окружность по трем наиболее отдаленных друг от друга точек. Другими словами она должна проходить через 3 заданные точки.

[Horse]

Понял. Ну тогда то, что я написал — верно. Эти формулы сработают, построенная окружность будет проходить через все три точки, но не в этом проблема. Проблема именно в определении этих трех точек. Было бы их меньше 20 — можно было бы перебор устроить…

А что это будет? Для пентагона пишите расчет необходимой мощи и центра удара для поражения всех нужных едениц?

[zaartix]

нет, все проще. Задача по риэлторской тематике.
Яндекс-карты не умеют определять пересечения улиц (
Мы придумали такой способ: есть база с домами (находящихся на улицах) и координатами этих домов. Надо найти перекресток двух заведомо пересекающихся улиц.
Выбираем все дома по этим улицам и ищем дома, находящиеся к примеру в пределах 200 метрах друг от друга. По-сути на картинке именно это и изображено (разные улицы = разные иконки). Дальше уже надо определить примерную область, в которой будет находится дом, указанный в объявлении как «перекресток улиц Тухачевского и Магнитогорской». Примерная область = окружность

Answer 3

[hayk]

Поясните пожалуйста, нужна ли окружность, которая проходит через все три точки, или же нужна окружность, внтури которой находятся все три точки?

Comments

[hayk]

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

[zaartix]

спасибо за ваше решение, сейчас проверить его нет возможности, завтра как проверю обязательно отпишусь.

[Nicolette]

, вы уверены? Возьмите хотя бы равносторонний треугольник, для него это неверно.

[hayk]

Да, действительно. То что я написал верно только для тех случаев, когда противолежащий этой стороне угол не меньше 90 градусов.

[Horse]

То, что вы написали верно когда угол равен 90, а не 'не меньше'

[hayk]

Если угол больше 90 градусов, то эта вершина треугольника просто будет внутри окружности, а не на ней.

Answer 4

[mythmaker]

Классическая олимпиадная задача по программированию, решения можно найти тут.

Comments

[zaartix]

спасибо за ссылку, отпишусь, когда выясню подходит ли.

[Sannis]

Осталось только не забыть про то, что всё это на сфере.

Answer 5

[Sannis]

Боюсь без кропотливой работы со сферическими координатами ничего путного не получится. Но и рисовать такую «окружность» будет не просто.

Если радиус небольшой, как у вас на рисунке, то должно через перпендикуляры считаться. Проверьте ещё раз выкладки.

Comments

[Алексей Гриченко]

Думаю, что «в пределах 200 метров» землю можно считать не только сферической, но еще и в вакууме. :)

[zaartix]

не, на самом деле тут суть не в как таковой сферичности, а в оси Y, точнее в координатах.
в координатах на плоскости, условно говоря x = y, а в геокоординатах совершенно не так, только на экваторе x будет равен y, а дальше, чем ближе к северу, тем больше, т.е. у нас в самаре 1 градус по x примерно равен 1.8 градусам по Y, отсюда и проблемы при использовании координат

[Sannis]

Ничто не мешает это учесть. Берёте одну из вершин треугольника за рефер, рассчитываете координаты остальных в относительных метрах и дальше по формулам.

Answer 6

[yuri ннн]

а если предположить что всё-таки земля (геоид) это почти сфера, тогда можно попробовать пойти через сферу римана и комплекс...?
но это так пока только идея, надо подумать как это реализовать…

Answer 7

[Horse]

надуплил… Извеняюся…
То что я сказал — справедливо для остроугольных (каждый угол < 90), иначе то что сказал havk
> Если точек 3, и нужна окружность внутри которой будут находиться все три точки, то ее центром будет точка, которая является серединой самой длинной стороны треугольника, которую образуют эти точки.

Если 1x != 1y — привидите в нормальную декартовую систуму координат и делайте то, что мы описали.

Comments

[Horse]

А вообще, лучше возьмите за центр — центр масс всех точек, и не парьтесь. Сверх точно не будет, возможно для отдельных (сверхредких) случаев будет не то, но для большинста — то что нужно.

[zaartix]

процедура приведения геокоординат в нормалькую декартову систему координат и называется полиноминальным преобразованием, которую я хотел избежать.

[Horse]

Да… Ну и бардак мы тут развели. Вас следовало сразу указать в какой системе координат хранятся ваши точки… По сути, если у вас есть 2d картинка и отмеченны точки на ней — вы можете забить на реальные координаты и использовать сразу локальные.

[zaartix]

да, про бардак соглашусь, но имхо это простительно, тема совершенно новая (для меня во всяком случае), далко не все моменты очевидны. Большое спасибо за участие.