curves (splines) for drawing in OSM

chnav · 2012-05-30T13:36:04.000Z

Между двумя точками в географических координатах можно провести разные линии - дугу большого круга (Great Circle), просто прямую при небольших расстояниях, локсодрому (Rhumb Line), прямую в прямоугольных проекциях (Grid Azimuth). В зависимости от крутизны редактора/рендера может импользоваться разная математика, и если в одном редакторе две прямые не пересекаются, в другом редакторе/проекции они запросто пересекутся. Про сплайны даже думать страшно, как собираются считать их на эллипсоиде

Vovanium · 2012-05-30T16:23:47.000Z

chnav:

Между двумя точками в географических координатах можно провести разные линии - дугу большого круга (Great Circle), просто прямую при небольших расстояниях, локсодрому (Rhumb Line), прямую в прямоугольных проекциях (Grid Azimuth).

А выбрали ли «каноническую» кривую? Мне всё время чудится, что это дуга большого круга…

Ivan_Komarov · 2012-05-30T16:33:17.000Z

А мне подумалось про чуть более сложные алгоритмы, типа Point Location на Trapezoidal Map. Кажется, что со сплайнами будет полный мрак.

chnav · 2012-05-30T16:34:49.000Z

Vovanium:

Мне всё время чудится, что это дуга большого круга…

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

Кстати, очень простой пример.
Рисуем две геодезические линии (по дуге большого круга на сфере или эллипсоиде, т.е. кратчайшей прямой) с азимутом отличным от 0°, параллельные, отстоящие на десяток метров. Естественно они не пересекаются.
Одну из линий делим на отрезки (также по кратчайшей прямой, т.е. дуге большого круга) через 1-10 км и ставим на ней промежуточные точки. Линии по-прежнему не пересекаются (на эллипсоиде).
Переводим массивы координат в меркатор и любуемся результатом. А ведь это типичный результат, например, для протяженных административных границ.

PS: границы с тегом source=www.eastgeology.com имеют много промежуточных точек на “прямых” участках. Неспроста

Hind · 2012-05-30T17:31:28.000Z

Вы собираетесь проецировать кривые третьего порядка на геоид. Может, не надо? Одумайтесь! :3

Ivan_Komarov · 2012-05-30T17:56:56.000Z

как альтернативный вариант - может делать тегами подсказки для рендера? типа geo=smoothed или geo=arc на отрезках way’ев?

Mir76 · 2012-05-31T19:19:40.000Z

Я видимо, совсем тупой, плохо объясняю. Есть два принципиально разных способа прикрутить сплайн, пусть какую-то кривую Безье, на геоид.

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

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

chnav:

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

Это как это не пересекаются??? Вы нашли два непересекающихся больших круга на сфере?

Zkir · 2012-05-31T19:43:53.000Z

Mir76:

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

Это называется - была векторная карта, а стала растровая

Массовый проект должен быть простым, а сплайны/Безье это слишком сложно.

Vovanium · 2012-05-31T20:55:41.000Z

Mir76:

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

Возникает несколько ненавязчивых вопросов:
а) То есть, помимо прямого расчёта полинома 3-й степени (быстрые алгоритмы отрисовки вроде брезенхема уже ушли лесом) предлагается считать тригонометрические функции в каждой точке?
б) Что насчёт 180 меридиана?
в) Как быть с вычислением длины, площади и пр. аналитикой? Считать приближенно в лоб?

chnav · 2012-06-01T04:11:23.000Z

Mir76:

Это как это не пересекаются??? Вы нашли два непересекающихся больших круга на сфере?

Две непересекающиеся дуги (отрезка). Я этого хлебнул по горло когда рисуешь планшеты в UTM. Это совсем нетривиальная задача.

PS: Zverik очень точно подметил про растр.

chnav · 2012-06-01T04:38:35.000Z

И вообще что такое сплайн в картографии и ГИС-съемке…
Отрезок я могу измерить физическими методами, проверить рулеткой. Окружность тоже измеряется. А как в поле измеряется сплайн, какой строитель, станок или прибор способен его изготовить - я не знаю. ИМХО максимум какую кривую можно поддерживать в базе - дугу окружности. Хотя даже с ней возникнут проблемы.

Mir76 · 2012-06-01T12:38:36.000Z

Zkir:

Mir76:

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

Это называется - была векторная карта, а стала растровая

Не, не стала Я написал математическую абстракцию про каждую точку, чтобы понятней было. В реальности сплайн все равно заменится на ломаную (векторную!) и потом она спроецируется в нечто многозвенное на геоиде. Проектирование отрезка ломаной отторжения не вызывает?

Zkir:

Массовый проект должен быть простым, а сплайны/Безье это слишком сложно.

Это уже другой вопрос - “нужны ли сплайны”. Я пока говорю про “возможны ли”

Mir76 · 2012-06-01T12:50:17.000Z

Vovanium:

а) То есть, помимо прямого расчёта полинома 3-й степени (быстрые алгоритмы отрисовки вроде брезенхема уже ушли лесом) предлагается считать тригонометрические функции в каждой точке?
б) Что насчёт 180 меридиана?
в) Как быть с вычислением длины, площади и пр. аналитикой? Считать приближенно в лоб?

а) сплайн пересчитывается в ломаную, она уже по одному звену проецируется стандартными, работающими сейчас методами проецирования отрезков. Кроме того, тригонометрия считается сопроцессором очень быстро, быстрее полиномов на самом деле. Для совсем критичных приложений можно и предвычисленные тригтаблицы задействовать и даже целочисленную арифметику.
б) не вижу особых проблем. Гораздо страшнее полюса, от них лучше отрезаться, хотя бы по 80 градусу. И есть четкое желание ограничить область применения сплайнов объектами меньше 20 километров в диаметре. Берег озера, поворот дороги - что-нибудь такое.
в) способ из пункта а) сводит все эти задачи к уже решенным. Кроме того, в каждой конкретной задаче можно подумать над аналитическим решением, ускоряющим вычисления. Оно будет сильно зависеть от исходного определения сплайна.

Mir76 · 2012-06-01T15:01:55.000Z

chnav:

Рисуем две геодезические линии (по дуге большого круга на сфере или эллипсоиде, т.е. кратчайшей прямой) с азимутом отличным от 0°, параллельные, отстоящие на десяток метров. Естественно они не пересекаются.
Одну из линий делим на отрезки (также по кратчайшей прямой, т.е. дуге большого круга) через 1-10 км и ставим на ней промежуточные точки. Линии по-прежнему не пересекаются (на эллипсоиде).
Переводим массивы координат в меркатор и любуемся результатом.

А ведь здесь проблема в том, что нет четкой договоренности как именно проводить даже не сплайн - а отрезок прямой по двум концевым точкам. Даже что вообще такое - отрезок прямой на эллипсоиде. В принципе даже в меркаторе можно потребовать, чтобы отрезок соединял две точки по дуге большого круга. Тогда он выглядеть на карте будет совсем не прямым, зато с пересечениями будет более адекватно.

Vovanium · 2012-06-03T18:28:33.000Z

Mir76:

а) сплайн пересчитывается в ломаную, она уже по одному звену проецируется стандартными, работающими сейчас методами проецирования отрезков. Кроме того, тригонометрия считается сопроцессором очень быстро, быстрее полиномов на самом деле. Для совсем критичных приложений можно и предвычисленные тригтаблицы задействовать и даже целочисленную арифметику.

То есть, насколько я понимаю, приходим к следующему:
Решение не даёт преимущества, которые могли бы дать сплайны (гладкость), так как любую ломаную и так можно уже строить.
Решение создаёт дополнительные сложности в реализации.

Ilis · 2012-06-04T02:07:24.000Z

Vovanium:

Решение не даёт преимущества, которые могли бы дать сплайны (гладкость), так как любую ломаную и так можно уже строить.

Из сплайна можно получить ломанную с любой точностью. А из ломанной сплайн — нельзя.

chnav · 2012-06-04T04:50:37.000Z

Повторю свой вопрос - какими инструментами и с какой точностью можно измерить сплайн на местности.

Ilis · 2012-06-04T05:24:08.000Z

chnav:

Повторю свой вопрос - какими инструментами и с какой точностью можно измерить сплайн на местности.

Линейкой с любой наперёд заданной точностью, аппроксимируя его полилинией.

Встречный вопрос: зачем его измерять с какой-то неимоверной точностью?

chnav · 2012-06-04T07:56:12.000Z

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

grisha · 2012-06-04T08:09:59.000Z

Ilis:

Из сплайна можно получить ломанную с любой точностью. А из ломанной сплайн — нельзя.

Почему же нельзя? Полно методов нахождения сплайнов по имеющемуся набору точек, и в зависимотси от количества контрольных точек так же можно получить любую точность.
И самое интересное - все это можно сделать не затрагивая OSM. Взять например все motorway и trunk на какой-нибудь местности и преобразовать их в сплайны с погрешностью скажем в полметра. И посмотреть будет ли какое-либо преимущество по занимаемой памяти и скорости обработки по сравнению с алгоритмами на основе упрощения ломаных. И уже имея такие результаты можно либо агитировать за добавление сплайнов в OSM либо признать что это будет излишним усложнением.