Разбиение отрезка на сфере на части с заданным шагом

[OlegZhdanov]

Добрый день! Ситуация такая: есть приложение на java c БД postgis. Необходимо разбить отрезок на сфере (или сфероиде) на равные части (входные данные - две точки на карте и шаг) с заданным шагом. На выходе требуется массив точек, равноудалённых друг от друга.

Вопрос: есть ли реализация данной задачи на postgis?
Или как реализовать расчёт на java?

[drug]

Рекомендую использовать параметрическую форму задания отрезка. Еще это называют твинингом от англ. twining. То что нужно в вашем случае. Для одной координаты Х это будет выглядеть так:

Код: Выделить всё

x = x1 + (x2 - x1)*t

где t - параметр от 0 до 1, х1 - координата первой точки, х2 координата второй. На D я пишу так:

Код: Выделить всё

auto tween(P, T)(P p0, P p1, T t)
{
    auto x = p0.x + (p1.x - p0.x)*t;
    auto y = p0.y + (p1.y - p0.y)*t;
    auto z = p0.z + (p1.z - p0.z)*t;

    return P(x, y, z);
}

Т.е. получаю две точки p1 и p2 и параметр t от 0 до 1. Функция возвращает точку, соответствующую t. В случае сферических координат то же самое, только замените x, y, z на lon, lat и alt.

З.Ы. Если параметр меньше нуля то будет возвращена точка левее р1, а если больше 1 то правее р2, т.е. будет осуществляться экстраполяция вместо интерполяции.

[gamm]

В случае сферических координат то же самое, только замените x, y, z на lon, lat и alt.

не получится, нужно строить дугу, и ее нарезать - как это делать, написано в учебнике геометрии за 7 класс.

[Игорь Белов]

Необходимо разбить отрезок на сфере (или сфероиде) на равные части (входные данные - две точки на карте и шаг) с заданным шагом.

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

В случае сферических координат то же самое, только замените x, y, z на lon, lat и alt.

Решением будут точки, не лежащие ни на ортодромии, ни на локсодромии, и расстояния между ними на сфере будут разными.

На выходе требуется массив точек, равноудалённых друг от друга. Вопрос: есть ли реализация данной задачи на postgis? Или как реализовать расчёт на java?

Про PostGIS не знаю. В общем случае для геодезической линии задача решается последовательным вычислением одной обратной геодезической задачи и нескольких прямых. Для сферы можно обойтись одним пуском консольной утилиты PROJ.4 geod:

Код: Выделить всё

$ geod -f "%.6f" +a=6378137 +lat_1=широта_1 +lon_1=долгота_1 +lat_2=широта_2 +lon_2=долгота_2 +n_S=число_сегментов

На выходе будут широты и долготы равноудалённых точек. Значение параметра +a неважно, но он (или +ellps и т.п.) должен быть.

Если непременно нужны эллипсоид и Java, воспользуйтесь библиотекой GeographicLib. Кстати, она войдёт в PROJ.4 с версии 4.9.0, и geod сможет делать вычисления на эллипсоиде.

[drug]

В случае сферических координат то же самое, только замените x, y, z на lon, lat и alt.

не получится, нужно строить дугу, и ее нарезать - как это делать, написано в учебнике геометрии за 7 класс.

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

Решением будут точки, не лежащие ни на ортодромии, ни на локсодромии, и расстояния между ними на сфере будут разными.

Ребята, вы о чем? Где сказано про ваши предположения в условиях? Ответ более чем адекватен вопросу, не нужно обвинять и судить других, первый раз сталкиваюсь на этом форуме с подобным. Будут уточнения по задаче, будем уточнять решение. Лично я сталкивался с задачей именно с подобной формулировкой и именно такое было решение - не поверите, работает больше 10 лет! И никто не тыкал мне в лицо учебником геометрии и не рассказывал, каким сложным может быть мир - в нем есть, оказывается, ортодромия и локсодромия! Простите, что на минутку уподобился вам. Вырвалось, за рабочий день накипело.

[gamm]

Где сказано про ваши предположения в условиях?

вот здесь:

Необходимо разбить отрезок на сфере (или сфероиде)

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

[drug]

Где сказано про ваши предположения в условиях?

вот здесь:

Необходимо разбить отрезок на сфере (или сфероиде)

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

Чтобы задать дугу нужна аналитическая формула и две точки, задающие ее начало и конец. В сферической системе координат получить эти точки на сфере можно без проблем с помощью вышеприведенной мною формулы. Какую аналитическую форму вы выберете - в виде отрезка дуги или отрезка прямой никак не влияет на координаты точек и вышеупомянутая формула будет корректна в любом случае. Более того, посмею утверждать, что очень часто дуга аппроксимируется именно прямой или ломаной из нескольких отрезков. При выводе графики достаточно выбрать подходящую длину отрезков, а при аналитических расчетах, как я уже сказал, координаты точек, тем более, не зависят от формы представления дуги. Искренне не понимаю о чем вы. Вы пробовали решать эту задачу или вам просто показалось что вы поймали меня на элементарной ошибке и ограничились постом, не вникая в тему? Если вы разобьете отрезок на сфере, например, от 0 до 30 на отрезки по 3 градуса у вас получатся 10 равных отрезков также на сфере. Как вы их будете интерпретировать - как дуги или отрезки, здесь вообще ортогонально. Но вдруг я ошибаюсь? Буду рад если вы меня аргументированно поправите. Обязательно внесу изменения в код, торжественно обещаю При этом гарантирую, что в коммите сошлюсь на вас.

[gamm]

В сферической системе координат получить эти точки на сфере можно без проблем с помощью вышеприведенной мною формулы.

не совсем так - ваши точки на сфере, но распределены неравномерно. Из учебника геометрии за 7 класс следует, что если точки распределены на дуге равномерно (с одинаковым шагом), то и расстояние между ними должно быть одинаковое. В вашем случае это не так. А почему не так - вам может объяснить тов. ErnieBoyd , если оно вам надо. Как я уже сказал, у нас свободная страна.

Ниже скриптик на R, для усиления эффекта взята достаточно длинная дуга

Код: Выделить всё

ll2xyz=function(lat,lon) {
  R=6371.032;
  lat=lat/180*pi;  
  lon=lon/180*pi;  
  z=R*sin(lat)
  r=R*cos(lat)
  x=r*cos(lon)
  y=r*sin(lon)
  c(x,y,z)
}

lon=seq(10,60,len=10)
lat=seq(10,20,len=10)
coord=matrix(ll2xyz(lat,lon),ncol=3)

# убеждаемся, что точки лежат на сфере
summary(sqrt(rowSums(coord^2)))
#   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
#   6371    6371    6371    6371    6371    6371

# убеждаемся, что расстояния между ними разные
foo=cbind(diff(coord[,1]),diff(coord[,2]),diff(coord[,3]))
summary(sqrt(rowSums(foo^2)))
#   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
#  595.2   602.6   609.1   608.4   614.7   619.5

т.е. для длин имеем
Min. 1st Qu. Median Mean 3rd Qu. Max.
595.2 602.6 609.1 608.4 614.7 619.5

разница от среднего примерно 2%. И все из-за какой-то идиотской лаксодромии с ортодромией ...

[drug]

Да? Простите, но мне без R ясно, что расстояние между точками на сфере в сферической системе координат, полученные путем твиннинга всегда будут равными в той же СК. Где сказано, что равномерность должна соблюдаться в прямоугольной СК? Вы не задумывались, что может быть достаточно равномерности в сферической СК?
Еще раз обращаю ваше внимание, что для такого общего условия как у ТС более чем достаточно приведенного мною решения, с которым ваши выкладки не имеют ничего общего к тому же. Если же вы мне покажете, что невозможно твиннигом между двумя точками в сферической СК получить равномерно распределенные точки на сфере, я сниму шляпу перед вами. Если же у вас нет такой возможности, тогда постарайтесь в следующий раз просто дополнять ответы других. А замечания делайте только в том случае, если у вас действительно есть аргументы против.

[gamm]

Еще раз обращаю ваше внимание, что для такого общего условия как у ТС более чем достаточно приведенного мною решения, с которым ваши выкладки не имеют ничего общего к тому же.

еще раз возвращаемся к учебнику геометрии для 7 класса ...

1) Дуга, соединяющая 2 точки, есть часть сечения шара, проходящего через центр (дуга большой окружности)
2) На плоскости этого сечения дуга является дугой окружности, все точки дуги лежат в этой плоскости
3) Расстояние между точками дуги в 3D равно расстоянию на этой плоскости
4) Если точки распределены на дуге окружности равномерно, то и расстояния между ними равны
5) То, что вы привели, решением не является, поскольку расстояния разные

как-то так ... поскольку у ТС черным по русски написано На выходе требуется массив точек, равноудалённых друг от друга.

[Игорь Белов]

Внесу свой скромный лепт в разгоревшуюся дискуссию.

На картинках по два решения для трёх линий: зелёные точки — фактически «твининг», красные расставлены по кратчайшей линии.

Первая картинка — «долгота/широта».

Cylindrical equidistant projection

map_geog.png (88.92 КБ) 10103 просмотра

На второй картинке видим глобус, глаз над начальной точкой.

Orthographic projection

map_ortho.png (145.97 КБ) 10114 просмотров

В целом такой «твининг» применим с определёнными погрешностями для коротких линий в умеренных широтах.

[drug]

Ребята, вы читаете что я пишу? А писал я о том, что решал задачу с подобной формулировкой. И в ней равноудаленность нужна была в сферических координатах. Более чем достаточное решение было. Нигде у ТС не указано на равноудаленность именно в прямоугольных координатах. Мое решение, как и ваше является частным случаем. Просто я сталкивался со своим случаем и привел свое решение, вы - с другим случаем и привели свой. Отличие в том, что я не учу других жизни. И вам не советую.

P.S. и не стоит брать твининг в кавычки, дескать брезгуете. Это устоявшийся термин. А если вас удивляет, что при переходе от сферической СК к прямоугольной возникают искажения, то хотя бы не стоит приписывать это параметрической форме кривых, на которой основан твининг. Это тоже более чем устоявшаяся форма.

[gamm]

А писал я о том, что решал задачу с подобной формулировкой. И в ней равноудаленность нужна была в сферических координатах.

не читаете как раз вы, то что написано у ТС. Я не исключаю, что вы расстояние измеряете в градусах, а площади - в квадратных градусах. Это ваше право, у нас свободная страна. Но если взять наконец учебник геометрии за 7 класс, то вы узнаете, что расстояние измеряется по дуге большого круга, а если равны дуги, то равны и хорды (которые я для вас любезно посчитал). И если хорды не равны, то и расстояния не равны (если для вас это новость, то читаем учебник геометрии за 7 класс). ТС нужна равноудаленность точек друг от друга. Чего в вашем решении нет, и на что вам любезно указали. Как теоретически, так и численным примером.

P.S. человеку, знакомому с геометрией, я бы просто сказал, что приращение расстояния по широте постоянно, а по долготе зависит от широты, от чего расстояния получаются разные. Для вас я привел численный пример.

P.S. Судя по фразе "И в ней равноудаленность нужна была в сферических координатах" и рассуждения о искажениях при переходе к декартовым, вы просто не в курсе, что расстояние инвариантно относительно систему координат (не меняется при правильном изменении системы координат). Либо вы придумали какие-то свои "сферические координаты", в которых расстояние измеряется не в метрах, а в чем-то еще. Если это так, то сообщите где такое чудо описано - никогда не встречал.

[OlegZhdanov]

Всем спасибо, решил задачу с помощью функций postgis