You are not logged in.

#51 2011-10-26 05:35:53

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

ErshKUS wrote:

задача 5:
-менять все полигоны городов/поселков на точки
-оставить транки, примари со сьздами. Тут сложней, стандарты на классы дорог различны внутри и снаружи городов (как мне кажется), поэтому придется понижать дороги внутри городов.
-составить список обектов кому место на общей карте
-упростить линии, например ST_Simplify (постгис), но тут есть другие грабли, нужно тщательно подбирать коэфициенты и алгоритмы, т.к. упрощая, например границу России, я сократил количество точек до нужного (не помню сколько), но Кгд обл. упростилась до 5 точек (може преставить как она выглядела)
- реки тоже упростить до way

P.S. это так, краткий очерк, вдруг кому будет полезно wink

Все не  так* sad
Трудно объяснять азбуку, советую посмотреть на мапник 1-8 уровня и на карты соответствующих масштабов  в бумажном атласе.

*Кроме, разве что:
составить список объектов кому место на общей карте

Last edited by Zkir (2011-10-26 05:43:13)


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#52 2011-10-26 06:47:03

ErshKUS
Member
From: Калиниград
Registered: 2010-12-27
Posts: 803

Re: Актуальные задачи, требующие искусства программирования

Zkir wrote:

Все не  так* sad
Трудно объяснять азбуку, советую посмотреть на мапник 1-8 уровня и на карты соответствующих масштабов  в бумажном атласе.

тогда ладно, сами.
P.S. карту России видел не раз...


Ты никогда не спутаешь пути: ты стоишь...
И, может, так и нужно, но как тогда узнать, что там выше крыш?   (Lumen, Лабиринт)

Offline

#53 2011-10-26 12:33:40

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

ErshKUS wrote:

тогда ладно, сами.
P.S. карту России видел не раз...

Да, я видимо плохо объясняю.  Предется постановку задачи переработать.


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#54 2011-11-08 11:50:53

shadowjack
Member
Registered: 2008-05-05
Posts: 439

Re: Актуальные задачи, требующие искусства программирования

Сижу со сломаной ногой дома, делать особо нечего. Выбирайте - роутинг или генерализация.

Offline

#55 2011-11-08 11:55:13

Komяpa
Member
From: Minsk
Registered: 2009-04-14
Posts: 1,323
Website

Re: Актуальные задачи, требующие искусства программирования

shadowjack, генерализация дорог без потери роутинга. с фишками типа схлопывания двухвеек в синглвейки и трансформации при этом запретов поворотов. роутинг какой-никакой, всё-таки, уже есть, как и генерализация всяких лендъюзов smile
неплохо, если получится сделать это на базе osm2pgsql в --slim-импорте.

PS: сломанные ноги - это весело, сам так два раза лежал :3

Last edited by Komяpa (2011-11-08 11:55:53)


world processing is what we do.
[OSMF BY Team] [http://komzpa.net/] [jabber: komzpa@gmail.com] [mobile/SMS: +375257407159]

Offline

#56 2011-11-08 12:15:50

shadowjack
Member
Registered: 2008-05-05
Posts: 439

Re: Актуальные задачи, требующие искусства программирования

Komяpa wrote:

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

Давай подумаем, какие операции нужны для такой генерализации:
1) Склейка веев по длине
2) Двухвейка в одновейку
3) Упрощение геометрии
4) Схлопывание развязок

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

EDIT: Вот еще подумал. Кажется, не с того конца беремся. Смысл упрощать OSM->OSM с сохранением роутинга? Не лучше ли отдельно упрощать роутинговый граф (а фиг его упростишь кроме тривиальных вещей) и отдельно векторный слой карты. Во втором случае можно с двухвейками особо и не морочиться - подумаешь, будут два вея поверх друг друга отрисованы. Упростить геометрию, да и дело с концом.
Единственный момент - какие хайвеи выбросить. Выброшеные хайвеи не должны влиять на связность сети, а могут влиять только на локальный роутинг. По этому поводу у меня где-то была статья по теме "Highway hierachies". Кстати, там они получали роутинг по полной статической карте европейской страны за время в единицы миллисекунд.

Last edited by shadowjack (2011-11-08 13:44:10)

Offline

#57 2011-11-08 15:53:04

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

shadowjack wrote:

Нужно ли сохранять, скажем, в п.п. 1 и 4 ограничения скорости и прочие атрибуты дорожной сети на кусках дорог?

Нет, не обязательно. Хотя было бы вкусно.

По п.2 - как определить, что два набора веев - это на самом деле одна дорога?

Это самый главный вопрос и есть. Видимо, по близости, при том что объединяемые веи односторонние и разнонаправленные. Одинаковые значения name/ref тоже должны намекнуть.

Смысл упрощать OSM->OSM с сохранением роутинга? Не лучше ли отдельно упрощать роутинговый граф (а фиг его упростишь кроме тривиальных вещей) и отдельно векторный слой карты.

Затем, чтобы получить обзорную карту разумного размера, пригодную для навигации (в навигаторах).  OSM->OSM здесь для того, чтобы можно было сделать OSM->MP стандартными средствами, а не изобретать импорт из постгис/шейпов.

Разумеется, генерализация дорожного графа и лесов-болот - две разные подзадачи.

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

Во втором случае дороги вообще не актуальны. Важен первый случай. smile

Единственный момент - какие хайвеи выбросить.

Выбрасывать по статусу. Для начала выкинуть tertiary и ниже.

Last edited by Zkir (2011-11-08 15:55:14)


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#58 2011-11-08 16:12:42

shadowjack
Member
Registered: 2008-05-05
Posts: 439

Re: Актуальные задачи, требующие искусства программирования

Какая конечная цель по количеству нодов/веев на обзорку России?
EDIT: имеется в виду, по дорожной сети.

Last edited by shadowjack (2011-11-08 16:22:51)

Offline

#59 2011-11-08 17:37:28

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,787

Re: Актуальные задачи, требующие искусства программирования

Zkir wrote:

По п.2 - как определить, что два набора веев - это на самом деле одна дорога?

Это самый главный вопрос и есть. Видимо, по близости, при том что объединяемые веи односторонние и разнонаправленные. Одинаковые значения name/ref тоже должны намекнуть.

Думаю, разнонаправленность тут большой рояли не играет - можно просто объединять все одноименные линии одного класса в рамках заданного расстояния.  ИМХО, самое сложное тут - это вычислять потом запреты, куда можно повернуть, а куда нет, где осталась однонаправленная линия, а где нет....

Last edited by Sergey Astakhov (2011-11-08 17:38:40)

Offline

#60 2011-11-08 17:44:48

dkiselev
Member
Registered: 2010-02-09
Posts: 3,364

Re: Актуальные задачи, требующие искусства программирования

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


mail: dkiselev@osm.me      skype: dmitry.v.kiselev
Open Street Maps are supreme! Exterminate all map forms! Exterminate! Exterminate!

Offline

#61 2011-11-08 17:57:09

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,787

Re: Актуальные задачи, требующие искусства программирования

dkiselev wrote:

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

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

Offline

#62 2011-11-08 18:13:23

dkiselev
Member
Registered: 2010-02-09
Posts: 3,364

Re: Актуальные задачи, требующие искусства программирования

Да я уже понял что проблемы не тут. Я вот к примеру даже на бумажке слабо представляю себе как схлопнуть двухвейку с дублерами каждого направления. НАдо порисовать такое на бумажке и пообсуждать - тогда и алгоритм начнет более ли менее вытанцовываться.

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

Last edited by dkiselev (2011-11-08 18:18:46)


mail: dkiselev@osm.me      skype: dmitry.v.kiselev
Open Street Maps are supreme! Exterminate all map forms! Exterminate! Exterminate!

Offline

#63 2011-11-08 18:30:07

Dinamik
Member
Registered: 2010-08-12
Posts: 1,096

Re: Актуальные задачи, требующие искусства программирования

dkiselev wrote:

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

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

Offline

#64 2011-11-08 18:30:45

dkiselev
Member
Registered: 2010-02-09
Posts: 3,364

Re: Актуальные задачи, требующие искусства программирования

И еще вопрос который лежит вне алгоритма - на сколько мы готовы пожертвовать эквивалентностью преобразования? Т.е. если вот тут http://osm.org/go/2YpZH_Kd@-- схлопнуть Малышева и выкинуть второстепенки (а именно сервис петельку под мостом) то стремясь сделать преобразование эквивалентными нужно перекресток со студенческой преоброзовать в обычный (где разрешены все маневры) - это правильно для роутинга но алгоритм усложняет на порядок.


mail: dkiselev@osm.me      skype: dmitry.v.kiselev
Open Street Maps are supreme! Exterminate all map forms! Exterminate! Exterminate!

Offline

#65 2011-11-08 19:40:45

Komяpa
Member
From: Minsk
Registered: 2009-04-14
Posts: 1,323
Website

Re: Актуальные задачи, требующие искусства программирования

1. порубить карту на тайлы, так, чтобы в каждый тайл попадала одна развязка целиком
2. найти пересечение всех дорог с границей тайла
3. сгенерировать перекресток, состоящий из линий, сходящихся в центр масс всех дорог внутри тайла.
4. расставить на сгенерированном перекрёстке запреты так, чтобы соединения, по которым запрещён проезд в исходном графе, нельзя было пройти в сгенерированном.


world processing is what we do.
[OSMF BY Team] [http://komzpa.net/] [jabber: komzpa@gmail.com] [mobile/SMS: +375257407159]

Offline

#66 2011-11-08 22:15:45

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

dkiselev wrote:

И еще вопрос который лежит вне алгоритма - на сколько мы готовы пожертвовать эквивалентностью преобразования? Т.е. если вот тут http://osm.org/go/2YpZH_Kd@-- схлопнуть Малышева и выкинуть второстепенки (а именно сервис петельку под мостом) то стремясь сделать преобразование эквивалентными нужно перекресток со студенческой преоброзовать в обычный (где разрешены все маневры) - это правильно для роутинга но алгоритм усложняет на порядок.

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

Эквивалентное преобразование в данном случае такое.
1. Малышева становится одновейной.
2. Перекресток Малышева и Студенческой становится точкой.
3. На этом перекрестке ставятся следующие запреты - со Студенческой с обоих сторон на Малышева только направо, проезд прямо по студенческой закрыт. С Малышева на Студенческую левые повороты с обоих сторон запрещены.

И опять же, в обзорной карте  residential и даже tertiary не нужен. Так что запретов должно стать не больше, а меньше.


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#67 2011-11-08 22:16:45

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

shadowjack wrote:

Какая конечная цель по количеству нодов/веев на обзорку России?
EDIT: имеется в виду, по дорожной сети.

Скажем так, до 50000 ребер в дорожном графе, причем ребро понимается как кусок дороги между перекрестками.


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#68 2011-11-08 22:25:52

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

Komяpa wrote:

1. порубить карту на тайлы, так, чтобы в каждый тайл попадала одна развязка целиком
2. найти пересечение всех дорог с границей тайла
3. сгенерировать перекресток, состоящий из линий, сходящихся в центр масс всех дорог внутри тайла.
4. расставить на сгенерированном перекрёстке запреты так, чтобы соединения, по которым запрещён проезд в исходном графе, нельзя было пройти в сгенерированном.

1. Выбрать из базы дороги trunk-secondary и соответствующие им линки.
2. Нарезать всю карту на гексагональные ячейки (например, километрового диаметра).
3. Если по исходному графу можно попасть  из данной ячейки в соседнюю, создать в обобщенном графе ребро, соединяющее центры этих ячеек.
4. Выполнить п.3 для всех ячеек.
5. Упростить форму получившегося графа дуглас-пойкером.
smile

Last edited by Zkir (2011-11-08 22:26:45)


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

#69 2011-11-09 05:32:46

dkiselev
Member
Registered: 2010-02-09
Posts: 3,364

Re: Актуальные задачи, требующие искусства программирования

Zkir wrote:

Эквивалентное преобразование в данном случае такое.
1. Малышева становится одновейной.
2. Перекресток Малышева и Студенческой становится точкой.
3. На этом перекрестке ставятся следующие запреты - со Студенческой с обоих сторон на Малышева только направо, проезд прямо по студенческой закрыт. С Малышева на Студенческую левые повороты с обоих сторон запрещены.

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

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


mail: dkiselev@osm.me      skype: dmitry.v.kiselev
Open Street Maps are supreme! Exterminate all map forms! Exterminate! Exterminate!

Offline

#70 2011-11-09 06:29:28

dimuzz
Member
From: Екатеринбург
Registered: 2009-09-10
Posts: 1,843

Re: Актуальные задачи, требующие искусства программирования

dkiselev wrote:

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

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

Имхо, это скорее значит, что петля под мостом - не service.

Offline

#71 2011-11-09 07:19:08

fserges
Member
From: St.Petersburg/Russia
Registered: 2010-11-08
Posts: 3,999

Re: Актуальные задачи, требующие искусства программирования

Рискну показаться непонятым ... но известен принцип - кому надо тот и делает. Пока Zkir сам не сделает, вряд ли он признает результаты генерализации приемлимыми smile Поясню.

Любая сложная задача это постоянный поиск компромисса. Генерализация одна из сложнейших задач и её принципиальная особенность - гибкие требования к генерализации. Поэтому генерализация карты это итеративный процесс и постоянная смена правил с целью поиска оптимального решения. Человек ставящий задачу не может создать полный комплекс правил по генерализации. Тогда как человек алгоритмизирующий генерализацию вынужден сам решать где и как проводить компромисс. В результате постановщик ТЗ в голове будет иметь одно а главный разработчик совсем другое smile

Так шта пока Zkir не напишет ОЧЕНЬ чёткое ТЗ на задачу он не получит приемлимого для себя результаты. И будет на всех форумах писать что нет у нас нормальных программистов smile


Бывший редактор ОСМ

Offline

#72 2011-11-09 07:33:56

Sergey Astakhov
Member
From: St.Petersburg, Russia
Registered: 2009-11-13
Posts: 5,787

Re: Актуальные задачи, требующие искусства программирования

fserges wrote:

В результате постановщик ТЗ в голове будет иметь одно а главный разработчик совсем другое smile

Так шта пока Zkir не напишет ОЧЕНЬ чёткое ТЗ на задачу он не получит приемлимого для себя результаты. И будет на всех форумах писать что нет у нас нормальных программистов smile

Это вы сейчас описали "водопадную" модель разработки, которая была признана некошерной ещё десятки лет назад. С тех пор много воды в этих "водопадах" утекло, так сейчас никто в здравом уме не делает.  Последовательные итерации и обратная связь - вот ключ к успеху. smile

Offline

#73 2011-11-09 07:36:10

fserges
Member
From: St.Petersburg/Russia
Registered: 2010-11-08
Posts: 3,999

Re: Актуальные задачи, требующие искусства программирования

Sergey Astakhov wrote:

Это вы сейчас описали "водопадную" модель разработки, которая была признана некошерной ещё десятки лет назад. С тех пор много воды в этих "водопадах" утекло, так сейчас никто в здравом уме не делает.  Последовательные итерации и обратная связь - вот ключ к успеху. smile

Так я говорю что в конечном счёте (с какой-то итерации) код допиливать придётся Zkir wink


Бывший редактор ОСМ

Offline

#74 2011-11-09 09:35:24

LinFor
Member
From: Moscow
Registered: 2011-10-17
Posts: 155

Re: Актуальные задачи, требующие искусства программирования

Sergey Astakhov wrote:
fserges wrote:

В результате постановщик ТЗ в голове будет иметь одно а главный разработчик совсем другое smile
Так шта пока Zkir не напишет ОЧЕНЬ чёткое ТЗ на задачу он не получит приемлимого для себя результаты. И будет на всех форумах писать что нет у нас нормальных программистов smile

Это вы сейчас описали "водопадную" модель разработки, которая была признана некошерной ещё десятки лет назад. С тех пор много воды в этих "водопадах" утекло, так сейчас никто в здравом уме не делает.  Последовательные итерации и обратная связь - вот ключ к успеху. smile

Ага, щазззз, видимо ПО для сегодняшнего "Фобос-Грунт" как раз по agile-модели писали - "не долетит - в следующей итерации ещё один запустим"....

Offline

#75 2011-11-09 09:53:35

Zkir
Member
From: Хрустальная Москва
Registered: 2009-02-21
Posts: 6,110

Re: Актуальные задачи, требующие искусства программирования

Задача генерализации дорожного графа хорошо формализуется и описана в этой теме уже раза три-четыре.
Могу еще раз:
1. Выбрать из базы дороги определенного уровня (по значению тега highway), и соответствующие им развязки (xxx_link) и запреты поворотов, остальные выкинуть. (это исходный граф). Например, взять secondary и выше, а tertiary и ниже - выкинуть.
2. Двухвейки переделать в одновейки, развязки (xxx_link) стянуть в точки. Расставить запреты, для сохранения эквивалентности рутинга с исходным графом.
3. Упростить геометрию получившихся дорог, сократив количество промежуточных точек, до требуемой величины. Точки перекрестков, при этом, естественно, не выкидываются. Это конечный граф.
4. Вот, собственно, и все.

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

dkiselev wrote:

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

Если имеются ввиду ID объектов в осм, то нет.

Last edited by Zkir (2011-11-09 09:54:21)


Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.

Offline

Board footer

Powered by FluxBB