You are not logged in.
- Topics: Active | Unanswered
Announcement
*** NOTICE: forum.openstreetmap.org is being retired. Please request a category for your community in the new ones as soon as possible using this process, which will allow you to propose your community moderators.
Please create new topics on the new site at community.openstreetmap.org. We expect the migration of data will take a few weeks, you can follow its progress here.***
Please create new topics on the new site at community.openstreetmap.org. We expect the migration of data will take a few weeks, you can follow its progress here.***
#201 2012-11-09 21:52:01
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
andriano wrote:
Если требуется, чтобы в эту точку мог быть проложен маршрут, она должна быть вершиной графа.
Вот чего не требуется, так как раз этого
Все известные науке практические рутеры умеют опускать перпендикуляр на рутинговое ребро.
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#202 2012-11-09 22:10:42
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
OverQuantum wrote:
Инфа о багах и явных некорректных схлопываниях - привествуется.
Какая-то лажа в районе Расторгуевского шоссе.
http://www.openstreetmap.org/?lat=55.55 … 3&layers=M
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#203 2012-11-10 05:58:49
- chnav
- Member
- From: Russia, mapping Kazakhstan
- Registered: 2010-03-18
- Posts: 3,303
Re: Актуальные задачи, требующие искусства программирования
andriano wrote:
OverQuantum wrote:Если дорога прямая как линия, её можно задать двумя точками, т.е. 1 отрезком.
Вообще говоря, если даже дорога извилистая как кишечник парнокопытного, то с точки зрения дорожного графа ее следует также представлять двумя точками: начальной и конечной, а также длиной (в теории графов называемой весом ), которая, понятное дело, для извилистой дороги не будет совпадать с расстоянием между этими точками.
Всё верно, именно это происходит в момент _компиляции_ карты. А промежуточный формат - полиш - может оставаться любой извилистости.
Offline
#204 2012-11-10 12:52:49
- andriano
- Member
- Registered: 2009-06-15
- Posts: 1,667
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
Все известные науке практические рутеры умеют опускать перпендикуляр на рутинговое ребро.
Я не писал все эти "известные науке роутеры", но предполагаю, что что задача построения маршрута разбивается ими на ряд подзадач (для простоты - только для "дальних" маршрутов, где, собственно, только и нужен генерализованный граф):
1. Нахождение ближайших вершин генерализованного роутингового графа к начальной и конечной точкам.
2. Нахождение пути между найденными вершинами.
3. Нахождение точки, в которой граница локального (полного) подграфа пересекается с найденным маршрутом.
4. Нахождение кратчайшего пути по локальному (полному) подграфу между начальной/конечной точкой и точкой, найденной в п.3.
Таким образом, мы сейчас рассматриваем этап 2, в котором "опускание перпендикуляра" не предусмотрено.
А нахождение ближайшей точки локального роутингово подграфа - это часть этапа 4, который производится не по генерализованному, а по полному графу ограниченного фрагмента местности (который содержит все дороги).
Здесь есть еще один интересный момент: генерализованный граф находится в ОП постоянно (и не изменяется), а локальные полные графы - подгружаются по мере необходимости (в частности, в процессе ведения по маршруту), поэтому внесение изменения в локальный граф - включение в него "стартовой" точки, вероятно, с разбиением одного ребра на два (куда опускается перпендикуляр) и добавлением дополнительного ребра (тот самый перпендикуляр) не нарушает целостности данных. Т.к. эти данные при следующем использовании все равно будут переподгружены с диска.
Поэтому этапы 2 и 4 могут быть осуществлены одним и тем же алгоритмом - поиском пути исключительно между вершинами.
Last edited by andriano (2012-11-10 12:56:17)
Offline
#205 2012-11-10 13:06:32
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
Какая-то лажа в районе Расторгуевского шоссе.
http://www.openstreetmap.org/?lat=55.55 … 3&layers=M
Всё по исходным данным RU-OVRV.mp, которые от 3 октября.
1) 30094742 до 4 октября было tertiary и в выгрузку не вошло.
2) Расторгуевское шоссе до 5 ноября было primary_link и схлопнуто.
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#206 2012-11-10 13:28:35
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
OverQuantum,
Всё по исходным данным RU-OVRV.mp, которые от 3 октября.
Хорошо, я понял)
Я посмотрел те места которые знаю, получилось очень прилично. Даже не знаю к чему еще придраться. 
Есть белые вершины (которые в конечной карте не нужны), но это похоже опять к исходным данным.
Принципиальный вопрос. Можно сделать, чтобы алгоритм оставлял номера трасс [Е95], [M8]?
Чтобы результат работы алгоритма мог быть использован вместо RU-OVRV.mp для обзорной карты РФ, номера трасс крайне желательны.
Last edited by Zkir (2012-11-10 13:29:29)
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#207 2012-11-10 14:15:46
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
Есть белые вершины (которые в конечной карте не нужны), но это похоже опять к исходным данным.
Либо тип дорог разный с разных сторон белых вершин, либо скоростной класс разный.
Zkir wrote:
Принципиальный вопрос. Можно сделать, чтобы алгоритм оставлял номера трасс [Е95], [M8]?
Можно, в том числе весь Label сохранять.
Основной вопрос - что делать, если объединяются дороги с разными названиями?
Вот на скриншотах - Проектируемый проезд N 552 переходит в Новобутовскую улицу.
Не объединять - не здорово, есть подозрение, что много чего не объединится из-за мелких различий в написании, даже если только номера трасс.
Например, около Нижнего есть отрезки "E22,M7,М7", а есть "E22,M7" и "E22".
Выбирать название мажоритарно по количеству отрезков - пойдёт?
Last edited by OverQuantum (2012-11-10 14:18:47)
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#208 2012-11-10 14:46:27
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
Либо тип дорог разный с разных сторон белых вершин, либо скоростной класс разный.
Окей)
Можно, в том числе весь Label сохранять.
Супер. Названия улиц попали в Label скорее по недосмотру, они в обзорной карте не нужны. А вот номера дорог, ака ref=* нужны)
Основной вопрос - что делать, если объединяются дороги с разными названиями?
Хотелось бы увидеть два варианта - а) мажоритарный выбор б) суммирование. "E22,M7,М7"+ "E22,M7" + "E22" = "E22,M7,М7".
Last edited by Zkir (2012-11-10 14:47:02)
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#209 2012-11-10 16:48:23
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
andriano wrote:
Нахождение пути между найденными вершинами.
Этот разговор для меня слишком абстрактный)
Скажу только, что обычно путь ищется не между вершинами*), а между точками лежащими на ребрах, причем в произвольных местах.
*) Под "вершиной графа" обычно понимается перекресток, тупик, или соединение двух дорог -- на скриншотах выше вершины отмечены разноцветными квадратиками.
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#210 2012-11-10 21:05:47
- andriano
- Member
- Registered: 2009-06-15
- Posts: 1,667
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
Скажу только, что обычно путь ищется не между вершинами*), а между точками лежащими на ребрах, причем в произвольных местах.
Насколько мне известно, путь ищется только между вершинами. А если обязательно нужно найти путь до чего-то еще, то это что-то превращается в вершину.
Просто потому, что никаких точек в графе нет вообще, поэтому и лежать на ребрах они никак не могут. Вес ребра - это лишь "цена" перехода из одной вершины в другую, для которой, а само название "ребро" - не совсем точная геометрическая интерпретация сущности, которую нельзя разделить на части.
Например, нельзя купить 2/3 билет в кино. Точно так же нельзя и отложить 2/3 длины ребра. Но можно одно ребро разбить на два, вставив между ними дополнительную вершину.
Offline
#211 2012-11-12 15:02:17
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
Хотелось бы увидеть два варианта - а) мажоритарный выбор б) суммирование. "E22,M7,М7"+ "E22,M7" + "E22" = "E22,M7,М7".
Мажоритарный вариант всю МКАД превращает в Е22
Комбинаторный вариант всю МКАД превращает в E30,E105,E22
Сиё вызвано тем, что двухвейка схлопывается в одновейку вся целиком за один раз (да, вся МКАД за 1 раз) и скоростной класс и название считается 1 раз по всем исходным отрезкам и выставляется всем отрезкам итоговой одновейки.
Можно попробовать схлопывать по-отрезочно, но как раз циклические дороги представляют порядочную проблему для по-отрезочного анализа.
UPD: Файлы удалены в пользу след. поста.
Last edited by OverQuantum (2012-11-14 20:50:44)
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#212 2012-11-14 20:49:40
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir,
Сделал схлопывание с более корректным сохранением названия.
Мажоритарный вариант, комбинаторный вариант.
Разница мизерная, в комбинаторном нашёл только сегмент "Р108,P107". Я бы оставил комбинаторный.
Если устраивает, то у меня вопросы по финализации задачи
1) Небольшая часть процедур работает в lat/lon координатах и их переклинит на границе lon=180/-180 и у полюсов.
(рассчёт центроида развязки, перебор точек по bbox-у, проэцирование точки на линию и т.п.)
Насколько я вижу, сейчас объекты 180/-180 не пересекают, так что особой надобности сделать весь алгоритм устойчивым к границе 180/-180 не требуется.
Большая же часть работает через расстояние по сфере WGS84 и проблем испытывать не будет.
2) Устроит ли лицензия GPL v3?
3) Устроит ли реализация на C или C++?
Perl я почти не умею, Java сильно не люблю.
Сейчас всё на скрипте. На C/C++ могу переписать сам. Уточните только - лучше чистый C или можно наворачивать объектные конструкты С++.
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#213 2012-11-14 21:39:00
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
Да, комбинаторный вариант мне нравится больше. К чему придраться я не знаю, так что устраивает
1) Наверно это не важно. На крайняк можно будет отрезать)
2) Да, вполне.
3) А что за скрипт? Он под виндой работает?
И вот еще что. Совсем об этом забыл, но оно важно. Можно сделать описание алгоритма на человеческом языке?
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#214 2012-11-14 21:49:37
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
3) А что за скрипт? Он под виндой работает?
VB6 
Атлична работает под виндой, особенно если собрать в exe-шник. Из исходников - только в интерпретаторе.
Zkir wrote:
Можно сделать описание алгоритма на человеческом языке?
Объёмом до 1 страницы - могу написать. Детальнее - нужно будет расписывать подробности алгоритмической реализации, не вижу особого смысла делать это в отдельном тексте, т.к. в исходниках будут довольно подробные комментарии на функции (но на английском).
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#215 2012-11-14 22:11:20
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
...
Last edited by Zkir (2012-11-14 22:13:05)
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#216 2012-11-14 22:12:11
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
OverQuantum wrote:
VB6
Хорошо вовремя спросил. Если VB6 (не VBScript) то и переписывать никуда (особливо на С++) не надо.
Приму как есть)
Объёмом до 1 страницы - могу написать.
Годится.
в исходниках будут довольно подробные комментарии на функции (но на английском).
Супер.
Last edited by Zkir (2012-11-14 22:12:46)
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#217 2012-11-14 22:35:06
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
Хорошо вовремя спросил. Если VB6 (не VBScript) то и переписывать никуда (особливо на С++) не надо.
Приму как есть)
VB6, не VBScript.
Э... ладно.
Просто код несколько наколеночный, экспериментальный - для проверки идей и работоспособности алгоритмов. Данные лежат в глобальных массивах, goto местами насыпано и т.п.
Ещё я посмотрю, можно ли на код VB6 вешать GPL v3.
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#218 2012-11-14 22:47:39
- Sergey Astakhov
- Member
- From: St.Petersburg, Russia
- Registered: 2009-11-13
- Posts: 5,817
Re: Актуальные задачи, требующие искусства программирования
OverQuantum wrote:
3) Устроит ли реализация на C или C++?
Perl я почти не умею, Java сильно не люблю.
Жаль.
Ваш бы код да в виде плугина к osmosis...
Offline
#219 2012-11-14 22:55:35
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Sergey Astakhov wrote:
Жаль.
Ваш бы код да в виде плугина к osmosis...
Я готов отдать весь приз за эту задачу тому кто перепишет код на Java
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#220 2012-11-14 23:37:28
- Sergey Astakhov
- Member
- From: St.Petersburg, Russia
- Registered: 2009-11-13
- Posts: 5,817
Re: Актуальные задачи, требующие искусства программирования
OverQuantum wrote:
Я готов отдать весь приз за эту задачу тому кто перепишет код на Java
Добрый ты - "Данные лежат в глобальных массивах, goto местами насыпано и т.п."
Offline
#221 2012-11-15 08:07:04
- Zkir
- Member
- From: Хрустальная Москва
- Registered: 2009-02-21
- Posts: 6,110
Re: Актуальные задачи, требующие искусства программирования
Так вы меня без решения задачи оставите.
VB6 (если РФ проходит по требуемой памяти) меня более чем устраивает. На java желающие сами перепишут.
По финализации задачи:
1. Выложить код на гитхаб.
2. Сделать описание алгоритма в пределах одной странички текста. Выложить туда же.
3. Прислать мне через ОСМ почту свой телефон для связи
4. Я проверю что код компилится и работает
5. Если все хорошо, свяжемся чтобы обсудить вручение приза
Last edited by Zkir (2012-11-15 08:07:37)
Истинные слова не не приятны, приятные слова не истинны.
True words are unpleasant; pleasant words are untrue.
Offline
#222 2012-11-15 09:17:56
- dkiselev
- Member
- Registered: 2010-02-09
- Posts: 3,364
Re: Актуальные задачи, требующие искусства программирования
А где посмотреть то что надо на яву переписать?
А на деньги от приза
— Приобретайте одноразовые шприцы.
— На все суммы?
— На все. И отправляйте их в Одессу.
Last edited by dkiselev (2012-11-15 09:21:45)
mail: dkiselev@osm.me skype: dmitry.v.kiselev
Open Street Maps are supreme! Exterminate all map forms! Exterminate! Exterminate!
Offline
#223 2012-11-15 18:17:43
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Zkir wrote:
если РФ проходит по требуемой памяти
RU-OVRV.mp от 03.10.2012 => 420MB максимум (350MB сразу после загрузки, далее плавно растёт)
(Из файла грузится 1.6M точек по 120 байт и 1.5M отрезков по 9 байт + строка ~= 300MB)
Лады, буду выкладывать.
dkiselev wrote:
А где посмотреть то что надо на яву переписать?
Причешу, выложу на гитхабе - посмотрите.
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#224 2012-11-20 20:52:25
- OverQuantum
- Member
- From: Zelenograd
- Registered: 2009-06-17
- Posts: 1,582
- Website
Re: Актуальные задачи, требующие искусства программирования
Репозиторий: https://github.com/OverQuantum/mp_extsimp
Описание алгоритма на русском
Результат обработки RU-OVRV.mp выложенным кодом
Кто захочет переделать на Java - пишите. Предложение переназначить приз - в силе, на пару недель
Last edited by OverQuantum (2012-11-20 23:23:40)
Это же OpenStreetMap. Он больше внутри, чем снаружи.
Offline
#225 2012-11-21 13:42:05
- s777n
- Member
- Registered: 2012-03-04
- Posts: 318
Re: Актуальные задачи, требующие искусства программирования
Есть конвертер vb6-to-java. Но конвертер возьмет на себе только тривиальную работу. Результат придется редактировать.
Например так будет выглядеть основной класс
public class mp_extsimp1 {
//
// mp_extsimp
// Generalization of complex junctions and two ways roads
// from OpenStreetMap data
//
// Copyright © 2012 OverQuantum
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//
// Author contacts:
// http://overquantum.livejournal.com
// https://github.com/OverQuantum
//
// Project homepage:
// https://github.com/OverQuantum/mp_extsimp
//
//
// OpenStreetMap data licensed under the Open Data Commons Open Database License (ODbL).
// OpenStreetMap wiki licensed under the Creative Commons Attribution-ShareAlike 2.0 license (CC-BY-SA).
// Please refer to http://www.openstreetmap.org/copyright for details
//
// osm2mp licensed under GPL v2, please refer to http://code.google.com/p/osm2mp/
//
// mp file format (polish format) description from http://www.cgpsmapper.com/manual.htm
//
//
//
//
//history
//2012.10.08 - "challenge accepted", project started
//2012.10.10 - added combining of edges
//2012.10.11 - added checking of type and oneway on combining of edges
//2012.10.12 - added collapsing of junctions
//2012.10.15 - added comments to code, added handling of speedclass
//2012.10.16 - added distance in metres by WGS 84
//2012.10.16 - added joining directions (only duplicate edges and close edges forming V-form)
//2012.10.17 - chg CollapseJunctions now iterative
//2012.10.17 - added inserting near nodes to edges on joining direction (no moving of node)
//2012.10.18 - adding JoinDirections2, closest edge founds, GoByTwoWays started
//2012.10.18 - adding JoinDirections2, joining works, but some mess created...
//2012.10.21 - finished JoinDirections2, handling of circles and deleted void edges
//2012.10.22 - adding CollapseJunctions2, done main part, remain marking edges for cases of crossing if border-nodes >= 2 in the end
//2012.10.22 - adding CollapseJunctions2, marking edges for cases of crossing if border-nodes >= 2 in the end, marking long oneways before
//2012.10.23 - added limiting distance of ShrinkBorderNodes
//2012.10.23 - added check for forward/backward coverage at ends of chains in JoinDirections2
//2012.10.24 - added CheckShortLoop, does not help
//2012.10.29 - added CheckShortLoop, forward/backward coverage in JoinDirections2 for cycles
//2012.10.29 - added DouglasPeucker_total_split
//2012.10.30 - added check lens in CosAngleBetweenEdges, skipping of RouteParamExt, LoopLimit in CJ2
//2012.10.31 - fix forw/back check in JD2 (split to two cycles)
//2012.11.01 - added JoinAcute (from JD), ProjectNode, CompareRoadtype. Looks like RC1 of algo
//2012.11.01 - added Save_MP_2 (w/o rev-dir)
//2012.11.06 - added JD3 - with cluster search
//2012.11.07 - fix loop in D-P, optimized aiming and del in CJ2, added/modified status writing in form1.caption
//2012.11.09 - fix saving2 on oneway=2
//2012.11.12 - added keep of main road label
//2012.11.13 - added TWback/TWforw and checking them in JD3 (unfinished)
//2012.11.14 - added correct naming and speedclass in JD3
//RC3
//2012.11.14 - hardcoded limits moved to func/sub parameters
//2012.11.14 - unused functions commented
//2012.11.15 - root code moved to module, removed comdlg32.bas
//2012.11.19 - added keeping header of source file, removed writing "; roadtype="
//2012.11.15-20 - adding explaining comments, small fixes
//2012.11.20 - added license and references
//TODO:
//*? dump problems of OSM data (1: too long links, 2: ?)
//? 180/-180 safety
//Option Explicit
//Cluster size in degrees for ClusterIndex build and search
public static final int CLUSTER_SIZE = 0.05;
//Conversion degrees to radians and back
public static final int DEGTORAD = 1.74532925199433E-02;
public static final int RADTODEG = 57.2957795130823;
//WGS84 datum
public static final int DATUM_R_EQUAT = 6378137;
public static final int DATUM_R_POLAR = 6356752.3142;
//'for expanding bbox
public static final int DATUM_R_OVER = 6380000;
//OSM highway main types
public static final int HIGHWAY_MOTORWAY = 0;
public static final int HIGHWAY_MOTORWAY_LINK = 1;
public static final int HIGHWAY_TRUNK = 2;
public static final int HIGHWAY_TRUNK_LINK = 3;
public static final int HIGHWAY_PRIMARY = 4;
public static final int HIGHWAY_PRIMARY_LINK = 5;
public static final int HIGHWAY_SECONDARY = 6;
public static final int HIGHWAY_SECONDARY_LINK = 7;
public static final int HIGHWAY_TERTIARY = 8;
public static final int HIGHWAY_TERTIARY_LINK = 9;
//OSM highway minor types (should not occur)
public static final int HIGHWAY_LIVING_STREET = 10;
public static final int HIGHWAY_RESIDENTIAL = 12;
public static final int HIGHWAY_UNCLASSIFIED = 14;
public static final int HIGHWAY_SERVICE = 16;
public static final int HIGHWAY_TRACK = 18;
public static final int HIGHWAY_OTHER = 20;
public static final int HIGHWAY_UNKNOWN = 22;
public static final int HIGHWAY_UNSPECIFIED = 24;
//Masks
//'all links
public static final int HIGHWAY_MASK_LINK = 1;
//'get main type (removes _link)
public static final int HIGHWAY_MASK_MAIN = 254;
//Specific marking of edges/nodes for algorithms
public static final int MARK_JUNCTION = 1;
public static final int MARK_COLLAPSING = 2;
public static final int MARK_AIMING = 4;
public static final int MARK_DISTCHECK = 8;
public static final int MARK_SIDE1CHECK = 8;
public static final int MARK_SIDE2CHECK = 16;
public static final int MARK_SIDESCHECK = 24;
public static final int MARK_WAVEPASSED = 16;
public static final int MARK_NODE_BORDER = -2;
public static final int MARK_NODE_OF_JUNCTION = -3;
public static final int MARK_NODEID_DELETED = -2;
//OSM node - point on Earth with lat/lon coordinates
//*TODO:** type is translated as a new class at the end of the file Public Type node
//Edge - part of OSM way between two nodes
//*TODO:** type is translated as a new class at the end of the file Public Type edge
//Aiming edge - edge for calc centroid of junction
//*TODO:** type is translated as a new class at the end of the file Public Type aimedge
//bbox, lat/lon min/max rectangle (not 180/-180 safe)
//*TODO:** type is translated as a new class at the end of the file Public Type bbox
//Element of label statistics "histogramm"
//*TODO:** type is translated as a new class at the end of the file Public Type LabelStat
public static String MPheader = "";
//All nodes
public static node[] Nodes;
public static int NodesAlloc = 0;
public static int NodesNum = 0;
//All road edges
public static edge[] Edges;
public static int EdgesAlloc = 0;
public static int EdgesNum = 0;
//Aim edges
public static aimedge[] AimEdges;
public static int AimEdgesAlloc = 0;
public static int AimEdgesNum = 0;
//Array for building chain of indexes
public static int[] Chain = 0;
public static int ChainAlloc = 0;
public static int ChainNum = 0;
//'max found NodeID
public static int NodeIDMax = 0;
//'case of calc distance during last call of DistanceToSegment()
public static int DistanceToSegment_last_case = 0;
//'edge, on which GoByChain() function have just passed from node to node
public static int GoByChain_lastedge = 0;
//'histogramm of speed classes
public static int SpeedHistogram(10) = 0;
//Cluster index
//'min lat-border of clusters
public static double ClustersLat0 = 0;
//'min lon-border of clusters
public static double ClustersLon0 = 0;
//'index of first node of cluster (X*Y)
public static int[] ClustersFirst = 0;
//'chain of nodes (NodesNum)
public static int[] ClustersChain = 0;
//'num of cluster by lat = X
public static int ClustersLatNum = 0;
//'num of cluster by lon = Y
public static int ClustersLonNum = 0;
//'num of indexed nodes (for continuing BuildNodeClusterIndex)
public static int ClustersIndexedNodes = 0;
//'index of last node of cluster - for building index (X*Y)
public static int[] ClustersLast = 0;
//for continuing GetNodeInBboxByCluster
//'last bbox
public static bbox ClustersFindLastBbox;
//'last index of cluster
public static int ClustersFindLastCluster = 0;
//'
public static int ClustersFindLastNode = 0;
//Label statistics, for estimate labels of joined roads
public static LabelStat[] LabelStats;
public static int LabelStatsNum = 0;
public static int LabelStatsAlloc = 0;
//'speed of chain after last call of EstimateChain()
public static int EstimateChain_speed = 0;
//'label of chain after last call of EstimateChain()
public static String EstimateChain_label = "";
//Indexes of forward and backward ways during two ways joining
public static int[] TWforw = 0;
public static int[] TWback = 0;
public static int TWalloc = 0;
public static int TWforwNum = 0;
public static int TWbackNum = 0;
//Init - init all arrays
public static void init() {
NodesAlloc = 1000;
G.redim(Nodes, NodesAlloc);
NodesNum = 0;
EdgesAlloc = 1000;
G.redim(Edges, EdgesAlloc);
EdgesNum = 0;
ChainAlloc = 1000;
G.redim(Chain, ChainAlloc);
ChainNum = 0;
public class mp_extsimp1 {
//
// mp_extsimp
// Generalization of complex junctions and two ways roads
// from OpenStreetMap data
//
// Copyright © 2012 OverQuantum
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//
// Author contacts:
// http://overquantum.livejournal.com
// https://github.com/OverQuantum
//
// Project homepage:
// https://github.com/OverQuantum/mp_extsimp
//
//
// OpenStreetMap data licensed under the Open Data Commons Open Database License (ODbL).
// OpenStreetMap wiki licensed under the Creative Commons Attribution-ShareAlike 2.0 license (CC-BY-SA).
// Please refer to http://www.openstreetmap.org/copyright for details
//
// osm2mp licensed under GPL v2, please refer to http://code.google.com/p/osm2mp/
//
// mp file format (polish format) description from http://www.cgpsmapper.com/manual.htm
//
//
//
//
//history
//2012.10.08 - "challenge accepted", project started
//2012.10.10 - added combining of edges
//2012.10.11 - added checking of type and oneway on combining of edges
//2012.10.12 - added collapsing of junctions
//2012.10.15 - added comments to code, added handling of speedclass
//2012.10.16 - added distance in metres by WGS 84
//2012.10.16 - added joining directions (only duplicate edges and close edges forming V-form)
//2012.10.17 - chg CollapseJunctions now iterative
//2012.10.17 - added inserting near nodes to edges on joining direction (no moving of node)
//2012.10.18 - adding JoinDirections2, closest edge founds, GoByTwoWays started
//2012.10.18 - adding JoinDirections2, joining works, but some mess created...
//2012.10.21 - finished JoinDirections2, handling of circles and deleted void edges
//2012.10.22 - adding CollapseJunctions2, done main part, remain marking edges for cases of crossing if border-nodes >= 2 in the end
//2012.10.22 - adding CollapseJunctions2, marking edges for cases of crossing if border-nodes >= 2 in the end, marking long oneways before
//2012.10.23 - added limiting distance of ShrinkBorderNodes
//2012.10.23 - added check for forward/backward coverage at ends of chains in JoinDirections2
//2012.10.24 - added CheckShortLoop, does not help
//2012.10.29 - added CheckShortLoop, forward/backward coverage in JoinDirections2 for cycles
//2012.10.29 - added DouglasPeucker_total_split
//2012.10.30 - added check lens in CosAngleBetweenEdges, skipping of RouteParamExt, LoopLimit in CJ2
//2012.10.31 - fix forw/back check in JD2 (split to two cycles)
//2012.11.01 - added JoinAcute (from JD), ProjectNode, CompareRoadtype. Looks like RC1 of algo
//2012.11.01 - added Save_MP_2 (w/o rev-dir)
//2012.11.06 - added JD3 - with cluster search
//2012.11.07 - fix loop in D-P, optimized aiming and del in CJ2, added/modified status writing in form1.caption
//2012.11.09 - fix saving2 on oneway=2
//2012.11.12 - added keep of main road label
//2012.11.13 - added TWback/TWforw and checking them in JD3 (unfinished)
//2012.11.14 - added correct naming and speedclass in JD3
//RC3
//2012.11.14 - hardcoded limits moved to func/sub parameters
//2012.11.14 - unused functions commented
//2012.11.15 - root code moved to module, removed comdlg32.bas
//2012.11.19 - added keeping header of source file, removed writing "; roadtype="
//2012.11.15-20 - adding explaining comments, small fixes
//2012.11.20 - added license and references
//TODO:
//*? dump problems of OSM data (1: too long links, 2: ?)
//? 180/-180 safety
//Option Explicit
//Cluster size in degrees for ClusterIndex build and search
public static final int CLUSTER_SIZE = 0.05;
//Conversion degrees to radians and back
public static final int DEGTORAD = 1.74532925199433E-02;
public static final int RADTODEG = 57.2957795130823;
//WGS84 datum
public static final int DATUM_R_EQUAT = 6378137;
public static final int DATUM_R_POLAR = 6356752.3142;
//'for expanding bbox
public static final int DATUM_R_OVER = 6380000;
//OSM highway main types
public static final int HIGHWAY_MOTORWAY = 0;
public static final int HIGHWAY_MOTORWAY_LINK = 1;
public static final int HIGHWAY_TRUNK = 2;
public static final int HIGHWAY_TRUNK_LINK = 3;
public static final int HIGHWAY_PRIMARY = 4;
public static final int HIGHWAY_PRIMARY_LINK = 5;
public static final int HIGHWAY_SECONDARY = 6;
public static final int HIGHWAY_SECONDARY_LINK = 7;
public static final int HIGHWAY_TERTIARY = 8;
public static final int HIGHWAY_TERTIARY_LINK = 9;
//OSM highway minor types (should not occur)
public static final int HIGHWAY_LIVING_STREET = 10;
public static final int HIGHWAY_RESIDENTIAL = 12;
public static final int HIGHWAY_UNCLASSIFIED = 14;
public static final int HIGHWAY_SERVICE = 16;
public static final int HIGHWAY_TRACK = 18;
public static final int HIGHWAY_OTHER = 20;
public static final int HIGHWAY_UNKNOWN = 22;
public static final int HIGHWAY_UNSPECIFIED = 24;
//Masks
//'all links
public static final int HIGHWAY_MASK_LINK = 1;
//'get main type (removes _link)
public static final int HIGHWAY_MASK_MAIN = 254;
//Specific marking of edges/nodes for algorithms
public static final int MARK_JUNCTION = 1;
public static final int MARK_COLLAPSING = 2;
public static final int MARK_AIMING = 4;
public static final int MARK_DISTCHECK = 8;
public static final int MARK_SIDE1CHECK = 8;
public static final int MARK_SIDE2CHECK = 16;
public static final int MARK_SIDESCHECK = 24;
public static final int MARK_WAVEPASSED = 16;
public static final int MARK_NODE_BORDER = -2;
public static final int MARK_NODE_OF_JUNCTION = -3;
public static final int MARK_NODEID_DELETED = -2;
//OSM node - point on Earth with lat/lon coordinates
//*TODO:** type is translated as a new class at the end of the file Public Type node
//Edge - part of OSM way between two nodes
//*TODO:** type is translated as a new class at the end of the file Public Type edge
//Aiming edge - edge for calc centroid of junction
//*TODO:** type is translated as a new class at the end of the file Public Type aimedge
//bbox, lat/lon min/max rectangle (not 180/-180 safe)
//*TODO:** type is translated as a new class at the end of the file Public Type bbox
//Element of label statistics "histogramm"
//*TODO:** type is translated as a new class at the end of the file Public Type LabelStat
public static String MPheader = "";
//All nodes
public static node[] Nodes;
public static int NodesAlloc = 0;
public static int NodesNum = 0;
//All road edges
public static edge[] Edges;
public static int EdgesAlloc = 0;
public static int EdgesNum = 0;
//Aim edges
public static aimedge[] AimEdges;
public static int AimEdgesAlloc = 0;
public static int AimEdgesNum = 0;
//Array for building chain of indexes
public static int[] Chain = 0;
public static int ChainAlloc = 0;
public static int ChainNum = 0;
//'max found NodeID
public static int NodeIDMax = 0;
//'case of calc distance during last call of DistanceToSegment()
public static int DistanceToSegment_last_case = 0;
//'edge, on which GoByChain() function have just passed from node to node
public static int GoByChain_lastedge = 0;
//'histogramm of speed classes
public static int SpeedHistogram(10) = 0;
//Cluster index
//'min lat-border of clusters
public static double ClustersLat0 = 0;
//'min lon-border of clusters
public static double ClustersLon0 = 0;
//'index of first node of cluster (X*Y)
public static int[] ClustersFirst = 0;
//'chain of nodes (NodesNum)
public static int[] ClustersChain = 0;
//'num of cluster by lat = X
public static int ClustersLatNum = 0;
//'num of cluster by lon = Y
public static int ClustersLonNum = 0;
//'num of indexed nodes (for continuing BuildNodeClusterIndex)
public static int ClustersIndexedNodes = 0;
//'index of last node of cluster - for building index (X*Y)
public static int[] ClustersLast = 0;
//for continuing GetNodeInBboxByCluster
//'last bbox
public static bbox ClustersFindLastBbox;
//'last index of cluster
public static int ClustersFindLastCluster = 0;
//'
public static int ClustersFindLastNode = 0;
//Label statistics, for estimate labels of joined roads
public static LabelStat[] LabelStats;
public static int LabelStatsNum = 0;
public static int LabelStatsAlloc = 0;
AimEdgesAlloc = 50;
G.redim(AimEdges, AimEdgesAlloc);
AimEdgesNum = 0;
LabelStatsAlloc = 30;
G.redim(LabelStats, LabelStatsAlloc);
LabelStatsNum = 0;
TWalloc = 100;
G.redim(TWforw, TWalloc);
G.redim(TWback, TWalloc);
TWbackNum = 0;
TWforwNum = 0;
}
//Add one node to dynamic array
//Assumed, Nodes(NodesNum) filled with required data prior to call
public static void addNode() {
if (NodesNum >= NodesAlloc) {
//realloc if needed
NodesAlloc = NodesAlloc * 2;
G.redimPreserve(Nodes, NodesAlloc);
}
NodesNum = NodesNum + 1;
}
//Add one edge to dynamic array
//Assumed, Edges(EdgesNum) filled with required data prior to call
public static void addEdge() {
if (EdgesNum >= EdgesAlloc) {
//realloc if needed
EdgesAlloc = EdgesAlloc * 2;
G.redimPreserve(Edges, EdgesAlloc);
}
EdgesNum = EdgesNum + 1;
}
//Add one AimEdge to dynamic array
//Assumed, AimEdges(AimEdgesNum) filled with required data prior to call
public static void addAimEdge() {
if (AimEdgesNum >= AimEdgesAlloc) {
//realloc if needed
AimEdgesAlloc = AimEdgesAlloc * 2;
G.redimPreserve(AimEdges, AimEdgesAlloc);
}
AimEdgesNum = AimEdgesNum + 1;
}
//Add one index into chain
public static void addChain(int i) {
if (ChainNum >= ChainAlloc) {
//realloc if needed
ChainAlloc = ChainAlloc * 2;
G.redimPreserve(Chain, ChainAlloc);
}
Chain[ChainNum] = i;
ChainNum = ChainNum + 1;
}
//Join two nodes by new edge
//node1 - start node, 'node2 - end node
//return: index of new edge
public static int joinByEdge(int node1, int node2) {
int _rtn = 0;
int k = 0;
Edges[EdgesNum].node1 = node1;
Edges[EdgesNum].node2 = node2;
//add edge to both nodes
k = Nodes[node1].Edges;
Nodes[node1]..edge(k) = EdgesNum;
Nodes[node1].Edges = Nodes[node1].Edges + 1;
k = Nodes[node2].Edges;
Nodes[node2]..edge(k) = EdgesNum;
Nodes[node2].Edges = Nodes[node2].Edges + 1;
_rtn = EdgesNum;
addEdge();
return _rtn;
}
//Merge loaded nodes from diffrent ways by NodeID
public static void joinNodesByID() {
Long, i = null; j As Long
int k = 0;
int mapNum = 0;
int[] iDmap() = null;
int[] nodeMap() = null;
//if NodeID indexes are too big, we could not use direct mapping
//max number for direct mapping should be selected with respect to available RAM
//'need more than 40M
if (NodeIDMax > 10000000# Then GoTo lHardWay) {
//SOFT WAY, via direct map from NodeID (~ O(n) )
//'IDmap(NodeID) = index in Nodes array
G.redim(iDmap, NodeIDMax);
for (i = 0; i <= NodeIDMax; i++) {
iDmap[i] = -1;
}
for (i = 0; i <= NodesNum - 1; i++) {
k = Nodes[i]..nodeID;
//'without NodeID - not mergable
if (k < 0) { //*TODO:** goto found: GoTo lSkip; }
if (iDmap[k] < 0) {
//'first occurence of NodeID
iDmap[k] = i;
}
else {
//'should join
mergeNodes(iDmap[k], i);
}
//*TODO:** label found: lSkip:;
if ((i && 8191) == 0) {
//display progress
Form1.Caption = "Join soft " + CStr(i) + " / " + CStr(NodesNum): Form1.Refresh;
}
}
//*TODO:** goto found: GoTo lExit;
//*TODO:** label found: lHardWay:;
//HARD WAY, via bubble search (~ O(n^2))
//' IDmap(a) = NodeID
G.redim(iDmap, NodesNum);
//' NodeMap(a) = index of node in Nodes() array
G.redim(nodeMap, NodesNum);
mapNum = 0;
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..nodeID >= 0) {
for (j = 0; j <= i - 1; j++) {
if (iDmap[j] == Nodes[i]..nodeID) {
//found - not first occurence - should join
mergeNodes(nodeMap[j], i);
//*TODO:** goto found: GoTo lFound;
}
}
//not found - first occurence of NodeID
nodeMap[mapNum] = i;
iDmap[mapNum] = Nodes[i]..nodeID;
mapNum = mapNum + 1;
}
//*TODO:** label found: lFound:;
if ((i && 8191) == 0) {
//display progress
Form1.Caption = "Join hard " + CStr(i) + " / " + CStr(NodesNum): Form1.Refresh;
}
}
//*TODO:** label found: lExit:;
}
//Merge node2 to node1 with relink of all edges
//flag: 1 - ignore node2 coords (0 - move node1 to average coordinates)
public static void mergeNodes(int node1, int node2, int flag) {
Long, k = null; i As Long, j As Long
int p = 0;
//relink edges from node2 to node1
p = Nodes[node1].Edges;
k = Nodes[node2].Edges;
for (i = 0; i <= k - 1; i++) {
j = Nodes[node2]..edge(i);
if (Edges[j].node1 == node2) {
//edge goes from node2 to X
Edges[j].node1 = node1;
}
if (Edges[j].node2 == node2) {
//edge goes from X to node2
Edges[j].node2 = node1;
}
Nodes[node1]..edge(p) = j;
p = p + 1;
}
Nodes[node1].Edges = p;
Nodes[node2].Edges = 0;
//kill all void edges right now
i = 0;
while (i < Nodes[node1].Edges) {
j = Nodes[node1]..edge(i);
if (Edges[j].node1 == Edges[j].node2) { delEdge(j); }
i = i + 1;
}
if ((flag && 1) == 0) {
//Calc average coordinates
//TODO: fix (not safe to 180/-180 edge)
Nodes[node1]..lat = 0.5 * (Nodes[node1]..lat + Nodes[node2]..lat);
Nodes[node1]..lon = 0.5 * (Nodes[node1]..lon + Nodes[node2]..lon);
}
delNode(node2);
}
//Delete edge and remove all references to it from both nodes
public static void delEdge(int edge1) {
int i = 0;
int k = 0;
//find this edge among edges of node1
i = Edges[edge1]..node1;
//'edge already deleted
if (i == -1) { return; }
for (k = 0; k <= Nodes[i].Edges - 1; k++) {
if (Nodes[i]..edge(k) == edge1) {
//remove edge from edges of node1
Nodes[i]..edge(k) = Nodes[i]..edge(Nodes[i].Edges - 1);
Nodes[i].Edges = Nodes[i].Edges - 1;
//*TODO:** goto found: GoTo lFound1;
}
}
//*TODO:** label found: lFound1:;
//find this edge among edges of node2
i = Edges[edge1]..node2;
for (k = 0; k <= Nodes[i].Edges - 1; k++) {
if (Nodes[i]..edge(k) == edge1) {
//remove edge from edges of node2
Nodes[i]..edge(k) = Nodes[i]..edge(Nodes[i].Edges - 1);
Nodes[i].Edges = Nodes[i].Edges - 1;
//*TODO:** goto found: GoTo lFound2;
}
}
//*TODO:** label found: lFound2:;
//'mark node as deleted
Edges[edge1]..node1 = -1;
}
//Delete node with all connected edges
public static void delNode(int node1) {
while (Nodes[node1].Edges > 0) {
delEdge(Nodes[node1]..edge(0));
}
Nodes[node1].Edges = 0;
//'mark node as deleted
Nodes[node1]..nodeID = MARK_NODEID_DELETED;
}
//Save geometry to simple .mp file (without joining of chains)
public static void save_MP(String filename) {
int i = 0;
Long, k1 = null; k2 As Long
int typ = 0;
Open(filename For Output As #2);
Print #2, "; Generated by mp_extsimp";
Print #2, "";
//Print #2, MPheader
//custom header
Print #2, "[IMG ID]";
Print #2, "CodePage=1251";
Print #2, "LblCoding=9";
Print #2, "ID=88888888";
Print #2, "Name=OSM";
Print #2, "TypeSet=Navitel";
Print #2, "Elevation=M";
Print #2, "Preprocess=F";
Print #2, "TreSize=3000";
Print #2, "TreMargin=0.00000";
Print #2, "RgnLimit=127";
Print #2, "POIIndex=Y";
Print #2, "POINumberFirst=N";
Print #2, "MG=Y";
Print #2, "Routing=Y";
Print #2, "Copyright=OpenStreetMap";
Print #2, "Levels=6";
//'for high precision of coordinates
Print #2, "Level0=26";
Print #2, "Level1=22";
Print #2, "Level2=20";
Print #2, "Level3=18";
Print #2, "Level4=16";
Print #2, "Level5=15";
Print #2, "Zoom0=0";
Print #2, "Zoom1=1";
Print #2, "Zoom2=2";
Print #2, "Zoom3=3";
Print #2, "Zoom4=4";
Print #2, "Zoom5=5";
Print #2, "[END-IMG ID]";
for (i = 0; i <= EdgesNum - 1; i++) {
k1 = Edges[i]..node1;
k2 = Edges[i]..node2;
if (k1 < 0) { //*TODO:** goto found: GoTo lSkip; }
Print #2, "; roadtype=" + CStr(Edges(i).roadtype) + " edge=" + CStr(i) + " mark=" + CStr(Edges(i).mark);
Print #2, "[POLYLINE]";
typ = getType_by_Highway(Edges[i]..roadtype);
Print #2, "Type=0x"; Hex(typ);
if (Edges[i]..label.length() > 0) {
Print #2, "Label=~[0x05]" + Edges(i).label;
Print #2, "StreetDesc=~[0x05]" + Edges(i).label;
}
if (Edges[i]..oneway > 0) { Print #2, "DirIndicator=1"; }
Print #2, "EndLevel=" + CStr(GetTopLevel_by_Highway(Edges(i).roadtype));
Print #2, "RouteParam=";
Print #2, CStr(Edges(i).speed); ",";
Print #2, CStr(GetClass_by_Highway(Edges(i).roadtype)); ",";
Print #2, CStr(Edges(i).oneway); ",";
Print #2, "0,0,0,0,0,0,0,0,0";
Print #2, "Data0=("; CStr(Nodes(k1).lat); ","; CStr(Nodes(k1).lon); "),(";
Print #2, CStr(Nodes(k2).lat); ","; CStr(Nodes(k2).lon); ")";
Print #2, "Nod1=0,"; CStr(k1); ",0";
Print #2, "Nod2=1,"; CStr(k2); ",0";
Print #2, "[END]";
Print #2, "";
if ((i && 8191) == 0) {
//display progress
Form1.Caption = "Save " + CStr(i) + " / " + CStr(EdgesNum): Form1.Refresh;
}
//*TODO:** label found: lSkip:;
}
Close(#2);
}
//Save geometry to .mp file with joining chains into polylines
public static void save_MP_2(String filename) {
int i = 0;
Long, k1 = null; k2 As Long
int typ = 0;
Open(filename For Output As #2);
Print #2, "; Generated by mp_extsimp";
Print #2, "";
Print #2, MPheader;
for (i = 0; i <= EdgesNum - 1; i++) {
if (Edges[i]..node1 == -1) {
//deleted edge
//'mark to ignore
Edges[i]..mark = 1;
}
else {
//'mark to save
Edges[i]..mark = 0;
}
}
for (i = 0; i <= EdgesNum - 1; i++) {
if (Edges[i]..mark == 0) {
//all marked to save - find chain and save
saveChain(i);
}
if ((i && 8191) == 0) {
//display progress
Form1.Caption = "Save2 " + CStr(i) + " / " + CStr(EdgesNum): Form1.Refresh;
}
}
//'file finalization flag
Print #2, "; Completed";
Close(#2);
}
//Find and optimize all chains by Douglas-Peucker with Epsilon (in metres)
public static void douglasPeucker_total(double epsilon) {
int i = 0;
int j = 0;
for (i = 0; i <= NodesNum - 1; i++) {
//'mark all nodes as not passed
Nodes[i]..mark = 0;
}
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..nodeID == MARK_NODEID_DELETED || Nodes[i].Edges != 2 || Nodes[i]..mark == 1) { //*TODO:** goto found: GoTo lSkip; }
//node: not deleted, not yet passed and with 2 edges -> should be checked for chain
douglasPeucker_chain(i, epsilon);
//*TODO:** label found: lSkip:;
if ((i && 8191) == 0) {
//show progress
Form1.Caption = "Doug-Pek " + CStr(i) + " / " + CStr(NodesNum): Form1.Refresh;
}
}
}
//find and optimize all chains by Douglas-Peucker with Epsilon (in metres) and limiting max edge (in metres)
public static void douglasPeucker_total_split(double epsilon, double maxEdge) {
int i = 0;
int j = 0;
for (i = 0; i <= NodesNum - 1; i++) {
//'mark all nodes as not passed
Nodes[i]..mark = 0;
}
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..nodeID == MARK_NODEID_DELETED || Nodes[i].Edges != 2 || Nodes[i]..mark == 1) { //*TODO:** goto found: GoTo lSkip; }
//node: not deleted, not yet passed and with 2 edges -> should be checked for chain
douglasPeucker_chain_split(i, epsilon, maxEdge);
//*TODO:** label found: lSkip:;
if ((i && 8191) == 0) {
//show progress
Form1.Caption = "Doug-Pek sp " + CStr(i) + " / " + CStr(NodesNum): Form1.Refresh;
}
}
}
//Find one chain (starting from node1) and optimize it by Douglas-Peucker with Epsilon (in metres)
public static void douglasPeucker_chain(int node1, double epsilon) {
int i = 0;
int j = 0;
Long, k = null; m As Long
edge refedge = null;
int chainEnd = 0;
int nextChainEdge = 0;
nextChainEdge = -1;
chainEnd = 0;
//Algorithm go from specified node into one direction by chain of nodes
//(nodes connected one by one, without junctions) until end (or junction) is reached
//After that algorithm will go from final edge into opposite direction and will compare edges
//and add nodes into Chain array
//On findind different edge (or reaching other end of chain) algorithm will pass found (sub)chain
//into OptimizeByDouglasPeucker_One recursive function for optimization
//Then rest of chain (if it exits) will be processed in similar way
//1) go by chain to the one end - to node with !=2 edges
//'start node
i = node1;
j = node1;
//*TODO:** label found: lGoNext:;
//'go by chain
k = goByChain(i, j);
//'if still 2 edges - proceed
if (k != node1 && Nodes[k].Edges == 2) { j = i: i == k: GoTo lGoNext; }
// *-----*-----*-----*---...
// k i j
//'OK, we found end of chain
j = k;
// *---------*-----*-----*---...
// k=j i
//2) go revert - from found end to another one and saving all nodes into Chain() array
ChainNum = 0;
addChain(k);
addChain(i);
//keep info about first edge in chain
refedge = Edges[GoByChain_lastedge];
//'reversed oneway
if (refedge.node1 != Chain[0] && refedge..oneway == 1) { refedge..oneway = 2; }
//*TODO:** label found: lGoNext2:;
k = goByChain(i, j);
// *-------------*-----*-----*---...
// j i k
//check oneway
m = Edges[GoByChain_lastedge]..oneway;
if (m > 0 && Edges[GoByChain_lastedge].node1 != i) { m = 2; }
//if oneway flag is differnt or road type is changed - break chain
if (m != refedge..oneway) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
if (Edges[GoByChain_lastedge]..roadtype != refedge..roadtype) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
addChain(k);
if (k != Chain[0] && Nodes[k].Edges == 2) {
//still 2 edges - still chain
Nodes[k]..mark = 1;
j = i;
i = k;
//*TODO:** goto found: GoTo lGoNext2;
}
chainEnd = 1;
//*TODO:** label found: lBreak:;
//3) optimize found chain by D-P
optimizeByDouglasPeucker_One(0, ChainNum - 1, epsilon, refedge);
if (chainEnd == 0) {
//continue with this chain, as it is not ended
// *================*--------------------*-----------*-----*---...
// NextChainEdge
//new reference info
refedge = Edges[nextChainEdge];
if (refedge.node1 == Chain[ChainNum - 1]) {
i = refedge..node2;
j = refedge.node1;
}
else {
if (refedge..oneway == 1) { refedge..oneway = 2; }
i = refedge.node1;
j = refedge..node2;
}
// *================*--------------------*-----------*-----*---...
// j i
//'chain from one edge - nothing to optimize by D-P
if (Nodes[i].Edges != 2) { return; }
//add both nodes of last edge
ChainNum = 0;
addChain(j);
addChain(i);
nextChainEdge = -1;
//'continue with chain
//*TODO:** goto found: GoTo lGoNext2;
}
}
//find one chain (starting from node1) and optimize it by Douglas-Peucker with Epsilon (in metres) and limiting edge len by MaxEdge
public static void douglasPeucker_chain_split(int node1, double epsilon, double maxEdge) {
int i = 0;
int j = 0;
Long, k = null; m As Long
edge refedge = null;
int chainEnd = 0;
int nextChainEdge = 0;
nextChainEdge = -1;
chainEnd = 0;
//Algorithm works as DouglasPeucker_chain above
//difference is only inside OptimizeByDouglasPeucker_One_split
//1) go by chain to the one end - to node with !=2 edges
//'start node
i = node1;
j = node1;
//*TODO:** label found: lGoNext:;
//'go by chain
k = goByChain(i, j);
//'if still 2 edges - proceed
if (k != node1 && Nodes[k].Edges == 2) { j = i: i == k: GoTo lGoNext; }
// *-----*-----*-----*---...
// k i j
//'OK, we found end of chain
j = k;
// *---------*-----*-----*---...
// k=j i
//2) go revert - from found end to another one and saving all nodes into Chain() array
ChainNum = 0;
addChain(k);
addChain(i);
//keep info about first edge in chain
refedge = Edges[GoByChain_lastedge];
//'reversed oneway
if (refedge.node1 != Chain[0] && refedge..oneway == 1) { refedge..oneway = 2; }
//*TODO:** label found: lGoNext2:;
k = goByChain(i, j);
// *-------------*-----*-----*---...
// j i k
//check oneway
m = Edges[GoByChain_lastedge]..oneway;
if (m > 0 && Edges[GoByChain_lastedge].node1 != i) { m = 2; }
//if oneway flag is differnt or road type is changed - break chain
if (m != refedge..oneway) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
if (Edges[GoByChain_lastedge]..roadtype != refedge..roadtype) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
addChain(k);
if (k != Chain[0] && Nodes[k].Edges == 2) {
//still 2 edges - still chain
Nodes[k]..mark = 1;
j = i;
i = k;
//*TODO:** goto found: GoTo lGoNext2;
}
chainEnd = 1;
//*TODO:** label found: lBreak:;
//3) optimize found chain by D-P
optimizeByDouglasPeucker_One_split(0, ChainNum - 1, epsilon, refedge, maxEdge);
if (chainEnd == 0) {
//continue with this chain, as it is not ended
// *================*--------------------*-----------*-----*---...
// NextChainEdge
//new reference info
refedge = Edges[nextChainEdge];
if (refedge.node1 == Chain[ChainNum - 1]) {
i = refedge..node2;
j = refedge.node1;
}
else {
if (refedge..oneway == 1) { refedge..oneway = 2; }
i = refedge.node1;
j = refedge..node2;
}
// *================*--------------------*-----------*-----*---...
// j i
//'chain from one edge - nothing to optimize by D-P
if (Nodes[i].Edges != 2) { return; }
//add both nodes of last edge
ChainNum = 0;
addChain(j);
addChain(i);
nextChainEdge = -1;
//'continue with chain
//*TODO:** goto found: GoTo lGoNext2;
}
}
//Save chain of edges into mp file (already opened as #2)
public static void saveChain(int edge1) {
int i = 0;
int j = 0;
Long, k = null; m As Long
edge refedge = null;
int chainEnd = 0;
int nextChainEdge = 0;
Long, k1 = null; k2 As Long
int typ = 0;
nextChainEdge = -1;
chainEnd = 0;
//Algorithm go from specified edge into one direction by chain of nodes
//(nodes connected one by one, without junctions) until end (or junction) is reached
//After that algorithm will go from final edge into opposite direction and will compare edges
//and add nodes into Chain array
//On findind different edge (or reaching other end of chain) algorithm will save found (sub)chain into mp file
//Then rest of chain (if it exits) will be processed in similar way
//1) go by chain to the one end - to node with !=2 edges
//'start node
i = Edges[edge1]..node1;
j = Edges[edge1]..node2;
if (Nodes[i].Edges != 2) {
//i is end of chain
ChainNum = 0;
addChain(i);
addChain(j);
refedge = Edges[edge1];
//'saved
Edges[edge1]..mark = 1;
if (Nodes[j].Edges != 2) {
//that's all
chainEnd = 1;
//*TODO:** goto found: GoTo lBreak;
}
else {
j = Chain[0];
i = Chain[1];
//*TODO:** goto found: GoTo lGoNext2;
}
}
//*TODO:** label found: lGoNext:;
//'go by chain
k = goByChain(i, j);
//'if still 2 edges - proceed
if (Nodes[k].Edges == 2) { j = i: i == k: GoTo lGoNext; }
// *-----*-----*-----*---...
// k i j
//'OK, we found end of chain
j = k;
// *---------*-----*-----*---...
// k=j i
//2) go revert - from found end to another one and saving all nodes into Chain() array
ChainNum = 0;
addChain(k);
addChain(i);
//keep info about first edge in chain
refedge = Edges[GoByChain_lastedge];
Edges[GoByChain_lastedge]..mark = 1;
//'reversed oneway
if (refedge..node1 != Chain[0] && refedge..oneway == 1) { refedge..oneway = 2; }
//*TODO:** label found: lGoNext2:;
k = goByChain(i, j);
// *-------------*-----*-----*---...
// j i k
//check oneway
m = Edges[GoByChain_lastedge]..oneway;
if (m > 0 && Edges[GoByChain_lastedge]..node1 != i) { m = 2; }
//if oneway flag is differnt or road type, speed or label is changed - break chain
if (m != refedge..oneway) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
if (Edges[GoByChain_lastedge]..roadtype != refedge..roadtype) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
if (Edges[GoByChain_lastedge]..speed != refedge..speed) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
if (!(Edges[GoByChain_lastedge]..label.equals(refedge..label))) { nextChainEdge = GoByChain_lastedge: GoTo lBreak; }
//'saved
Edges[GoByChain_lastedge]..mark = 1;
addChain(k);
if (Nodes[k].Edges == 2) {
//still 2 edges - still chain
j = i;
i = k;
//*TODO:** goto found: GoTo lGoNext2;
}
chainEnd = 1;
//*TODO:** label found: lBreak:;
//3) save chain to file
//Print #2, "; roadtype=" + CStr(refedge.roadtype) 'debug info about road type
Print #2, "[POLYLINE]";
//'object type - from road type
typ = getType_by_Highway(refedge..roadtype);
Print #2, "Type=0x"; Hex(typ);
if (refedge..label.length() > 0) {
//labels - into special codes fro labelization
Print #2, "Label=~[0x05]" + refedge.label;
Print #2, "StreetDesc=~[0x05]" + refedge.label;
}
//'oneway indicator
if (refedge..oneway > 0) { Print #2, "DirIndicator=1"; }
//'top level of visibility - from road type
Print #2, "EndLevel=" + CStr(GetTopLevel_by_Highway(refedge.roadtype));
Print #2, "RouteParam=";
//'speed class
Print #2, CStr(refedge.speed); ",";
//'road class - from road type
Print #2, CStr(GetClass_by_Highway(refedge.roadtype)); ",";
if (refedge..oneway > 0) {
//'one_way
Print #2, "1,";
}
else {
Print #2, "0,";
}
//'other params are not handled
Print #2, "0,0,0,0,0,0,0,0,0";
Print #2, "Data0=";
if (refedge..oneway == 2) {
//reverted oneway, save in backward sequence
for (i = ChainNum - 1; i <= 0; i--) {
if (i != ChainNum - 1) { Print #2, ","; }
Print #2, "("; CStr(Nodes(Chain(i)).lat); ","; CStr(Nodes(Chain(i)).lon); ")";
}
Print #2,;
Print #2, "Nod1=0,"; CStr(Chain(ChainNum - 1)); ",0";
Print #2, "Nod2=" + CStr(ChainNum - 1) + ","; CStr(Chain(0)); ",0";
}
else {
//forward oneway or twoway, save in direct sequence
for (i = 0; i <= ChainNum - 1; i++) {
if (i != 0) { Print #2, ","; }
Print #2, "("; CStr(Nodes(Chain(i)).lat); ","; CStr(Nodes(Chain(i)).lon); ")";
}
Print #2,;
Print #2, "Nod1=0,"; CStr(Chain(0)); ",0";
Print #2, "Nod2=" + CStr(ChainNum - 1) + ","; CStr(Chain(ChainNum - 1)); ",0";
}
Print #2, "[END]";
Print #2, "";
if (chainEnd == 0) {
//continue with this chain, as it is not ended
// *================*--------------------*-----------*-----*---...
// NextChainEdge
//new reference info
refedge = Edges[nextChainEdge];
if (refedge..node1 == Chain[ChainNum - 1]) {
i = refedge..node2;
j = refedge..node1;
}
else {
if (refedge..oneway == 1) { refedge..oneway = 2; }
i = refedge..node1;
j = refedge..node2;
}
// *================*--------------------*-----------*-----*---...
// j i
Edges[nextChainEdge]..mark = 1;
//add both nodes of last edge
ChainNum = 0;
addChain(j);
addChain(i);
if (Nodes[i].Edges != 2) {
//chain from one edge
chainEnd = 1;
//*TODO:** goto found: GoTo lBreak;
}
nextChainEdge = -1;
//'continue with chain
//*TODO:** goto found: GoTo lGoNext2;
}
}
//Go by chain from node1 in some direction, but not to Node0
//(assumed, that node1 have two edges, not 1, not 3 or more, otherwise - UB)
//Usage: GoByChain(x,x) goes by first edge, z=GoByChain(x,y)->u=GoByChain(z,x)->... allows to travel by chain node by node
public static int goByChain(int node1, int node0) {
Long, i = null; k As Long
//check first edge
i = Nodes[node1]..edge(0);
k = Edges[i].node1;
if (k == node1) { k = Edges[i]..node2; }
GoByChain_lastedge = i;
if (k == node0) {
//node0 -> check second edge
i = Nodes[node1]..edge(1);
k = Edges[i].node1;
if (k == node1) { k = Edges[i]..node2; }
GoByChain_lastedge = i;
}
return k;
}
//Get edge, conecting node1 and node2, return -1 if no connection
//TODO(opt): swap node1 and node2 if node2 have smaller edges
public static int getEdgeBetween(int node1, int node2) {
int _rtn = 0;
Long, i = null; j As Long
for (i = 0; i <= Nodes[node1].Edges - 1; i++) {
j = Nodes[node1]..edge(i);
if (Edges[j].node1 == node2 || Edges[j].node2 == node2) {
//found
_rtn = j;
return _rtn;
}
}
_rtn = -1;
return _rtn;
}
//Parse OSM highway class to our own constants
public static int getHighwayType(String text) {
int _rtn = 0;
switch (Trim(text).toLowerCase()) {
case "primary":
_rtn = HIGHWAY_PRIMARY;
break;
case "primary_link":
_rtn = HIGHWAY_PRIMARY_LINK;
break;
case "secondary":
_rtn = HIGHWAY_SECONDARY;
break;
case "secondary_link":
_rtn = HIGHWAY_SECONDARY_LINK;
break;
case "tertiary":
_rtn = HIGHWAY_TERTIARY;
break;
case "tertiary_link":
_rtn = HIGHWAY_TERTIARY_LINK;
break;
case "motorway":
_rtn = HIGHWAY_MOTORWAY;
break;
case "motorway_link":
_rtn = HIGHWAY_MOTORWAY_LINK;
break;
case "trunk":
_rtn = HIGHWAY_TRUNK;
break;
case "trunk_link":
_rtn = HIGHWAY_TRUNK_LINK;
break;
case "living_street":
_rtn = HIGHWAY_LIVING_STREET;
break;
case "residential":
_rtn = HIGHWAY_RESIDENTIAL;
break;
case "unclassified":
_rtn = HIGHWAY_UNCLASSIFIED;
break;
case "service":
_rtn = HIGHWAY_SERVICE;
break;
case "track":
_rtn = HIGHWAY_TRACK;
break;
case "road":
_rtn = HIGHWAY_UNKNOWN;
break;
case Else:
_rtn = HIGHWAY_OTHER;
break;
}
return _rtn;
}
//Convert constants to polyline type
public static int getType_by_Highway(int highwayType) {
int _rtn = 0;
switch (highwayType) {
case HIGHWAY_MOTORWAY:
_rtn = 1;
break;
case HIGHWAY_MOTORWAY_LINK:
_rtn = 9;
break;
case HIGHWAY_TRUNK:
_rtn = 1;
break;
case HIGHWAY_TRUNK_LINK:
_rtn = 9;
break;
case HIGHWAY_PRIMARY:
_rtn = 2;
break;
case HIGHWAY_PRIMARY_LINK:
_rtn = 8;
break;
case HIGHWAY_SECONDARY:
_rtn = 3;
break;
case HIGHWAY_SECONDARY_LINK:
_rtn = 8;
break;
case HIGHWAY_TERTIARY:
_rtn = 3;
break;
case HIGHWAY_TERTIARY_LINK:
_rtn = 8;
break;
case HIGHWAY_LIVING_STREET:
_rtn = 6;
break;
case HIGHWAY_RESIDENTIAL:
_rtn = 6;
break;
case HIGHWAY_UNCLASSIFIED:
_rtn = 3;
break;
case HIGHWAY_SERVICE:
_rtn = 7;
break;
case HIGHWAY_TRACK:
_rtn = 10;
break;
case HIGHWAY_UNKNOWN:
_rtn = 3;
break;
case HIGHWAY_OTHER:
_rtn = 3;
break;
case Else:
_rtn = 3;
break;
}
return _rtn;
}
//Convert constants to road class
public static int getClass_by_Highway(int highwayType) {
int _rtn = 0;
switch (highwayType) {
case HIGHWAY_MOTORWAY:
_rtn = 4;
break;
case HIGHWAY_MOTORWAY_LINK:
_rtn = 4;
break;
case HIGHWAY_TRUNK:
_rtn = 4;
break;
case HIGHWAY_TRUNK_LINK:
_rtn = 4;
break;
case HIGHWAY_PRIMARY:
_rtn = 3;
break;
case HIGHWAY_PRIMARY_LINK:
_rtn = 3;
break;
case HIGHWAY_SECONDARY:
_rtn = 2;
break;
case HIGHWAY_SECONDARY_LINK:
_rtn = 2;
break;
case HIGHWAY_TERTIARY:
_rtn = 1;
break;
case HIGHWAY_TERTIARY_LINK:
_rtn = 1;
break;
case HIGHWAY_LIVING_STREET:
_rtn = 0;
break;
case HIGHWAY_RESIDENTIAL:
_rtn = 0;
break;
case HIGHWAY_UNCLASSIFIED:
_rtn = 1;
break;
case HIGHWAY_SERVICE:
_rtn = 0;
break;
case HIGHWAY_TRACK:
_rtn = 0;
break;
case HIGHWAY_UNKNOWN:
_rtn = 0;
break;
case HIGHWAY_OTHER:
_rtn = 0;
break;
case Else:
_rtn = 0;
break;
}
return _rtn;
}
//Convert constants to top level for visibility
public static int getTopLevel_by_Highway(int highwayType) {
int _rtn = 0;
switch (highwayType) {
case HIGHWAY_MOTORWAY:
_rtn = 6;
break;
case HIGHWAY_MOTORWAY_LINK:
_rtn = 2;
break;
case HIGHWAY_TRUNK:
_rtn = 6;
break;
case HIGHWAY_TRUNK_LINK:
_rtn = 2;
break;
case HIGHWAY_PRIMARY:
_rtn = 5;
break;
case HIGHWAY_PRIMARY_LINK:
_rtn = 2;
break;
case HIGHWAY_SECONDARY:
_rtn = 4;
break;
case HIGHWAY_SECONDARY_LINK:
_rtn = 2;
break;
case HIGHWAY_TERTIARY:
_rtn = 3;
break;
case HIGHWAY_TERTIARY_LINK:
_rtn = 2;
break;
case HIGHWAY_LIVING_STREET:
_rtn = 2;
break;
case HIGHWAY_RESIDENTIAL:
_rtn = 2;
break;
case HIGHWAY_UNCLASSIFIED:
_rtn = 2;
break;
case HIGHWAY_SERVICE:
_rtn = 2;
break;
case HIGHWAY_TRACK:
_rtn = 2;
break;
case HIGHWAY_UNKNOWN:
_rtn = 2;
break;
case HIGHWAY_OTHER:
_rtn = 2;
break;
case Else:
_rtn = 2;
break;
}
return _rtn;
}
//Move node 3 to closest point on line node1-node2
//TODO: fix (not safe to 180/-180 edge)
public static void projectNode(int node1, int node2, node node3) { // TODO: Use of ByRef founded
double k = 0;
double xab = 0;
double yab = 0;
xab = Nodes[node2]..lat - Nodes[node1]..lat;
yab = Nodes[node2]..lon - Nodes[node1]..lon;
k = (xab * (node3..lat - Nodes[node1]..lat) + yab * (node3..lon - Nodes[node1]..lon)) / (xab * xab + yab * yab);
node3..lat = Nodes[node1]..lat + k * xab;
node3..lon = Nodes[node1]..lon + k * yab;
}
//Calc cosine of angle betweeen two edges
//(calc via vectors on reference ellipsoid, 180/-180 safe)
public static double cosAngleBetweenEdges(int edge1, int edge2) {
double _rtn = 0;
Double, x1 = null; y1 As Double, z1 As Double
Double, x2 = null; y2 As Double, z2 As Double
Double, x3 = null; y3 As Double, z3 As Double
Double, x4 = null; y4 As Double, z4 As Double
Long, node1 = null; node2 As Long
Double, len1 = null; len2 As Double
//XYZ
node1 = Edges[edge1].node1;
.node2 = Edges[edge1]..node2;
latLonToXYZ(Nodes[node1]..lat, Nodes[node1]..lon, x1, y1, z1);
latLonToXYZ(Nodes[.node2]..lat, Nodes[.node2]..lon, x2, y2, z2);
node1 = Edges[edge2].node1;
.node2 = Edges[edge2]..node2;
latLonToXYZ(Nodes[node1]..lat, Nodes[node1]..lon, x3, y3, z3);
latLonToXYZ(Nodes[.node2]..lat, Nodes[.node2]..lon, x4, y4, z4);
//vectors
x2 = x2 - x1;
y2 = y2 - y1;
z2 = z2 - z1;
x4 = x4 - x3;
y4 = y4 - y3;
z4 = z4 - z3;
//vector lengths
len1 = Sqr(x2 * x2 + y2 * y2 + z2 * z2);
len2 = Sqr(x4 * x4 + y4 * y4 + z4 * z4);
if (len1 == 0 || len2 == 0) {
//one of vectors is void
_rtn = 0;
}
else {
//Cosine of angle is scalar multiply divided by lengths
_rtn = (x2 * x4 + y2 * y4 + z2 * z4) / (len1 * len2);
}
return _rtn;
}
//Convert (lat,lon) to (x,y,z) on reference ellipsoid
public static Object latLonToXYZ(double lat, double lon, double x, double y, double z) { // TODO: Use of ByRef founded
double r = 0;
r = DATUM_R_EQUAT * Cos(lat * DEGTORAD);
z = DATUM_R_POLAR * Sin(lat * DEGTORAD);
x = r * Sin(lon * DEGTORAD);
y = r * Cos(lon * DEGTORAD);
}
//Calc distance square from node1 to node2 in metres
//metric distance of ellipsoid chord (not arc)
public static double distanceSquare(int node1, int node2) {
Double, x1 = null; y1 As Double, z1 As Double
Double, x2 = null; y2 As Double, z2 As Double
latLonToXYZ(Nodes[node1]..lat, Nodes[node1]..lon, x1, y1, z1);
latLonToXYZ(Nodes[node2]..lat, Nodes[node2]..lon, x2, y2, z2);
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2);
}
//Calc distance from node1 to node2 in metres
public static double distance(int node1, int node2) {
return Sqr(distanceSquare(node1, node2));
}
//Calc distance from node3 to interval (not just line) from node1 to node2 in metres
//Calc by Heron's formula from sides of triangle (180/-180 safe)
public static double distanceToSegment(int node1, int node2, int node3) {
double _rtn = 0;
double a = 0;
double b = 0;
double c = 0;
double s2 = 0;
//'Calc squares of triangle sides
a = distanceSquare(node1, node2);
b = distanceSquare(node1, node3);
c = distanceSquare(node2, node3);
if (a == 0) {
_rtn = Sqr(b);
//'node1=node2
DistanceToSegment_last_case = 0;
return _rtn;
}
else if (b > (a + c)) {
_rtn = Sqr(c);
//'node1 is closest point to node3
DistanceToSegment_last_case = 1;
return _rtn;
}
else if (c > (a + b)) {
_rtn = Sqr(b);
//'node2 is closest point to node3
DistanceToSegment_last_case = 2;
return _rtn;
}
else {
//'Calc sides lengths from squares
a = Sqr(a);
b = Sqr(b);
c = Sqr(c);
s2 = 0.5 * Sqr((a + b + c) * (a + b - c) * (a + c - b) * (b + c - a));
_rtn = s2 / a;
//'closest point is inside interval
DistanceToSegment_last_case = 3;
}
return _rtn;
}
//Calc distance between not crossing edges (edge1 and edge2)
//(180/-180 safe)
public static double distanceBetweenSegments(int edge1, int edge2) {
Double, d1 = null; d2 As Double
//Just minimum of 4 distances (each ends to each other edge)
d1 = distanceToSegment(Edges[edge1]..node1, Edges[edge1]..node2, Edges[edge2]..node1);
d2 = distanceToSegment(Edges[edge1]..node1, Edges[edge1]..node2, Edges[edge2]..node2);
if (d2 < d1) { d1 = d2; }
d2 = distanceToSegment(Edges[edge2]..node1, Edges[edge2]..node2, Edges[edge1]..node1);
if (d2 < d1) { d1 = d2; }
d2 = distanceToSegment(Edges[edge2]..node1, Edges[edge2]..node2, Edges[edge1]..node2);
if (d2 < d1) { d1 = d2; }
return d1;
}
//Recursive check to optimize chain/subchain by Douglas-Peucker with Epsilon (in metres)
//subchain is defined by IndexStart,IndexLast
//refedge - road parameters of chain (for create new edge in case of optimization)
//(180/-180 safe)
private static void optimizeByDouglasPeucker_One(int indexStart, int indexLast, double epsilon, edge refedge) {
int i = 0;
int farestIndex = 0;
double farestDist = 0;
double dist = 0;
double k = 0;
double scalarMult = 0;
int newspeed = 0;
String newlabel = "";
//'one edge (or less) -> nothing to do
if (((indexStart + 1) >= indexLast)) { return; }
//'distance between subchain edge
k = distance(Chain[indexStart], Chain[indexLast]);
//find node, farest from line first-last node (farer than Epsilon)
//'start max len - Epsilon
farestDist = epsilon;
//'nothing yet found
farestIndex = -1;
for (i = indexStart + 1; i <= indexLast - 1; i++) {
if (k == 0) {
//circled subchain
dist = distance(Chain[i], Chain[indexStart]);
}
else {
dist = distanceToSegment(Chain[indexStart], Chain[indexLast], Chain[i]);
}
if (dist > farestDist) {
farestDist = Dist: farestIndex == i;
}
}
if (farestIndex == -1) {
//farest node not found -> all distances less than Epsilon -> remove all internal nodes
//calc speed and label from all subchain edges
estimateChain(indexStart, indexLast);
newspeed = EstimateChain_speed;
newlabel = EstimateChain_label;
for (i = indexStart + 1; i <= indexLast - 1; i++) {
//'kill all nodes with edges
delNode(Chain[i]);
}
//join first and last nodes by new edge
if (refedge..oneway == 2) {
//reversed oneway
i = joinByEdge(Chain[indexLast], Chain[indexStart]);
Edges[i]..oneway = 1;
}
else {
i = joinByEdge(Chain[indexStart], Chain[indexLast]);
Edges[i]..oneway = refedge..oneway;
}
Edges[i]..roadtype = refedge..roadtype;
Edges[i]..speed = newspeed;
Edges[i]..label = newlabel;
return;
}
//farest point found - keep it
//call Douglas-Peucker for two new subchains
optimizeByDouglasPeucker_One(indexStart, farestIndex, epsilon, refedge);
optimizeByDouglasPeucker_One(farestIndex, indexLast, epsilon, refedge);
}
//Recursive check to optimize chain/subchain by Douglas-Peucker with Epsilon (in metres) and limiting edge len by MaxEdge
//subchain is defined by IndexStart,IndexLast
//refedge - road parameters of chain (for create new edge in case of optimization)
//(180/-180 safe)
private static void optimizeByDouglasPeucker_One_split(int indexStart, int indexLast, double epsilon, edge refedge, double maxEdge) {
int i = 0;
int farestIndex = 0;
double farestDist = 0;
double dist = 0;
double k = 0;
double scalarMult = 0;
int newspeed = 0;
String newlabel = "";
//'one edge (or less) -> nothing to do
if (((indexStart + 1) >= indexLast)) { return; }
//'distance between subchain edge
k = distance(Chain[indexStart], Chain[indexLast]);
//find node, farest from line first-last node (farer than Epsilon)
//'start max len - Epsilon
farestDist = epsilon;
//'nothing yet found
farestIndex = -1;
for (i = indexStart + 1; i <= indexLast - 1; i++) {
if (k == 0) {
//circled subchain
dist = distance(Chain[i], Chain[indexStart]);
}
else {
dist = distanceToSegment(Chain[indexStart], Chain[indexLast], Chain[i]);
}
if (dist > farestDist) {
farestDist = Dist: farestIndex == i;
}
if (distance(Chain[i], Chain[indexStart]) > maxEdge) {
//distance from start to this node is more than limit -> we should keep this node
farestIndex = i;
//*TODO:** goto found: GoTo lKeepFar;
}
}
if (farestIndex == -1) {
//farest node not found -> all distances less than Epsilon -> remove all internal nodes
//calc speed and label from all subchain edges
estimateChain(indexStart, indexLast);
newspeed = EstimateChain_speed;
newlabel = EstimateChain_label;
for (i = indexStart + 1; i <= indexLast - 1; i++) {
//'kill with edges
delNode(Chain[i]);
}
//join first and last nodes by new edge
if (refedge..oneway == 2) {
//reversed oneway
i = joinByEdge(Chain[indexLast], Chain[indexStart]);
Edges[i]..oneway = 1;
}
else {
i = joinByEdge(Chain[indexStart], Chain[indexLast]);
Edges[i]..oneway = refedge..oneway;
}
Edges[i]..roadtype = refedge..roadtype;
Edges[i]..speed = newspeed;
Edges[i]..label = newlabel;
return;
}
//*TODO:** label found: lKeepFar:;
//farest point found - keep it
//call Douglas-Peucker for two new subchains
//'Douglas-Peucker for two new subchains
optimizeByDouglasPeucker_One_split(indexStart, farestIndex, epsilon, refedge, maxEdge);
optimizeByDouglasPeucker_One_split(farestIndex, indexLast, epsilon, refedge, maxEdge);
}
//Load .mp file
//(loader is basic and rather stupid, uses relocation on file to read section info without internal buffering)
public static void load_MP(String filename) {
int logOptimization = 0;
String sLine = "";
double fLat = 0;
double fLon = 0;
String sWay = "";
//'0 - none, 1 - header, 2 - polyline, 3 - polygon
int sectionType = 0;
//'Phase of reading polyline: 0 - general part, 1 - scan for routeparam, 2 - scan for geometry, 3 - scan for routing (nodeid e.t.c)
int iPhase = 0;
int iStartLine = 0;
int iPrevLine = 0;
int fileLen = 0;
String sPrefix = "";
int dataLineNum = 0;
Long, k = null; k2 As Long, k3 As Long, p As Long
Long, i = null; j As Long
int thisLineNodes = 0;
int nodeID = 0;
int wayClass = 0;
int waySpeed = 0;
int wayOneway = 0;
String[] routep() = null;
int lastCommentHighway = 0;
String label = "";
//'no nodeid yet
NodeIDMax = -1;
Open(filename For Input As #1);
fileLen = LOF(1);
sectionType = 0;
wayClass = -1;
waySpeed = -1;
iPhase = 0;
label = "";
iStartLine = 0;
iPrevLine = 0;
MPheader = "";
lastCommentHighway = HIGHWAY_UNSPECIFIED;
//*TODO:** label found: lNextLine:;
//'get current position in file
iPrevLine = Seek(1);
Line(Input #1, sLine);
//check for section start
if (sLine.indexOf("[IMG ID]", 1) > 0) {
//header section
sectionType = 1;
iPhase = 0;
}
if (sLine.indexOf("[POLYGON]", 1) > 0) {
//polygon
sectionType = 3;
//*TODO:** goto found: GoTo lStartPoly;
}
if (sLine.indexOf("[POLYLINE]", 1) > 0) {
//polyline
sectionType = 2;
//*TODO:** label found: lStartPoly:;
if ((iPrevLine && 1023) == 0) {
//display progress
Form1.Caption = "Load: " + CStr(iPrevLine) + " / " + CStr(fileLen): Form1.Refresh;
}
dataLineNum = 0;
if (iPhase == 0) {
//first pass of section? start scanning
wayClass = -1;
waySpeed = -1;
iPhase = 1;
//'remember current pos (where to go after ending pass)
iStartLine = iPrevLine;
}
}
if (sLine.indexOf("[END", 1) > 0) {
//section ended
if (sectionType == 1) {
//'add ending of section into saved header
MPheader = MPheader + sLine + vbNewLine;
}
//'no routing params found in 1st pass - skip way completely
if (iPhase == 1 && (waySpeed == -1)) { iPhase = 0; }
if (iPhase > 0 && iPhase < 3) {
//not last pass of section -> goto start of it
//'relocate in file
Seek(1, iStartLine);
iPhase = iPhase + 1;
//*TODO:** goto found: GoTo lNextLine;
}
//'if no osm2mp info yet found
lastCommentHighway = HIGHWAY_UNSPECIFIED;
label = "";
iPhase = 0;
sectionType = 0;
}
switch (iPhase) {
case 0:
if (Trim(sLine).substring(0, 9).equals("; highway")) {
//comment, produced by osm2mp
lastCommentHighway = getHighwayType(Trim(sLine.substring(12, sLine.length())));
}
if (sectionType == 1) {
//line of header section
MPheader = MPheader + sLine + vbNewLine;
}
//'scan for routing param
break;
case 1:
if (Trim(sLine).substring(0, 10).equals("RouteParam")) {
//'skip ext
if (Trim(sLine).substring(0, 13).equals("RouteParamExt")) { //*TODO:** goto found: GoTo lNoData; }
k2 = sLine.indexOf("=", 1) + 1;
//'split by "," delimiter
routep = Split(sLine.substring(k2, sLine.length() - k2), ",");
//'direct copy of speed
waySpeed = Val(routep[0]);
//'and oneway
wayOneway = Val(routep[2]);
if (lastCommentHighway == HIGHWAY_UNSPECIFIED) {
//'default class
wayClass = 3;
//TODO: should be detected by Type and WayClass
}
else {
//get class from osm2mp comment
wayClass = lastCommentHighway;
}
}
if (Trim(sLine).substring(0, 5).equals("Label")) {
//label
k2 = sLine.indexOf("=", 1);
label = Trim(sLine.substring(k2 + 1, sLine.length() - k2));
if (label.substring(0, 4).equals("~[0x")) {
//use only special codes
k2 = label.indexOf("]", 1);
label = Trim(label.substring(k2 + 1, label.length() - k2));
}
else {
//ignore others
label = "";
}
}
break;
case 3:
//scan for node routing info:
if (Trim(sLine).substring(0, 3).equals("Nod")) {
//Nod
k2 = sLine.indexOf("=", 1);
if (k2 <= 0) { //*TODO:** goto found: GoTo lSkipRoadNode; }
k = Val(sLine.substring(k2 + 1, 20));
if (k > NodesAlloc) {
//error: too big node index: " + sLine
//*TODO:** goto found: GoTo lSkipRoadNode;
}
k3 = sLine.indexOf(",", k2);
if (k3 < 0) {
//error: bad NodeID
//*TODO:** goto found: GoTo lSkipRoadNode;
}
nodeID = Val(sLine.substring(k3 + 1, 20));
//'update max NodeID
if (nodeID > NodeIDMax) { NodeIDMax = nodeID; }
//'store nodeid
Nodes[NodesNum - thisLineNodes + k].nodeID == nodeID;
//*TODO:** label found: lSkipRoadNode:;
}
break;
case 2:
if (Trim(sLine).substring(0, 4).equals("Data")) {
//geometry
k = sLine.indexOf("Data", 1);
if (k <= 0) { //*TODO:** goto found: GoTo lNoData; }
sWay = "";
//'"Data" + next char + "="
sPrefix = sLine.substring(0, k + 4) + "=";
dataLineNum = dataLineNum + 1;
thisLineNodes = 0;
//*TODO:** label found: lNextPoint:;
//get lat-lon coords from line
k2 = k.toLowerCase().indexOf(sLine.toLowerCase());
if (k2 <= 0) { //*TODO:** goto found: GoTo lEndData; }
fLat = Val(sLine.substring(k2 + 1, 20));
k3 = sLine.indexOf(",", k2);
if (k3 <= 0) { //*TODO:** goto found: GoTo lEndData; }
fLon = Val(sLine.substring(k3 + 1, 20));
//fill node info
Nodes[NodesNum]..lat = fLat;
Nodes[NodesNum]..lon = fLon;
Nodes[NodesNum].Edges = 0;
Nodes[NodesNum].nodeID = -1;
if (thisLineNodes > 0) {
//not the first node of way -> create edge
j = joinByEdge(NodesNum - 1, NodesNum);
//'oneway edges is always -> by geometry
Edges[j]..oneway = wayOneway;
Edges[j]..roadtype = wayClass;
Edges[j].label = label;
if (waySpeed >= 0) {
Edges[j]..speed = waySpeed;
}
else {
//were not specified
//'56km/h
Edges[j]..speed = 3;
}
}
thisLineNodes = thisLineNodes + 1;
//'finish node creation
addNode();
k = k3;
//*TODO:** goto found: GoTo lNextPoint;
//*TODO:** label found: lEndData:;
p = 0;
//*TODO:** label found: lNoData:;
}
break;
}
if (!EOF(1)) { //*TODO:** goto found: GoTo lNextLine; }
Close(#1);
}
//Check that index is already present in Chain() array
public static int isInChain(int node1) {
int i = 0;
for (i = 0; i <= ChainNum - 1; i++) {
if (Chain[i] == node1) { return 0; }
}
return 0;
}
//Find index of node1 in Chain() array, return -1 if not present
public static int findInChain(int node1) {
int i = 0;
for (i = 0; i <= ChainNum - 1; i++) {
if (Chain[i] == node1) { return 0; }
}
return -1;
}
//Check all edges of node for junction marker and add them into collapsing constuction
public static void checkForCollapeByChain2(int node1) {
int j = 0;
int edge = 0;
int borderNode = 0;
borderNode = 0;
for (j = 0; j <= Nodes[node1].Edges - 1; j++) {
edge = Nodes[node1].edge(j);
if ((Edges[edge]..mark && MARK_JUNCTION) > 0) {
//edge is marked as junction
//'mark it as collapsing
Edges[edge]..mark = Edges[edge]..mark || MARK_COLLAPSING;
//add other end of edge into collapsing constuction
if (isInChain(Edges[edge].node1) == 0) {
//node1 is not in chain
addChain(Edges[edge].node1);
}
if (isInChain(Edges[edge]..node2) == 0) {
//node2 is not in chain
addChain(Edges[edge]..node2);
}
//*TODO:** goto found: GoTo lNext;
}
//at lease one non-junction edge found
borderNode = 1;
//*TODO:** label found: lNext:;
}
//'node is border-node
if (borderNode == 1) { Nodes[node1]..mark = MARK_NODE_BORDER; }
}
//Check all edges of node for collapsing marker and add their other ends into chain
public static void groupCollapse(int node1) {
int j = 0;
int edge = 0;
int k = 0;
for (j = 0; j <= Nodes[node1].Edges - 1; j++) {
edge = Nodes[node1].edge(j);
if ((Edges[edge]..mark && MARK_COLLAPSING) > 0) {
k = Edges[edge].node1;
//'get other end of edge
if (k == node1) { k = Edges[edge]..node2; }
//if other end is marked as node-of-junction -> add it to current chain
if (Nodes[k]..mark == MARK_NODE_OF_JUNCTION && isInChain(k) == 0) { addChain(k); }
}
}
}
//Collapse all junctions to nodes
//junctions detected as clouds of _links and short loops
//SlideMaxDist - max distance allowed to slide by border-nodes
//LoopLimit - max loop considered as junction
//AngleLimit - min angle between aiming edges to use precise calc of centroid
public static void collapseJunctions2(double slideMaxDist, double loopLimit, double angleLimit) {
Long, i = null; j As Long, k As Long, mode1 As Long
Long, m = null; e As Long
int joinGroups = 0;
//'controids
int[] joinedNode() = null;
int joiningNodes = 0;
int passNumber = 0;
int borderNodes = 0;
bbox[] joinGroupBox() = null;
passNumber = 1;
//Algorithm marks _link edges as junctions
//then all edges checked for participating of short loops, if short loop found all its edges also marked as junctions
//then all junction edges tries to collapse with keeping connection points (border nodes) on other road
//border nodes can slide on other edges while construction of junction edges tries to shrink like stretched rubber
//siding also marks passed edges as part of collapsing junctions
//final constructions from collapsing edges is separated from each other
//then centroids of this constructions found, it is done by finding point which minimizes sum of squares
//of distances to aiming lines, aiming lines is build from all edges connecting to collapsing junction and
//all not _link edges of this junctions
//then all collapsing edges deleted, all nodes - joined into centroid
//then algorithm reiterates from start till no junction were found
//*TODO:** label found: lIteration:;
//mark all as not-yet-joining
for (i = 0; i <= NodesNum - 1; i++) {
//'no wave
Nodes[i]..mark = 0;
//'no wave
Nodes[i]..temp_dist = 0;
}
//1) Mark all potential parts of junctions
for (i = 0; i <= EdgesNum - 1; i++) {
//'not checked
Edges[i]..mark = 0;
if (Edges[i]..node1 > -1) {
if ((Edges[i]..roadtype && HIGHWAY_MASK_LINK) != 0) {
//all links are parts of junctions
Edges[i]..mark = MARK_JUNCTION;
}
}
}
for (i = 0; i <= EdgesNum - 1; i++) {
if (Edges[i]..node1 > -1) {
//check all edges (not links) for short loops
//all short loops also marked as part of junctions
if ((Edges[i]..roadtype && HIGHWAY_MASK_LINK) == 0 && (Edges[i]..mark && MARK_JUNCTION) == 0) {
//not _link, not yet marked junction
//'not marked distcheck -> should check it
if ((Edges[i]..mark && MARK_DISTCHECK) == 0) { checkShortLoop2(i, loopLimit); }
}
}
if ((i && 65535) == 0) {
//display progress
Form1.Caption = "Collapse " + CStr(passNumber) + ", Shorts " + CStr(i) + " / " + CStr(EdgesNum): Form1.Refresh;
}
}
for (i = 0; i <= NodesNum - 1; i++) {
//'not in join group
Nodes[i]..mark = -1;
}
//2) mark edges by trying to shrink junction
joinGroups = 0;
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..nodeID != MARK_NODEID_DELETED && Nodes[i]..mark == -1) {
//not deleted node, not marked yet -> should check
//start new group
ChainNum = 0;
borderNodes = 0;
//'add this node to a chain
addChain(i);
//'check all edges of node for collapsing
checkForCollapeByChain2(Chain[0]);
//'node is border-node
if (Nodes[Chain[0]]..mark == MARK_NODE_BORDER) { borderNodes = 1; }
j = 1;
if (ChainNum > 1) {
//at least 2 nodes found to collapse
//*TODO:** label found: lRecheckAgain:;
//continue to check all edges of added nodes by chain
while (j < ChainNum) {
checkForCollapeByChain2(Chain[j]);
if (Nodes[Chain[j]]..mark == MARK_NODE_BORDER) {
//border-node found - move it to start of chain (by swap)
k = Chain[borderNodes];
Chain[borderNodes] = Chain[j];
Chain[j] = k;
borderNodes = borderNodes + 1;
}
j = j + 1;
}
if (borderNodes > 1) {
//if border-nodes found - shrink whole construction by sliding border-nodes by geometry
shrinkBorderNodes(borderNodes, slideMaxDist);
borderNodes = 0;
//*TODO:** goto found: GoTo lRecheckAgain;
}
//mark all found nodes
for (j = 0; j <= ChainNum - 1; j++) {
Nodes[Chain[j]]..mark = MARK_NODE_OF_JUNCTION;
}
}
}
if ((i && 8191) == 0) {
//show progress
Form1.Caption = "Collapse " + CStr(passNumber) + ", Shrink " + CStr(i) + " / " + CStr(NodesNum): Form1.Refresh;
}
}
//3) group edges to separate junctions
joinGroups = 0;
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..mark == MARK_NODE_OF_JUNCTION) {
ChainNum = 0;
//'add this node to a chain
addChain(i);
j = 0;
while (j < ChainNum) {
//'check all edges and add their other ends if they are collapsing
groupCollapse(Chain[j]);
j = j + 1;
}
if (ChainNum > 1) {
//2 or more found - new group
for (j = 0; j <= ChainNum - 1; j++) {
Nodes[Chain[j]]..mark = joinGroups;
}
joinGroups = joinGroups + 1;
}
}
}
//4) calculate coordinates of centroid for collapsed junction
G.redim(joinedNode, joinGroups);
G.redim(joinGroupBox, joinGroups);
//Create nodes for all found join-groups
for (i = 0; i <= joinGroups; i++) {
joinedNode[i] = NodesNum;
Nodes[NodesNum]..mark = -1;
Nodes[NodesNum].Edges = 0;
//'fake coords, so cluster-index algo will not get (0,0) coords
Nodes[NodesNum]..lat = Nodes[0]..lat;
Nodes[NodesNum]..lon = Nodes[0]..lon;
addNode();
joinGroupBox[i]..lat_max = -360;
joinGroupBox[i]..lat_min = 360;
joinGroupBox[i]..lon_max = -360;
joinGroupBox[i]..lon_min = 360;
}
//calc bboxes for all join groups
for (j = 0; j <= NodesNum - 1; j++) {
if (Nodes[j]..mark >= 0) {
i = Nodes[j]..mark;
//update bbox for group
if (Nodes[j]..lat < joinGroupBox[i]..lat_min) { joinGroupBox[i]..lat_min = Nodes[j]..lat; }
if (Nodes[j]..lat > joinGroupBox[i]..lat_max) { joinGroupBox[i]..lat_max = Nodes[j]..lat; }
if (Nodes[j]..lon < joinGroupBox[i]..lon_min) { joinGroupBox[i]..lon_min = Nodes[j]..lon; }
if (Nodes[j]..lon > joinGroupBox[i]..lon_max) { joinGroupBox[i]..lon_max = Nodes[j]..lon; }
}
}
//'rebuild cluster-index from zero
buildNodeClusterIndex(0);
for (i = 0; i <= joinGroups - 1; i++) {
joiningNodes = 0;
AimEdgesNum = 0;
//'first
mode1 = 0;
//*TODO:** label found: lNextNode:;
//get node from bbox by cluster-index
//without cluster-index search have complexety ~O(n^2)
j = getNodeInBboxByCluster(joinGroupBox[i], mode1);
//'"next" next time
mode1 = 1;
if (j != -1) {
if (Nodes[j]..mark == i) {
//this joining group
joiningNodes = joiningNodes + 1;
for (m = 0; m <= Nodes[j].Edges - 1; m++) {
e = Nodes[j]..edge(m);
//'skip already marked as aiming
if ((Edges[e]..mark && MARK_AIMING) > 0) { //*TODO:** goto found: GoTo lSkipEdge; }
//'skip all collapsing junctions
if ((Edges[e]..mark && MARK_COLLAPSING) > 0 && (Edges[e]..mark && MARK_JUNCTION) > 0) { //*TODO:** goto found: GoTo lSkipEdge; }
//remain: all edges which will survive from all nodes of this join group
//plus all collapsing edges of main roads (this needed for removing noise of last edges near junctions)
if (Edges[e]..node1 == j) {
//'lat1-lon1 is always a node which will collapse (and so points to junction)
AimEdges[AimEdgesNum]..lat1 = Nodes[j]..lat;
AimEdges[AimEdgesNum]..lon1 = Nodes[j]..lon;
AimEdges[AimEdgesNum]..lat2 = Nodes[Edges[e]..node2]..lat;
AimEdges[AimEdgesNum]..lon2 = Nodes[Edges[e]..node2]..lon;
}
else {
AimEdges[AimEdgesNum]..lat1 = Nodes[j]..lat;
AimEdges[AimEdgesNum]..lon1 = Nodes[j]..lon;
AimEdges[AimEdgesNum]..lat2 = Nodes[Edges[e]..node1]..lat;
AimEdges[AimEdgesNum]..lon2 = Nodes[Edges[e]..node1]..lon;
}
if ((Edges[Nodes[j]..edge(m)]..mark && MARK_COLLAPSING) > 0) {
//mark as aiming, for skip it next time
Edges[e]..mark = Edges[e]..mark || MARK_AIMING;
}
addAimEdge();
//*TODO:** label found: lSkipEdge:;
}
}
//*TODO:** goto found: GoTo lNextNode;
}
if (joiningNodes > 0) {
if ((joiningNodes && 127) == 0) {
//display progress
Form1.Caption = "Collapse " + CStr(passNumber) + ", Aim " + CStr(i) + " / " + CStr(joinGroups): Form1.Refresh;
}
//'find centroid of junction
findAiming(Nodes[joinedNode[i]], angleLimit);
}
}
//5) delete all collapsing edges
for (i = 0; i <= EdgesNum - 1; i++) {
if ((Edges[i]..mark && MARK_COLLAPSING) > 0) {
delEdge(i);
}
}
//6) Ñollapse nodes to junctions single nodes
for (j = 0; j <= NodesNum - 1; j++) {
if (Nodes[j]..mark >= 0) {
i = Nodes[j]..mark;
for (m = 0; m <= Nodes[j].Edges - 1; m++) {
//reconnect edge to centroid
if (Edges[Nodes[j]..edge(m)]..node1 == j) {
Edges[Nodes[j]..edge(m)]..node1 = joinedNode[i];
}
else {
Edges[Nodes[j]..edge(m)]..node2 = joinedNode[i];
}
k = Nodes[joinedNode[i]].Edges;
Nodes[joinedNode[i]]..edge(k) = Nodes[j]..edge(m);
Nodes[joinedNode[i]].Edges = k + 1;
}
//'all edges were reconnected
Nodes[j].Edges = 0;
//'kill
delNode(j);
}
if ((j && 8191) == 0) {
Form1.Caption = "Collapse " + CStr(passNumber) + ", Del " + CStr(j) + " / " + CStr(NodesNum): Form1.Refresh;
}
}
if (joinGroups > 0) {
//unless no junction detected - relaunch algo
passNumber = passNumber + 1;
DoEvents;
//*TODO:** goto found: GoTo lIteration;
}
}
//Shrink group of border-nodes to minimum-distance (point or segment or more complex)
//BorderNum - numbed of border nodes (must be in the start of Chain array)
//shrink is achived by moving border-nodes along geometry while minimizing sum length
//all edges, passed by border-node marked as part of junctions
//MaxShift limit max length allowed to pass by each border-node
//if two border-nodes reach each other, they joins
//if reaching 1 border-node is not possible, then near edges are checked for internal-points minimizing sum len
//this edges also marked as part of junctions (requires than all edges were not very long)
public static void shrinkBorderNodes(int borderNum, double maxShift) {
//'current node index of border-node
int[] borderNodes() = null;
//'distance, covered by border-node while moving on edges
double[] borderShifts() = null;
Long, i = null; j As Long, k As Long
Long, e = null; p As Long
int moving = 0;
int moved = 0;
Double, dist = null; dist0 As Double
double dist1 = 0;
Double, dist_min = null; node_dist_min As Long, edge_dist_min As Long
//'indexes of border-nodes
G.redim(borderNodes, borderNum);
//'len, passed by border-nodes
G.redim(borderShifts, borderNum);
//get border nodes
for (i = 0; i <= borderNum - 1; i++) {
borderNodes[i] = Chain[i];
//'zero len passed
borderShifts[i] = 0;
}
//*TODO:** label found: lRestartCycle:;
moving = 0;
moved = 0;
while (moving < borderNum) {
//*TODO:** label found: lRestartMoving:;
//calc current sum of distances from Moving border-node to all others
dist0 = 0;
for (j = 0; j <= borderNum - 1; j++) {
if (j != moving) {
dist1 = distance(borderNodes[moving], borderNodes[j]);
dist0 = dist0 + dist1;
}
}
//finding node, where this border-node can move to minimize distance
//'need sum-distance less than current
dist_min = dist0;
//'not yet found
node_dist_min = -1: edge_dist_min == -1;
for (k = 0; k <= Nodes[borderNodes[moving]].Edges - 1; k++) {
e = Nodes[borderNodes[moving]]..edge(k);
if ((Edges[e]..mark && MARK_JUNCTION) == 0) {
//not junction edge
p = Edges[e]..node1;
//'get len of this edge
dist1 = distance(p, Edges[e]..node2);
//'moving will exceed MaxShift
if (borderShifts[moving] + dist1 > maxShift) { //*TODO:** goto found: GoTo lSkipAsLong; }
//'get other end of edge
if (p == borderNodes[moving]) { p = Edges[e]..node2; }
//calc new sum of distances from this border-node to all others
dist = 0;
for (j = 0; j <= borderNum - 1; j++) {
if (j != moving) {
dist1 = distance(p, borderNodes[j]);
dist = dist + dist1;
}
}
//'minimizing found
if (dist < dist_min) { dist_min = Dist: node_dist_min == p: edge_dist_min == e; }
//*TODO:** label found: lSkipAsLong:;
}
}
if (node_dist_min > -1) {
//found node, more close to other border-nodes
//'mark for collapse
Edges[edge_dist_min]..mark = Edges[edge_dist_min]..mark || MARK_COLLAPSING;
//'add found node to chain of junction nodes
if (isInChain(node_dist_min) == 0) { addChain(node_dist_min); }
//'at least 1 border-node moved
moved = 1;
//' update passed distance
borderShifts[moving] = borderShifts[moving] + distance(Edges[edge_dist_min]..node1, Edges[edge_dist_min]..node2);
for (i = 0; i <= borderNum - 1; i++) {
if (node_dist_min == borderNodes[i]) {
//after moving border-node joined with another one - remove
if (borderShifts[i] < borderShifts[moving]) {
//joined with node with smaller moves - keep smallest
borderShifts[i] = borderShifts[moving];
}
//join
borderNodes[moving] = borderNodes[borderNum - 1];
borderShifts[moving] = borderShifts[borderNum - 1];
borderNum = borderNum - 1;
//'only 1 border-node left
if (borderNum == 1) { //*TODO:** goto found: GoTo lReachOne; }
//'back to moving this node
//*TODO:** goto found: GoTo lRestartMoving;
}
}
//border-node not joined, just moved
borderNodes[moving] = node_dist_min;
//*TODO:** goto found: GoTo lRestartMoving;
}
//not found - proceeding to next node
moving = moving + 1;
}
//'some border-nodes were moved, repeat cycle
if (moved == 1) { //*TODO:** goto found: GoTo lRestartCycle; }
//no border-nodes moved during whole cycle - looks like shrinking reached minimum
if (borderNum > 1) {
//2 or more border nodes remains
//'all border-nodes
for (i = 0; i <= borderNum - 1; i++) {
//'all edges of it
for (k = 0; k <= Nodes[borderNodes[i]].Edges - 1; k++) {
e = Nodes[borderNodes[i]]..edge(k);
if ((Edges[e]..mark && MARK_JUNCTION) == 0) {
//not junction edge -> edge of main road
for (j = 0; j <= borderNum - 1; j++) {
//'not the same border-node
if (j != i) {
dist = distanceToSegment(Edges[e]..node1, Edges[e]..node2, borderNodes[j]);
if (DistanceToSegment_last_case == 3) {
//3rd case distance - interval internal point is closer to border-node j than both ends of interval
//-> mark edge and both nodes for collapsing
//'mark for definite collapse
Edges[e]..mark = Edges[e]..mark || MARK_COLLAPSING;
if (isInChain(Edges[e]..node1) == 0) { addChain(Edges[e]..node1); }
if (isInChain(Edges[e]..node2) == 0) { addChain(Edges[e]..node2); }
}
}
}
}
}
}
}
//*TODO:** label found: lReachOne:;
//one border-node reach - end
}
//mark one half of loop as junction by moving from node to node with smallest temp_dist
//node1 - start node (i.e. where waves collide)
public static void markLoopHalf(int node1) {
Long, i = null; e As Long, d As Long
Double, min_dist = null; min_dist_node As Long, min_dist_edge As Long
int node = 0;
node = node1;
//*TODO:** label found: lMoveNext:;
//'reached start node - exit
if (Nodes[node]..mark == 1 || Nodes[node]..mark == -1) { return; }
//find near node with smaller temp_dist
min_dist = Nodes[node]..temp_dist;
min_dist_node = -1;
min_dist_edge = -1;
//'check all edges
for (i = 0; i <= Nodes[node].Edges - 1; i++) {
e = Nodes[node]..edge(i);
.d = Edges[e].node1;
if (.d == node) { .d = Edges[e]..node2; }
//d - always other end of edge
if (Nodes[.d]..mark != 0 && Nodes[.d]..temp_dist < min_dist) {
//smaller temp_dist found
min_dist = Nodes[.d]..temp_dist;
min_dist_node = .d;
min_dist_edge = e;
}
}
if (min_dist_edge > -1) {
//'mark passed edge as junction
Edges[min_dist_edge]..mark = Edges[min_dist_edge]..mark || (MARK_JUNCTION);
node = min_dist_node;
//*TODO:** goto found: GoTo lMoveNext;
}
}
//Check edge for participating in short loop (shorted than MaxDist)
//Launch two waves for propagation - one from each end of edge
//if waves collide, they are part of short loop
//waves are limited by length and MARK_DISTCHECK
//if no short loop found, this edge marked with MARK_DISTCHECK (means, no short loop passing this edge)
public static void checkShortLoop2(int edge1, double maxDist) {
Long, i = null; j As Long, k As Long, k2 As Long
Long, e = null; d As Long, q As Long
int node1 = 0;
int node2 = 0;
Double, dist0 = null; Dist1 As Double
//wave starts
node1 = Edges[edge1].node1;
node2 = Edges[edge1].node2;
//'half of edge len - start point is center of edge
dist0 = 0.5 * distance(node1, node2);
Nodes[node1]..mark = 1;
Nodes[node2]..mark = -1;
Edges[edge1]..mark = Edges[edge1]..mark || MARK_WAVEPASSED;
ChainNum = 0;
addChain(node1);
addChain(node2);
Nodes[node1]..temp_dist = dist0;
Nodes[node2]..temp_dist = dist0;
//propagate waves
j = 0;
while (j < ChainNum) {
k = Nodes[Chain[j]]..mark;
if (k > 0) {
k2 = k + 1;
}
else {
k2 = k - 1;
}
dist0 = Nodes[Chain[j]]..temp_dist;
for (i = 0; i <= Nodes[Chain[j]].Edges - 1; i++) {
q = Nodes[Chain[j]]..edge(i);
//'wave already passed this edge
if ((Edges[q]..mark && MARK_WAVEPASSED) != 0) { //*TODO:** goto found: GoTo lSkipEdge; }
//'no short loop here - no need to pass thru this edge
if ((Edges[q]..mark && MARK_DISTCHECK) != 0) { //*TODO:** goto found: GoTo lSkipEdge; }
Edges[q]..mark = Edges[q]..mark || MARK_WAVEPASSED;
.d = Edges[q].node1;
if (.d == Chain[j]) { .d = Edges[q].node2; }
if (Nodes[.d]..mark != 0) {
if ((Nodes[.d]..mark < 0 && k > 0) || (Nodes[.d]..mark > 0 && k < 0)) {
//loop found
//'update by len of this edge
Dist1 = dist0 + distance(.d, Chain[j]);
//'len of second part of wave
Dist1 = Dist1 + Nodes[.d]..temp_dist;
//'loop is too long
if (Dist1 > maxDist) { //*TODO:** goto found: GoTo lSkipEdge; }
//'short loop found
//*TODO:** goto found: GoTo lShortLoop;
}
//*TODO:** goto found: GoTo lSkipEdge;
}
//'update by len of this edge
Dist1 = dist0 + distance(.d, Chain[j]);
//'set passed len
Nodes[.d]..temp_dist = Dist1;
Nodes[.d]..mark = k2;
//'add to chain, but only if distance from start is not too long
if (Dist1 < maxDist) { addChain(.d); }
//*TODO:** label found: lSkipEdge:;
}
j = j + 1;
}
//short loop not found
//'no short passing this edge
Edges[edge1]..mark = Edges[edge1]..mark || MARK_DISTCHECK;
//*TODO:** goto found: GoTo lClearTemp;
//*TODO:** label found: lShortLoop:;
//short loop found
//'mark final edge
Edges[q]..mark = Edges[q]..mark || (MARK_JUNCTION);
//mark both loop half by moving backward from collision edge to start
markLoopHalf(.d);
markLoopHalf(Chain[j]);
//'mark start edge
Edges[edge1]..mark = Edges[edge1]..mark || (MARK_JUNCTION);
//*TODO:** label found: lClearTemp:;
//clear all temp marks
for (j = 0; j <= ChainNum - 1; j++) {
Nodes[Chain[j]]..mark = 0;
Nodes[Chain[j]]..temp_dist = 0;
for (i = 0; i <= Nodes[Chain[j]].Edges - 1; i++) {
q = Nodes[Chain[j]]..edge(i);
Edges[q]..mark = Edges[q]..mark && (-1 Xor MARK_WAVEPASSED);
}
}
}
//Find centroid of junction by aiming-edges
//Will find location, equally distant from all lines (defined by AimEdges)
//Iterative search by 5 points, combines moving into direction of minimizing sum of squares of distances
//and bisection method to clarify centroid position
public static void findAiming(node result, double angleLimit) { // TODO: Use of ByRef founded
double px = 0;
double py = 0;
double dx = 0;
double dy = 0;
double q = 0;
Long, i = null; j As Long, t As Long
Double, v = null; v1 As Double, v2 As Double, v3 As Double, v4 As Double
Double, dvx = null; dvy As Double
double estStepX = 0;
double estStepY = 0;
//Dim phase As Long
double maxAngle = 0;
px = 0;
py = 0;
if (AimEdgesNum == 0) { return; }
//calculate equation elements of all aimedges
//equation: Distance of (x,y) = a * x + b * y + c
//q[i] = 1 / sqrt(((y2[i]-y1[i])^2+(x2[i]-x1[i])^2)
//a[i] = (y2[i]-y1[i])*q[i]
//b[i] = (x1[i]-x2[i])*q[i]
//c[i] = (y1[i]*x2[i]-x1[i]*y2[i])*q[i]
//also calc default centroid as average of all aimedges lat1-lot1 coords
for (i = 0; i <= AimEdgesNum - 1; i++) {
//TODO: fix (not safe to 180/-180 edge)
px = px + AimEdges[i]..lat1;
py = py + AimEdges[i]..lon1;
dx = AimEdges[i]..lat2 - AimEdges[i]..lat1;
dy = AimEdges[i]..lon2 - AimEdges[i]..lon1;
q = Sqr(dx * dx + dy * dy);
AimEdges[i]..d = q;
if (q != 0) {
q = 1 / q;
}
//' a and b is normalized normal to edge
AimEdges[i]..a = dy * q;
AimEdges[i]..b = -dx * q;
AimEdges[i]..c = (AimEdges[i]..lon1 * AimEdges[i]..lat2 - AimEdges[i]..lon2 * AimEdges[i]..lat1) * q;
}
px = px / AimEdgesNum;
py = py / AimEdgesNum;
//check max angle between aimedges
//angle is checked in lat/lon grid, so not exactly angle in real world
maxAngle = 0;
for (i = 1; i <= AimEdgesNum - 1; i++) {
for (j = 0; j <= i - 1; j++) {
//vector product of normals, result is sin(angle)
//angle is smallest of (a,180-a)
q = Abs(AimEdges[i]..a * AimEdges[j]..b - AimEdges[i]..b * AimEdges[j]..a);
if (q > maxAngle) { maxAngle = q; }
}
}
//'angle is too small, iterative aiming will make big error along roads and should not be used
if (maxAngle < angleLimit) { //*TODO:** goto found: GoTo lResult; }
//OK, angle is good => lets start iterative search
//initial steps
estStepX = 0.0001;
estStepY = 0.0001;
t = 0;
//px and py is start location
//*TODO:** label found: lNextStep:;
t = t + 1;
v = 0;
v1 = 0;
v2 = 0;
v3 = 0;
v4 = 0;
//calc distance in 5 points - current guess and 4 points on ends of "+"-cross
for (i = 0; i <= AimEdgesNum - 1; i++) {
//sum of module distances, not good
// v = v + Abs(px * AimEdges(i).a + py * AimEdges(i).b + AimEdges(i).c)
// v1 = v1 + Abs((px + EstStepX) * AimEdges(i).a + py * AimEdges(i).b + AimEdges(i).c)
// v2 = v2 + Abs((px - EstStepX) * AimEdges(i).a + py * AimEdges(i).b + AimEdges(i).c)
// v3 = v3 + Abs(px * AimEdges(i).a + (py + EstStepY) * AimEdges(i).b + AimEdges(i).c)
// v4 = v4 + Abs(px * AimEdges(i).a + (py - EstStepY) * AimEdges(i).b + AimEdges(i).c)
//sum of square distances - better
v = v + (px * AimEdges[i]..a + py * AimEdges[i]..b + AimEdges[i]..c) ^ 2;
v1 = v1 + ((px + estStepX) * AimEdges[i]..a + py * AimEdges[i]..b + AimEdges[i]..c) ^ 2;
v2 = v2 + ((px - estStepX) * AimEdges[i]..a + py * AimEdges[i]..b + AimEdges[i]..c) ^ 2;
v3 = v3 + (px * AimEdges[i]..a + (py + estStepY) * AimEdges[i]..b + AimEdges[i]..c) ^ 2;
v4 = v4 + (px * AimEdges[i]..a + (py - estStepY) * AimEdges[i]..b + AimEdges[i]..c) ^ 2;
}
if (v > v1 || v > v2 || v > v3 || v > v4) {
//v is not smallest => centroid location is not in covered by our cross (px+-EstStepX,py+-EstStepY)
//=> we need to shift
if (v > v1 || v > v2) {
//shift by X (by half of quad) in direction to minimize v
if (v1 < v2) { px = px + estStepX * 0.5 Else px == px - estStepX * 0.5; }
}
if (v > v3 || v > v4) {
//shift by Y (by half of quad) in direction to minimize v
if (v3 < v4) { py = py + estStepY * 0.5 Else py == py - estStepY * 0.5; }
}
//*TODO:** goto found: GoTo lNextStep;
}
else {
//v is smallest => centroid location IS covered by our cross (px+-EstStepX,py+-EstStepY)
//we need to select sub-rectangle to clarify position
//find q as max of v1-v4
q = v1: i == 1;
if (v2 > q) { q = v2: i == 2; }
if (v3 > q) { q = v3: i == 3; }
if (v4 > q) { q = v4: i == 4; }
switch (i) {
case 4:
//v4 is max, select half with v3
py = py + estStepY * 0.5;
estStepY = estStepY * 0.5;
break;
case 3:
//v3 is max, select half with v4
py = py - estStepY * 0.5;
estStepY = estStepY * 0.5;
break;
case 2:
//v2 is max, select half with v1
px = px + estStepX * 0.5;
estStepX = estStepX * 0.5;
break;
case 1:
//v1 is max, select half with v2
px = px - estStepX * 0.5;
estStepX = estStepX * 0.5;
break;
}
//if required accuracy not yet reached - continue
//exit if 100k iteration does not help
if (t < 100000 && estStepX > 0.0000001 || estStepY > 0.0000001) { //*TODO:** goto found: GoTo lNextStep; }
}
//OK, found
//*TODO:** label found: lResult:;
result..lat = px;
result..lon = py;
}
//Calc speedclass and label of combined subchain of edges
public static void estimateChain(int indexStart, int indexLast) {
Long, i = null; j As Long
for (i = 0; i <= 10; i++) {
SpeedHistogram[i] = 0;
}
EstimateChain_label = "";
EstimateChain_speed = 0;
resetLabelStats();
for (i = indexStart; i <= indexLast - 1; i++) {
j = getEdgeBetween(Chain[i], Chain[i + 1]);
if (j >= 0) {
//'add label of edge into stats
addLabelStat0(Edges[j]..label);
j = Edges[j]..speed;
//'add speed into histogram
SpeedHistogram[j] = SpeedHistogram[j] + 1;
}
}
//'estimate speed
EstimateChain_speed = estimateSpeedByHistogram();
//'calc resulting label
EstimateChain_label = getLabelByStats(0);
}
//Estimate speed class of road by histogram
public static int estimateSpeedByHistogram() {
int _rtn = 0;
Long, total = null; i As Long
//call total sum
for (i = 0; i <= 10; i++) {
total = total + SpeedHistogram[i];
}
//'default speedclass
_rtn = 3;
//'should never happens
if (total == 0) { return _rtn; }
//find speedclass with 90% coverage
for (i = 0; i <= 10; i++) {
if (SpeedHistogram[i] > total * 0.9) {
//90% of chain have this speedclass
_rtn = i;
return _rtn;
}
}
//no 90%
//find minimum speedclass with 40% coverage
for (i = 0; i <= 10; i++) {
if (SpeedHistogram[i] > total * 0.4) {
//40% of chain have this speedclass
_rtn = i;
return _rtn;
}
}
//no 40% (very much alike will not happens)
//find minimum speedclass with 10% coverage
for (i = 0; i <= 10; i++) {
if (SpeedHistogram[i] > total * 0.1) {
//10% of chain have this speedclass
_rtn = i;
return _rtn;
}
}
//no 10% (almost impossible)
//find minimum speedclass with >0 coverage
for (i = 0; i <= 10; i++) {
if (SpeedHistogram[i] > 0) {
_rtn = i;
return _rtn;
}
}
return _rtn;
}
//Delete edges which connect node with itself
public static void filterVoidEdges() {
int i = 0;
for (i = 0; i <= EdgesNum - 1; i++) {
if (Edges[i](..node1 != -1) && Edges[i]..node1 == Edges[i]..node2) {
delEdge(i);
}
}
}
//Combine edges. edge2 is deleted, edge1 is kept
//assumed, that edges have at leaset 1 common node
//return: 0 - not combined, 1 - combined
public static Object combineEdges(int edge1, int edge2, int commonNode) {
Object _rtn = null;
_rtn = 0;
if (combineEdgeParams(edge1, edge2, commonNode) > 0) {
_rtn = 1;
delEdge(edge2);
}
return _rtn;
}
//Compare roadtype-s
//return: 1 - type1 have higher priority, -1 - type2 have higher priority, 0 - equal
public static int compareRoadtype(int type1, int type2) {
int _rtn = 0;
if (type1 == type2) {
//'just equal
_rtn = 0;
}
else if ((type1 && HIGHWAY_MASK_LINK) != 0 && (type2 && HIGHWAY_MASK_LINK) == 0) {
//'type1 is link, type2 is not
_rtn = -1;
}
else if ((type1 && HIGHWAY_MASK_LINK) == 0 && (type2 && HIGHWAY_MASK_LINK) != 0) {
//'type2 is link, type1 is not
_rtn = 1;
}
else if ((type1 && HIGHWAY_MASK_MAIN) < (type2 && HIGHWAY_MASK_MAIN)) {
//'type1 is less numerically - higher
_rtn = 1;
}
else if ((type1 && HIGHWAY_MASK_MAIN) > (type2 && HIGHWAY_MASK_MAIN)) {
//'type1 is higher numerically - less
_rtn = -1;
}
else {
//should not happen
_rtn = 0;
}
return _rtn;
}
//Combine edge parameters and store it to edge1
//return: 0 - not possible to combine, 1 - combined
public static Object combineEdgeParams(int edge1, int edge2, int commonNode) {
Object _rtn = null;
int k1 = 0;
int k2 = 0;
int k3 = 0;
_rtn = 0;
if (commonNode == -1) {
//common node not specified in call
if (Edges[edge1]..node1 == Edges[edge2]..node1 || Edges[edge1]..node1 == Edges[edge2]..node2) {
commonNode = Edges[edge1]..node1;
}
else if (Edges[edge1]..node2 == Edges[edge2]..node1 || Edges[edge1]..node2 == Edges[edge2]..node2) {
commonNode = Edges[edge1]..node2;
}
else {
//can't combine edges without at least one common point
return _rtn;
}
}
//calc combined label - by stats
resetLabelStats();
addLabelStat0(Edges[edge1]..label);
addLabelStat0(Edges[edge2]..label);
Edges[edge1]..label = getLabelByStats(0);
//calc combiner road type
if (Edges[edge1]..roadtype != Edges[edge2]..roadtype) {
//combine main road type - higher by OSM
k1 = Edges[edge1]..roadtype && HIGHWAY_MASK_MAIN;
k2 = Edges[edge2]..roadtype && HIGHWAY_MASK_MAIN;
//'keep link only if both are links
k3 = (Edges[edge2]..roadtype && Edges[edge2]..roadtype && HIGHWAY_MASK_LINK);
//'numerically min roadtype
if (k2 < k1) { k1 = k2; }
Edges[edge1]..roadtype = k1 || k3;
}
//combined speed - lower
if (Edges[edge2]..speed < Edges[edge1]..speed) {
Edges[edge1]..speed = Edges[edge2]..speed;
}
if (Edges[edge1]..oneway == 1) {
//combined oneway - keep only if both edges directed in one way
if (Edges[edge2]..oneway == 1) {
//both edges are oneway
if (Edges[edge1]..node1 == commonNode && Edges[edge2]..node2 == commonNode) {
//edges are opposite oneway, result is bidirectional
Edges[edge1]..oneway = 0;
}
else if (Edges[edge1]..node2 == commonNode && Edges[edge2]..node1 == commonNode) {
//edges are opposite oneway, result is bidirectional
Edges[edge1]..oneway = 0;
}
//else - result is oneway
}
else {
//edge2 is bidirectional, so result also
Edges[edge1]..oneway = 0;
}
}
//if edge1 is bidirectional, so also result
_rtn = 1;
return _rtn;
}
//Join edges with very acute angle into one
//1) distance between edges ends < JoinDistance
//2) angle between edges lesser than limit
//AcuteKoeff: 1/tan() of limit angle (3 =>18.4 degrees)
public static void joinAcute(double joinDistance, double acuteKoeff) {
Long, i = null; j As Long, k As Long, m As Long, n As Long, p As Long
int q = 0;
double dist = 0;
int merged = 0;
int passNumber = 0;
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..nodeID != MARK_NODEID_DELETED && Nodes[i].Edges > 1) {
//'mark to check, not deleted with 2+ edges
Nodes[i]..mark = 1;
}
else {
//'mark to skip
Nodes[i]..mark = 0;
}
}
passNumber = 1;
//*TODO:** label found: lIteration:;
merged = 0;
for (i = 0; i <= NodesNum - 1; i++) {
if (Nodes[i]..mark == 1) {
//check for edges connecting same nodes several times
//made by filling Chain array with other ends of edges
ChainNum = 0;
j = 0;
while (j < Nodes[i].Edges) {
k = Edges[Nodes[i]..edge(j)]..node1;
//'get other end
if (k == i) { k = Edges[Nodes[i]..edge(j)]..node2; }
m = findInChain(k);
if (m == -1) {
//first occurence in chain
addChain(k);
}
else {
//not first - should join
m = getEdgeBetween(i, k);
//'combining succeed, we should check j-th edge once again
if (combineEdges(m, Nodes[i]..edge(j), i) > 0) { //*TODO:** goto found: GoTo lAgain; }
}
j = j + 1;
//*TODO:** label found: lAgain:;
}
//'node is processed, mark to skip
Nodes[i]..mark = 0;
for (j = 0; j <= ChainNum - 1; j++) {
//'skip removed nodes
if (Chain[j] == -1) { //*TODO:** goto found: GoTo lSkipJ; }
//'skip deleted nodes
if (Nodes[Chain[j]]..nodeID == MARK_NODEID_DELETED) { //*TODO:** goto found: GoTo lSkipJ; }
for (k = 0; k <= ChainNum - 1; k++) {
//'skip same and removed nodes
if (j == k || Chain[k] == -1) { //*TODO:** goto found: GoTo lSkipK; }
//'skip deleted nodes
if (Nodes[Chain[k]]..nodeID == MARK_NODEID_DELETED) { //*TODO:** goto found: GoTo lSkipK; }
//'distance from Chain(k) to interval i-Chain(j)
dist = distanceToSegment(i, Chain[j], Chain[k]);
if (dist < joinDistance) {
//node Chain(k) is close to edge i->Chain(j)
if (distance(Chain[j], Chain[k]) < joinDistance) {
//Chain(k) is close to Chain(j), they should be combined
//'edge i-Chain(j)
m = getEdgeBetween(i, Chain[j]);
//'edge i-Chain(k)
n = getEdgeBetween(i, Chain[k]);
if (m >= 0 && n >= 0) {
//*TODO:** label found: lCheckEdge:;
//remove any edges from Chain(j) to Chain(k)
p = getEdgeBetween(Chain[j], Chain[k]);
if (p >= 0) {
delEdge(p);
//*TODO:** goto found: GoTo lCheckEdge;
}
//'at least one change made
merged = merged + 1;
//'mark node to check again
Nodes[i]..mark = 1;
q = compareRoadtype(Edges[m]..roadtype, Edges[n]..roadtype);
if (q == -1) {
//edge n have higher priority
//'combine edge m into n
combineEdges(n, m, i);
//'combine node Chain(j) into Chain(k) w/o moving Chain(k)
mergeNodes(Chain[k], Chain[j], 1);
//'mark node to check once again
Nodes[Chain[k]]..mark = 1;
//'remove Chain(j) from chain
Chain[j] = -1;
//'proceed to next j
//*TODO:** goto found: GoTo lSkipJ;
}
else {
//edge m have higher priority or edges are equal
//'combine edge n into m
combineEdges(m, n, i);
if (q == 0) {
//edges are equal
//'combine with averaging coordinates
mergeNodes(Chain[j], Chain[k], 0);
}
else {
//edge m have higher priority
//'combine w/o moving Chain(j)
mergeNodes(Chain[j], Chain[k], 1);
}
//'mark node to check once again
Nodes[Chain[j]]..mark = 1;
//'remove Chain(k) from chain
Chain[k] = -1;
//'proceed to next k
//*TODO:** goto found: GoTo lSkipK;
}
}
}
else if (distance(i, Chain[k]) > dist * acuteKoeff) {
//distance from i to chain(k) is higher than distance from Chain(k) to interval i-Chain(j) in AcuteKoeff times
//=> angle Chain(k)-i-Chain(j) < limit angle
//=>
//Chain(k) should be inserted into edge i-Chain(j)
//edge i-Chain(j) became Chain(k)-Chain(j) and keeps all params
//edge i-Chain(k) became joined by params
//'edge i-Chain(j) - long edge
m = getEdgeBetween(i, Chain[j]);
//'edge i-Chain(k) - short edge
n = getEdgeBetween(i, Chain[k]);
if (m >= 0 && n >= 0) {
if (compareRoadtype(Edges[m]..roadtype, Edges[n]..roadtype) == -1) {
//edge n have higher priority
}
else {
//edge m have higher priority or equal
//'move Chain(k) to line i-Chain(j)
projectNode(i, Chain[j], Nodes[Chain[k]]);
}
//'combine params from m into n
combineEdgeParams(n, m, i);
//'edge m is now Chain(k)-Chain(j)
reconnectEdge(m, i, Chain[k]);
//'mark nodes as needed to check once again
Nodes[Chain[j]]..mark = 1;
Nodes[Chain[k]]..mark = 1;
Nodes[i]..mark = 1;
//'at least one change made
merged = merged + 1;
//'remove Chain(j) from chain, as it is not connected to node i
Chain[j] = -1;
//'proceed to next j
//*TODO:** goto found: GoTo lSkipJ;
}
}
}
//*TODO:** label found: lSkipK:;
}
//*TODO:** label found: lSkipJ:;
}
}
if ((i && 8191) == 0) {
//show progress
Form1.Caption = "JA #" + CStr(passNumber) + " : " + CStr(i) + " / " + CStr(NodesNum): Form1.Refresh;
DoEvents;
}
}
if (merged > 0) {
//at least one change made - relaunch algorithm
passNumber = passNumber + 1;
//'show progress
Form1.Caption = "JoinAcute " + CStr(passNumber) + ": " + CStr(merged);
//*TODO:** goto found: GoTo lIteration;
}
}
//Reconnect edge1 from node1 to node2
//assumed that node1 is present in edge1
public static void reconnectEdge(int edge1, int node1, int node2) {
int i = 0;
if (Edges[edge1].node1 == node1) {
Edges[edge1].node1 = node2;
}
else {
Edges[edge1].node2 = node2;
}
//remove edge1 from node1 edges
for (i = 0; i <= Nodes[node1].Edges - 1; i++) {
if (Nodes[node1]..edge(i) == edge1) {
Nodes[node1]..edge(i) = Nodes[node1]..edge(Nodes[node1].Edges - 1);
Nodes[node1].Edges = Nodes[node1].Edges - 1;
//*TODO:** goto found: GoTo lFound;
}
}
//*TODO:** label found: lFound:;
//add edge1 to node2 edges
Nodes[node2]..edge(Nodes[node2].Edges) = edge1;
Nodes[node2].Edges = Nodes[node2].Edges + 1;
}
//Get bounding box of edge
public static bbox getEdgeBbox(int edge1) {
getEdgeBbox()..lat_min = Nodes[Edges[edge1]..node1]..lat;
getEdgeBbox()..lat_max = Nodes[Edges[edge1]..node1]..lat;
getEdgeBbox()..lon_min = Nodes[Edges[edge1]..node1]..lon;
getEdgeBbox()..lon_max = Nodes[Edges[edge1]..node1]..lon;
if (getEdgeBbox()..lat_min > Nodes[Edges[edge1]..node2]..lat) {
getEdgeBbox()..lat_min = Nodes[Edges[edge1]..node2]..lat;
}
if (getEdgeBbox()..lat_max < Nodes[Edges[edge1]..node2]..lat) {
getEdgeBbox()..lat_max = Nodes[Edges[edge1]..node2]..lat;
}
if (getEdgeBbox()..lon_min > Nodes[Edges[edge1]..node2]..lon) {
getEdgeBbox()..lon_min = Nodes[Edges[edge1]..node2]..lon;
}
if (getEdgeBbox()..lon_max < Nodes[Edges[edge1]..node2]..lon) {
getEdgeBbox()..lon_max = Nodes[Edges[edge1]..node2]..lon;
}
}
//Expand bounding box by distance in metres
public static Object expandBbox(bbox bbox1, double dist) { // TODO: Use of ByRef founded
double cos1 = 0;
double cos2 = 0;
double dist_angle = 0;
//'distance in degrees of latitude
dist_angle = RADTODEG * dist / DATUM_R_OVER;
bbox1..lat_min = bbox1..lat_min - dist_angle;
bbox1..lat_max = bbox1..lat_max + dist_angle;
cos1 = Cos(bbox1..lat_min * DEGTORAD);
cos2 = Cos(bbox1..lat_max * DEGTORAD);
//'smallest cos() - further from equator
if (cos2 < cos1) { cos1 = cos2; }
//'distance in degrees of longtitue
dist_angle = dist_angle / cos1;
bbox1..lon_min = bbox1..lon_min - dist_angle;
bbox1..lon_max = bbox1..lon_max + dist_angle;
//TODO: fix (not safe to 180/-180 edge)
}
//Join two directions of road way
//MaxCosine - cosine of max angle between start edges, -0.996 means (175,180) degrees - contradirectional edges or close
//MaxCosine2 - cosine of max angle between other edges, during going-by-two-ways
//MinChainLen - length of min two-way road to join
public static void joinDirections3(double joinDistance, double maxCosine, double maxCosine2, double minChainLen, double combineDistance) {
Long, i = null; j As Long, k As Long, mode1 As Long
Long, e = null; d As Long, q As Long
Double, dist1 = null; dist2 As Double
bbox bbox_edge = null;
double angl = 0;
Double, min_dist = null; min_dist_edge As Long
int roadtype = 0;
int speednew = 0;
//'chain of forward edges
int[] edgesForw() = null;
//'chain of backward edges
int[] edgesBack() = null;
//'1 if road is circled
int loopChain = 0;
//'len of half of road
int halfChain = 0;
//Algorithm will check all non-link oneway edges for presence of contradirectional edge in the vicinity
//All found pairs of edges will be checked in both directions by GoByTwoWays function
//for presence of continuous road of one type
//During this check will be created new chain of nodes, which is projection of joining nodes into middle line
//Then both found ways will be joined into one bidirectional way, consist from new nodes
//All related roads will reconnected to new way and old edges were deleted
//mark all nodes as not checked
for (i = 0; i <= NodesNum - 1; i++) {
//'not moved
Nodes[i]..mark = -1;
}
for (i = 0; i <= EdgesNum - 1; i++) {
Edges[i]..mark = 1;
//'skip deleted and 2-ways edges
if (Edges[i]..node1 == -1 || Edges[i]..oneway == 0) { //*TODO:** goto found: GoTo lFinMarkEdge; }
//'skip links
if ((Edges[i].roadtype && HIGHWAY_MASK_LINK) > 0) { //*TODO:** goto found: GoTo lFinMarkEdge; }
//'skip edges between complex connections
if (Nodes[Edges[i]..node1].Edges != 2 && Nodes[Edges[i]..node2].Edges != 2) { //*TODO:** goto found: GoTo lFinMarkEdge; }
Edges[i]..mark = 0;
//*TODO:** label found: lFinMarkEdge:;
}
//rebuild cluster-index from 0
buildNodeClusterIndex(0);
for (i = 0; i <= EdgesNum - 1; i++) {
//'skip marked edge or deleted
if (Edges[i]..mark > 0 || Edges[i]..node1 < 0) { //*TODO:** goto found: GoTo lSkipEdge; }
//'get bbox
bbox_edge = getEdgeBbox(i);
//'expand it
expandBbox(bbox_edge, joinDistance);
min_dist = joinDistance;
min_dist_edge = -1;
//'first
mode1 = 0;
//*TODO:** label found: lSkipNode2:;
k = getNodeInBboxByCluster(bbox_edge, mode1);
//'next (next time)
mode1 = 1;
//'no more nodes
if (k == -1) { //*TODO:** goto found: GoTo lAllNodes; }
//'skip nodes of same edge, deleted and complex nodes
if (k == Edges[i]..node1 || k == Edges[i]..node2 || Nodes[k]..nodeID == MARK_NODEID_DELETED || Nodes[k].Edges != 2) { //*TODO:** goto found: GoTo lSkipNode2; }
//'calc dist from found node to our edge
dist1 = distanceToSegment(Edges[i]..node1, Edges[i]..node2, k);
//'too far, skip
if (dist1 > min_dist) { //*TODO:** goto found: GoTo lSkipNode2; }
//node is on join distance, check all (2) edges
for (d = 0; d <= 1; d++) {
q = Nodes[k]..edge(.d);
//'deleted or 2-way edge or other road class
if (Edges[q]..node1 == -1 || Edges[q]..oneway == 0 || Edges[q].roadtype != Edges[i].roadtype) { //*TODO:** goto found: GoTo lSkipEdge2; }
angl = cosAngleBetweenEdges(q, i);
if (angl < maxCosine) {
//contradirectional edge or close
dist1 = distanceBetweenSegments(i, q);
//'found edge close enough
if (dist1 < min_dist) { min_dist = Dist1: min_dist_edge == q; }
}
//*TODO:** label found: lSkipEdge2:;
}
//*TODO:** label found: //*TODO:** goto found: GoTo lSkipNode2:;
//*TODO:** label found: lAllNodes:;
//all nodes in bbox check
if (min_dist_edge > -1) {
//found edge close enough
//now - trace two ways in both directions
//in the process we will fill Chain array with all nodes of joining ways
//sequence of nodes in Chain will correspond to sequence of nodes on combined way
//index of new node, where old node should join, will in .mark field of old nodes
//also will be created two lists of deleting edges separated to two directions - arrays TWforw and TWback
roadtype = Edges[i].roadtype;
loopChain = 0;
ChainNum = 0;
TWforwNum = 0;
TWbackNum = 0;
//first pass, in direction of edge i
goByTwoWays(i, min_dist_edge, joinDistance, combineDistance, maxCosine2, 0);
//reverse of TWforw and TWback removed, as order of edges have no major effect
//reverse Chain
reverseArray(Chain, ChainNum);
//second pass, in direction of min_dist_edge
goByTwoWays(min_dist_edge, i, joinDistance, combineDistance, maxCosine2, 1);
//'first and last nodes coincide - this is loop road
if (Chain[0] == Chain[ChainNum - 1]) { loopChain = 1; }
//'half len of road in nodes
halfChain = ChainNum / 2;
//'will "kill" halfchain limit for very short loops
if (halfChain < 10) { halfChain = ChainNum + 1; }
//call metric length of found road
dist1 = 0;
for (j = 1; j <= ChainNum - 1; j++) {
dist1 = dist1 + distance(Nodes[Chain[j - 1]]..mark, Nodes[Chain[j]]..mark);
}
if (dist1 < minChainLen) {
//road is too short -> unmark all edges and not delete anything
for (j = 0; j <= ChainNum - 1; j++) {
for (k = 0; k <= Nodes[Chain[j]].Edges - 1; k++) {
if (Edges[Nodes[Chain[j]]..edge(k)]..mark == 2) {
Edges[Nodes[Chain[j]]..edge(k)]..mark = 1;
}
}
}
//*TODO:** goto found: GoTo lSkipDel;
}
//process both directions edges list
//to build index of edges, which joins between each pair of nodes in Chain
//note: is some rare cases chain of nodes have pleats, where nodes of one directions
//in Chain swaps position due to non uniform projecting of nodes to middle-line
//In this cases one or more edges joins to bidirectional road in backward direction
//to the original direction of this one-way line
//These edges could be ignored during combining parameter of bidirectional road
//(as they are usually very short)
//also at least two other edges will overlap in at least one interval between nodes
//only one of them will be counted during combining parameter (last in TW* array)
//this is considired acceptable, as they are near edges of very same road
G.redim(edgesForw, ChainNum);
G.redim(edgesBack, ChainNum);
for (j = 0; j <= ChainNum - 1; j++) {
edgesForw[j] = -1;
edgesBack[j] = -1;
}
//process forward direction
for (j = 0; j <= TWforwNum - 1; j++) {
e = Edges[TWforw[j]]..node1;
.d = Edges[TWforw[j]]..node2;
//'get indexes of nodes inside Chain
e = findInChain(e);
.d = findInChain(.d);
if (e == -1 || .d == -1) {
//(should not happen)
//edge with nodes not in chain - skip
//*TODO:** goto found: GoTo lSkip1;
}
if (e < .d) {
//normal forward edge (or pleat crossing 0 of chain)
// ... e ---> d .....
//'skip too long edges on loop chains as it could be wrong (i.e. pleat edge which cross 0 of chain)
if (loopChain == 1 && (.d - e) > halfChain) { //*TODO:** label found: //*TODO:** goto found: GoTo lSkip1:; }
for (q = e; q <= .d - 1; q++) {
//in forward direction between q and q+1 node is edge TWforw(j)
edgesForw[q] = TWforw[j];
}
}
else {
//pleat edge (or normal crossing 0 of chain)
// ---.---> d .... ... .... e --->
//'on straight chains forward edge could not go backward without pleat
if (loopChain == 0) { //*TODO:** goto found: GoTo lSkip1; }
if ((e - .d) > halfChain) {
//e and d is close to ends of chain
//-> this is really forward edge crossing 0 of chain in a loop road
for (q = 0; q <= .d - 1; q++) {
edgesForw[q] = TWforw[j];
}
for (q = e; q <= ChainNum - 1; q++) {
edgesForw[q] = TWforw[j];
}
}
}
//*TODO:** label found: lSkip1:;
}
//process backward direction
for (j = 0; j <= TWbackNum - 1; j++) {
e = Edges[TWback[j]]..node1;
.d = Edges[TWback[j]]..node2;
//'get indexes of nodes inside Chain
e = findInChain(e);
.d = findInChain(.d);
if (e == -1 || .d == -1) {
//(should not happen)
//edge with nodes not in chain - skip
//*TODO:** goto found: GoTo lSkip2;
}
if (.d < e) {
//normal backward edge (or pleat crossing 0 of chain)
// ... d <--- e .....
//'skip too long edges on loop chains as it could be wrong (i.e. pleat edge which cross 0 of chain)
if (loopChain == 1 && (e - .d) > halfChain) { //*TODO:** label found: //*TODO:** goto found: GoTo lSkip2:; }
for (q = .d; q <= e - 1; q++) {
edgesBack[q] = TWback[j];
}
}
else {
//pleat edge (or normal crossing 0 of chain)
// <-.-- e ... ... .... ... d <--.---.---
//'on straight chains backward edge could not go forward without pleat
if (loopChain == 0) { //*TODO:** goto found: GoTo lSkip2; }
if ((.d - e) > halfChain) {
//e and d is close to ends of chain
//-> this is really backward edge crossing 0 of chain in a loop road
for (q = 0; q <= e - 1; q++) {
edgesBack[q] = TWback[j];
}
for (q = .d; q <= ChainNum - 1; q++) {
edgesBack[q] = TWback[j];
}
}
}
//*TODO:** label found: lSkip2:;
}
for (j = 1; j <= ChainNum - 1; j++) {
.d = Nodes[Chain[j - 1]]..mark;
e = Nodes[Chain[j]]..mark;
if (.d != e) {
k = joinByEdge(Nodes[Chain[j - 1]]..mark, Nodes[Chain[j]]..mark);
Edges[k].roadtype = roadtype;
Edges[k]..oneway = 0;
Edges[k]..mark = 1;
if (edgesForw[j - 1] (== -1) && edgesBack[j - 1] == -1) {
//no edges for this interval between nodes
//(should never happens)
//'default value
Edges[k]..speed = 3;
Edges[k]..label = "";
}
else {
//get minimal speed class of both edges
speednew = 10;
resetLabelStats();
if (edgesForw[j - 1] != -1) {
//forward edge present
speednew = Edges[edgesForw[j - 1]]..speed;
addLabelStat0(Edges[edgesForw[j - 1]]..label);
}
if (edgesBack[j - 1] != -1) {
//backward edge present
if (speednew > Edges[edgesBack[j - 1]]..speed) { speednew = Edges[edgesBack[j - 1]]..speed; }
addLabelStat0(Edges[edgesBack[j - 1]]..label);
}
Edges[k]..speed = speednew;
Edges[k]..label = getLabelByStats(0);
}
//ends of chain could be oneway if only one edge (or even part is joining there
//ex: * ------> * --------> * ----------> *
// * <-------- * <--------- * <---------- *
//joins into:
// *--->*----*------*----*-------*-----*<------*
if (edgesBack[j - 1] == -1) {
//no backward edge - result in one-way
Edges[k]..oneway = 1;
}
else if (edgesForw[j - 1] == -1) {
//no forward edge - result in one-way, backward to other road
Edges[k]..oneway = 1;
Edges[k]..node1 = Nodes[Chain[j]]..mark;
Edges[k]..node2 = Nodes[Chain[j - 1]]..mark;
}
}
}
//delete all old edges
for (j = 0; j <= TWforwNum - 1; j++) {
delEdge(TWforw[j]);
}
for (j = 0; j <= TWbackNum - 1; j++) {
delEdge(TWback[j]);
}
//merge all old nodes into new ones
for (j = 0; j <= ChainNum - 1; j++) {
mergeNodes(Nodes[Chain[j]]..mark, Chain[j], 1);
}
//update cluster index to include only newly created nodes (i.e. nodes of joined road)
buildNodeClusterIndex(1);
//*TODO:** label found: lSkipDel:;
}
//'mark edge as checked
Edges[i]..mark = 1;
//*TODO:** label found: lSkipEdge:;
if ((i && 8191) == 0) {
//show progress
Form1.Caption = "JD3: " + CStr(i) + " / " + CStr(EdgesNum): Form1.Refresh;
DoEvents;
}
}
}
//Reverse array into backward direction
public static void reverseArray(int[] arr, int num) { // TODO: Use of ByRef founded
int i = 0;
int j = 0;
int t = 0;
//'half of len
j = num \ 2;
for (i = 0; i <= j - 1; i++) {
//swap elements from first and second halfs
t = arr(i);
arr(i) = arr(num - 1 - i);
arr(num - 1 - i) == t;
}
}
//Find edges of two way road
//Algorithm goes by finding next edge on side, which is not leading
//Found new node (end of found edge) is projected to local middle line
//Array Chain is filled by found nodes
//Arrays TWforw and TWback is filled by found edges
//
//edge1,edge2 - start edges
//JoinDistance - distance limit between two ways
//CombineDistance - distance to join two nodes into one (on middle line)
//MaxCosine2 - angle limit between edges
//Params: 0 - first pass (chain empty, go by edge1 direction)
// 1 - second pass (chain contains all 4 nodes of edges at the end, go by edge2 direction)
public static void goByTwoWays(int edge1, int edge2, double joinDistance, double combineDistance, double maxCosine2, int params) {
Long, i = null; j As Long, k As Long
//'arrow-head edges
int edge_side1 = 0;
int edge_side2 = 0;
//'arrow-head nodes
Long, side1i = null; side1j As Long
Long, side2i = null; side2j As Long
//'flags of circle on each side
int side1circled = 0;
int side2circled = 0;
int[4] side(4) = null;
double[4] dist(4) = null;
double dist_t = 0;
double dx = 0;
double dy = 0;
Double, px = null; py As Double
double dd = 0;
int roadtype = 0;
double angl = 0;
int calc_side = 0;
Double, angl_min = null; angl_min_edge As Long
int checkchain = 0;
int passNumber = 0;
//'keep road type for comparing
roadtype = Edges[edge1].roadtype;
//'mark edges as participating in joining
Edges[edge1]..mark = 2;
Edges[edge2]..mark = 2;
//'arrow-head of finding chains
edge_side1 = edge1;
edge_side2 = edge2;
//i node is back, j is front of arrow-head - on both sides
side1i = Edges[edge1]..node1;
side1j = Edges[edge1]..node2;
side2i = Edges[edge2]..node2;
side2j = Edges[edge2]..node1;
//'circles not yet found
side1circled = 0;
side2circled = 0;
passNumber = 0;
if ((params && 1)) { passNumber = 1; }
if (passNumber == 1) {
//second pass
//skip initial part, as it is already done in first pass
//*TODO:** goto found: GoTo lKeepGoing;
}
//middle line projection vector
//TODO: fix (not safe to 180/-180 edge)
//'sum of two edges
dx = (Nodes[side1j]..lat - Nodes[side1i]..lat) + (Nodes[side2j]..lat - Nodes[side2i]..lat);
dy = (Nodes[side1j]..lon - Nodes[side1i]..lon) + (Nodes[side2j]..lon - Nodes[side2i]..lon);
//'start point - average of two starts
px = (Nodes[side1i]..lat + Nodes[side2i]..lat) * 0.5;
py = (Nodes[side1i]..lon + Nodes[side2i]..lon) * 0.5;
side[0] = side1i;
side[1] = side1j;
side[2] = side2i;
side[3] = side2j;
//calc relative positions of projections of all 4 noes to edge1
dd = 1 / (dx * dx + dy * dy);
for (i = 0; i <= 3; i++) {
dist[i] = (Nodes[side[i]]..lat - px) * dx + (Nodes[side[i]]..lon - py) * dy;
}
//Sort dist() and side() by dist() by bubble sort
for (i = 0; i <= 3; i++) {
for (j = i + 1; j <= 3; j++) {
if (dist[j] < dist[i]) {
dist_t = dist[j]: dist[j] == dist[i]: dist[i] == dist_t;
k = side[j]: side[j] == side[i]: side[i] == k;
}
}
}
//Add nodes to chain in sorted order
for (i = 0; i <= 3; i++) {
addChain(side[i]);
Nodes[NodesNum].Edges = 0;
Nodes[NodesNum]..nodeID = -1;
Nodes[NodesNum]..mark = -1;
//'info that old node will collapse to this new one
Nodes[side[i]]..mark = NodesNum;
//'projected coordinates
Nodes[NodesNum]..lat = px + dist[i] * dx * dd;
Nodes[NodesNum]..lon = py + dist[i] * dy * dd;
addNode();
}
//*TODO:** label found: lKeepGoing:;
angl_min = MaxCosine2: angl_min_edge == -1;
if (Chain[ChainNum - 1] == side1j) {
//side1 is leading, side2 should be prolonged
calc_side = 2;
}
else {
//side2 is leading, side1 should be prolonged
calc_side = 1;
}
if (calc_side == 2) {
//search edge from side2j which is most opposite to edge_side1
for (i = 0; i <= Nodes[side2j].Edges - 1; i++) {
j = Nodes[side2j]..edge(i);
if (j == edge_side2 || Edges[j]..node1 < 0 || Edges[j]..oneway == 0 || Edges[j].roadtype != roadtype || Edges[j]..node2 != side2j) { //*TODO:** goto found: GoTo lSkipEdgeSide2; }
//skip same edge_side2, deleted, 2-ways, other road types and directed from this node outside
dist_t = distanceBetweenSegments(j, edge_side1);
//'skip too far edges
if (dist_t > joinDistance) { //*TODO:** goto found: GoTo lSkipEdgeSide2; }
angl = cosAngleBetweenEdges(j, edge_side1);
//'remember edge with min angle
if (angl < angl_min) { angl_min = angl: angl_min_edge == j; }
//*TODO:** label found: lSkipEdgeSide2:;
}
//'mark edge as participating in joining
Edges[edge_side2]..mark = 2;
//'add edge to chain (depending on pass number)
addTW(edge_side2, passNumber);
if (angl_min_edge == -1) {
//no edge found - end of chain
//'mark last edge of side1
Edges[edge_side1]..mark = 2;
//'and add it to chain
addTW(edge_side1, 1 - passNumber);
//*TODO:** goto found: GoTo lChainEnds;
}
edge_side2 = angl_min_edge;
//'update i and j nodes of side
side2i = side2j;
side2j = Edges[edge_side2]..node1;
if (Edges[edge_side2]..mark == 2) {
//found marked edge, this means that we found cycle
side2circled = 1;
}
if (side2j == side1j) {
//found joining of two directions, should end chain
//'mark both last edges as participating in joining
Edges[edge_side2]..mark = 2;
Edges[edge_side1]..mark = 2;
//'add them to chains
addTW(edge_side2, passNumber);
addTW(edge_side1, 1 - passNumber);
//*TODO:** goto found: GoTo lChainEnds;
}
}
else {
//search edge from side1j which is most opposite to edge_side2
for (i = 0; i <= Nodes[side1j].Edges - 1; i++) {
j = Nodes[side1j]..edge(i);
if (j == edge_side1 || Edges[j]..oneway == 0 || Edges[j].roadtype != roadtype || Edges[j]..node1 != side1j) { //*TODO:** goto found: GoTo lSkipEdgeSide1; }
//skip same edge_side1, 2-ways, other road types and directed from this node outside
dist_t = distanceBetweenSegments(j, edge_side2);
//'skip too far edges
if (dist_t > joinDistance) { //*TODO:** goto found: GoTo lSkipEdgeSide1; }
angl = cosAngleBetweenEdges(j, edge_side2);
//'remember edge with min angle
if (angl < angl_min) { angl_min = angl: angl_min_edge == j; }
//*TODO:** label found: lSkipEdgeSide1:;
}
//'mark edge as participating in joining
Edges[edge_side1]..mark = 2;
//'add edge to chain (depending on pass number)
addTW(edge_side1, 1 - passNumber);
if (angl_min_edge == -1) {
//no edge found - end of chain
//'mark last edge of side2
Edges[edge_side2]..mark = 2;
//'and add it to chain
addTW(edge_side2, passNumber);
//*TODO:** goto found: GoTo lChainEnds;
}
edge_side1 = angl_min_edge;
//'update i and j nodes of side
side1i = side1j;
side1j = Edges[edge_side1]..node2;
if (Edges[edge_side1]..mark == 2) {
//found marked edge, means, that we found cycle
side1circled = 1;
}
if (side2j == side1j) {
//found marked edge, this means that we found cycle
//'mark both last edges as participating in joining
Edges[edge_side2]..mark = 2;
Edges[edge_side1]..mark = 2;
//'add them to chains
addTW(edge_side2, passNumber);
addTW(edge_side1, 1 - passNumber);
//*TODO:** goto found: GoTo lChainEnds;
}
}
//middle line projection vector
//TODO: fix (not safe to 180/-180 edge)
dx = Nodes[side1j]..lat - Nodes[side1i]..lat + Nodes[side2j]..lat - Nodes[side2i]..lat;
dy = Nodes[side1j]..lon - Nodes[side1i]..lon + Nodes[side2j]..lon - Nodes[side2i]..lon;
px = (Nodes[side1i]..lat + Nodes[side2i]..lat) * 0.5;
py = (Nodes[side1i]..lon + Nodes[side2i]..lon) * 0.5;
dd = 1 / (dx * dx + dy * dy);
//'remember current chain len
checkchain = ChainNum;
if (calc_side == 2) {
//project j node from side2 to middle line
dist_t = (Nodes[side2j]..lat - px) * dx + (Nodes[side2j]..lon - py) * dy;
addChain(side2j);
//'old node will collapse to this new one
Nodes[side2j]..mark = NodesNum;
}
else {
//project j node from side1 to middle line
dist_t = (Nodes[side1j]..lat - px) * dx + (Nodes[side1j]..lon - py) * dy;
addChain(side1j);
//'old node will collapse to this new one
Nodes[side1j]..mark = NodesNum;
}
//create new node
Nodes[NodesNum].Edges = 0;
Nodes[NodesNum]..nodeID = -1;
Nodes[NodesNum]..mark = -1;
Nodes[NodesNum]..lat = px + dist_t * dx * dd;
Nodes[NodesNum]..lon = py + dist_t * dy * dd;
//reproject prev node into current middle line ("ChainNum - 2" because ChainNum were updated above by AddChain)
j = Nodes[Chain[ChainNum - 2]]..mark;
dist_t = (Nodes[j]..lat - px) * dx + (Nodes[j]..lon - py) * dy;
Nodes[j]..lat = px + dist_t * dx * dd;
Nodes[j]..lon = py + dist_t * dy * dd;
if (distance(j, NodesNum) < combineDistance) {
//Distance from new node to prev-one is too small, collapse node with prev-one
//TODO(?): averaging coordinates?
if (calc_side == 2) {
Nodes[side2j]..mark = j;
}
else {
Nodes[side1j]..mark = j;
}
//do not call AddNode -> new node will die
}
else {
addNode();
//'fix order of nodes in chain
fixChainOrder(checkchain);
}
//'both sides circled - whole road is a loop
if (side1circled > 0 && side2circled > 0) { //*TODO:** goto found: GoTo lFoundCycle; }
//'proceed to searching next edge
//*TODO:** goto found: GoTo lKeepGoing;
//*TODO:** label found: lChainEnds:;
//Node there is chance, that circular way will be not closed from one of sides
//Algorithm does not handle this case, it should collapse during juctions collapsing
return;
//*TODO:** label found: lFoundCycle:;
//handle cycle road
//find all nodes from end of chain which is present in chain two times
//remove all of them, except last one
//in good cases last node should be same as first node
//TODO: what if not?
for (i = ChainNum - 1; i <= 0; i--) {
for (j = 0; j <= i - 1; j++) {
if (Chain[i] == Chain[j]) { //*TODO:** goto found: GoTo lFound; }
}
//not found
//'keep this node (which is one time in chain) and next one (which is two times)
ChainNum = i + 2;
//*TODO:** goto found: GoTo lExit;
//*TODO:** label found: lFound:;
}
//*TODO:** label found: lExit:;
}
//Fix order of nodes in Chain
//Fixing is needed when last node is not new arrow-head of GoByTwoWays algorithm (ex. several short edges of one side, but long edge of other side)
public static void fixChainOrder(int checkindex) {
Long, i2 = null; i1 As Long, i0 As Long, k As Long
double p = 0;
//'2 or less nodes in chain, nothing to fix
if (checkindex < 2) { return; }
//'last new node
i2 = Nodes[Chain[checkindex]]..mark;
//'exit in case of probles
if (i2 < 0) { return; }
//'prev new node
i1 = Nodes[Chain[checkindex - 1]]..mark;
if (i1 < 0) { return; }
//'prev-prev new node
i0 = Nodes[Chain[checkindex - 2]]..mark;
if (i0 < 0) { return; }
k = 3;
//if prev-prev new nodes is combined with prev new node - find diffent node backward
while (i0 == i1) {
//'reach Chain(0)
if (checkindex < k) { return; }
i0 = Nodes[Chain[checkindex - k]]..mark;
k = k + 1;
}
//Scalar multiplication of vectors i0->i1 and i1->i2
p = (Nodes[i2]..lat - Nodes[i1]..lat) * (Nodes[i1]..lat - Nodes[i0]..lat) + (Nodes[i2]..lon - Nodes[i1]..lon) * (Nodes[i1]..lon - Nodes[i0]..lon);
if (p < 0) {
//vectors are contradirectional -> swap
i0 = Chain[checkindex];
Chain[checkindex] = Chain[checkindex - 1];
Chain[checkindex - 1] == i0;
//check last new node on new place
fixChainOrder(checkindex - 1);
}
}
//Build cluster index
//Cluster index allow to quickly find nodes in specific bbox
//Cluster index is collections of nodes chains, where starts can be selected from coordinates
//and continuation - by indexes in chains
//Flags: 1 - only update from ClustersIndexedNodes to NodesNum (0 - full re/build)
public static void buildNodeClusterIndex(int flags) {
Long, i = null; j As Long, k As Long
int x = 0;
int y = 0;
if ((flags && 1) != 0) {
//Only update
//TODO(?): remove chain from deleted nodes
G.redimPreserve(ClustersChain, NodesNum);
//*TODO:** goto found: GoTo lClustering;
}
//calc overall bbox
bbox wholeBbox = null;
wholeBbox..lat_max = -360;
wholeBbox..lat_min = 360;
wholeBbox..lon_max = -360;
wholeBbox..lon_min = 360;
for (i = 0; i <= NodesNum - 1; i++) {
//'skip deleted nodes
if (Nodes[i]..nodeID != MARK_NODEID_DELETED) {
if (Nodes[i]..lat < wholeBbox..lat_min) { wholeBbox..lat_min = Nodes[i]..lat; }
if (Nodes[i]..lat > wholeBbox..lat_max) { wholeBbox..lat_max = Nodes[i]..lat; }
if (Nodes[i]..lon < wholeBbox..lon_min) { wholeBbox..lon_min = Nodes[i]..lon; }
if (Nodes[i]..lon > wholeBbox..lon_max) { wholeBbox..lon_max = Nodes[i]..lon; }
}
}
ClustersIndexedNodes = 0;
//'no nodes at all or something wrong
if (wholeBbox..lat_max < wholeBbox..lat_min || wholeBbox..lon_max < wholeBbox..lon_min) { return; }
//calc number of clusters
ClustersLatNum = 1 + (wholeBbox..lat_max - wholeBbox..lat_min) / CLUSTER_SIZE;
ClustersLonNum = 1 + (wholeBbox..lon_max - wholeBbox..lon_min) / CLUSTER_SIZE;
//'starts of chains
G.redim(ClustersFirst, ClustersLatNum * ClustersLonNum);
//'ends of chains (for updating)
G.redim(ClustersLast, ClustersLatNum * ClustersLonNum);
//'whole chain
G.redim(ClustersChain, NodesNum);
//'edge of overall bbox
ClustersLat0 = wholeBbox..lat_min;
ClustersLon0 = wholeBbox..lon_min;
for (i = 0; i <= ClustersLatNum * ClustersLonNum - 1; i++) {
//'no nodes in cluster yet
ClustersFirst[i] = -1;
ClustersLast[i] = -1;
}
ClustersIndexedNodes = 0;
//*TODO:** label found: lClustering:;
for (i = ClustersIndexedNodes; i <= NodesNum - 1; i++) {
if (Nodes[i]..nodeID != MARK_NODEID_DELETED) {
//get cluster from lat/lon
x = (Nodes[i]..lat - ClustersLat0) / CLUSTER_SIZE;
y = (Nodes[i]..lon - ClustersLon0) / CLUSTER_SIZE;
j = x + y * ClustersLatNum;
k = ClustersLast[j];
if (k == -1) {
//first index in chain of this cluster
ClustersFirst[j] = i;
}
else {
//continuing chain
ClustersChain[k] = i;
}
//'this is last node in chain
ClustersChain[i] = -1;
ClustersLast[j] = i;
}
}
//'last node in cluster index
ClustersIndexedNodes = NodesNum;
}
//Find node in bbox by using cluster index
//Flags: 1 - next (0 - first)
public static int getNodeInBboxByCluster(bbox box1, int flags) {
int _rtn = 0;
Long, i = null; j As Long, k As Long
Long, x = null; y As Long
Long, x1 = null; x2 As Long, y1 As Long, y2 As Long
if ((flags && 1) == 0) {
//first node needed
//get coordinates of all needed clusters
x1 = (box1..lat_min - ClustersLat0) / CLUSTER_SIZE;
x2 = (box1..lat_max - ClustersLat0) / CLUSTER_SIZE;
y1 = (box1..lon_min - ClustersLon0) / CLUSTER_SIZE;
y2 = (box1..lon_max - ClustersLon0) / CLUSTER_SIZE;
//'store bbox for next searches
ClustersFindLastBbox = box1;
x = x1;
y = y1;
//*TODO:** goto found: GoTo lCheckFirst;
}
if (ClustersFindLastNode == -1) {
//Last time nothing found - nothing to do further
_rtn = -1;
//*TODO:** goto found: GoTo lExit;
}
//get coordinates of all needed clusters
x1 = (ClustersFindLastBbox..lat_min - ClustersLat0) / CLUSTER_SIZE;
x2 = (ClustersFindLastBbox..lat_max - ClustersLat0) / CLUSTER_SIZE;
y1 = (ClustersFindLastBbox..lon_min - ClustersLon0) / CLUSTER_SIZE;
y2 = (ClustersFindLastBbox..lon_max - ClustersLon0) / CLUSTER_SIZE;
//get coordinates of last used cluster
x = ClustersFindLastCluster Mod ClustersLatNum;
y = (ClustersFindLastCluster - x) \ ClustersLatNum;
//*TODO:** label found: lNextNode:;
//'get node from chain
k = ClustersChain[ClustersFindLastNode];
if (k != -1) {
//not end of chain
//*TODO:** label found: lCheckNode:;
//'keep as last result
ClustersFindLastNode = k;
//'deleted node - find next
if (Nodes[k]..nodeID == MARK_NODEID_DELETED) { //*TODO:** goto found: GoTo lNextNode; }
//'node outside desired bbox - find next
if (Nodes[k]..lat < ClustersFindLastBbox..lat_min || Nodes[k]..lat > ClustersFindLastBbox..lat_max) { //*TODO:** goto found: GoTo lNextNode; }
if (Nodes[k]..lon < ClustersFindLastBbox..lon_min || Nodes[k]..lon > ClustersFindLastBbox..lon_max) { //*TODO:** goto found: GoTo lNextNode; }
//'OK, found
_rtn = k;
//*TODO:** goto found: GoTo lExit;
}
//end of chain -> last node in cluster
//*TODO:** label found: lNextCluster:;
//proceed to next cluster
x = x + 1;
//'next line of cluster
if (x > x2) { y = y + 1: x == x1; }
if (y > y2) {
//last cluster - no nodes
//'nothing found
_rtn = -1;
//'nothing will be found next time
ClustersFindLastNode = -1;
ClustersFindLastCluster = -1;
//*TODO:** goto found: GoTo lExit;
}
//*TODO:** label found: lCheckFirst:;
//get first node of cluster
j = x + y * ClustersLatNum;
k = ClustersFirst[j];
//'no first node - skip cluster
if (k == -1) { //*TODO:** goto found: GoTo lNextCluster; }
ClustersFindLastCluster = j;
//'there is first node - check it
//*TODO:** goto found: GoTo lCheckNode;
//*TODO:** label found: lExit:;
return _rtn;
}
//Remove all labels stats from memory
public static void resetLabelStats() {
LabelStatsNum = 0;
}
//Add label to label stats
public static void addLabelStat0(String text) {
//Call AddLabelStat1(Text) 'majoritary version
//'combinatory version
addLabelStat2(text);
}
public static Object getLabelByStats(int flags) {
//GetLabelByStats = GetLabelByStats1(Text) 'majoritary version
//'combinatory version
return getLabelByStats2(0);
}
//Add label completely (for majoritary calc and so on)
public static void addLabelStat1(String text) {
int i = 0;
//'skip empty strings
if (text.length() < 1) { return; }
for (i = 0; i <= LabelStatsNum - 1; i++) {
if (LabelStats[i].text.equals(text)) {
//already present - increment count
LabelStats[i]..count = LabelStats[i]..count + 1;
return;
}
}
//not present - add
LabelStats[LabelStatsNum].text = text;
LabelStats[LabelStatsNum]..count = 1;
LabelStatsNum = LabelStatsNum + 1;
if (LabelStatsNum >= LabelStatsAlloc) {
//realloc if needed
LabelStatsAlloc = LabelStatsAlloc * 2;
G.redimPreserve(LabelStats, LabelStatsAlloc);
}
}
//Add label by parts (for combinatory calc and so on)
public static void addLabelStat2(String text) {
int i = 0;
String[] marks() = null;
if (text.length() < 1) { return; }
//'split string by delimiter into set of strings
marks = Split(text, ",");
for (i = 0; i <= marks.length; i++) {
addLabelStat1(marks[i]);
}
}
//Get label of road from stats, combinatory version
//Flags: 0 - default
public static String getLabelByStats2(int flags) {
String _rtn = "";
int i = 0;
_rtn = "";
//'no labels in stats
if (LabelStatsNum == 0) { return _rtn; }
//combine all labels from stats
_rtn = LabelStats[0]..text;
for (i = 1; i <= LabelStatsNum - 1; i++) {
_rtn = getLabelByStats2() + "," + LabelStats[i]..text;
}
return _rtn;
}
//
//Get label of road from stats, majoritary version
//Flags: 0 - default
public static String getLabelByStats1(int flags) {
String _rtn = "";
int i = 0;
Long, max_count = null; max_len As Long, max_index As Long
//select label with max count and max len (amoung max count)
max_count = -1;
max_len = -1;
max_index = -1;
for (i = 0; i <= LabelStatsNum - 1; i++) {
if (LabelStats[i]..count > max_count) {
//max count
max_count = LabelStats[i]..count;
max_index = i;
max_len = LabelStats[i]..text.length();
}
else if (LabelStats[i]..count == max_count) {
if (LabelStats[i]..text.length() > max_len) {
//max len amoung max count
max_count = LabelStats[i]..count;
max_index = i;
max_len = LabelStats[i]..text.length();
}
}
}
if (max_index > -1) {
_rtn = LabelStats[max_index]..text;
}
else {
//nothing found
_rtn = "";
}
return _rtn;
}
//Add edge into one of TW arrays
//side: 0 - into TWforw, 1 - into TWback
public static Object addTW(int edge1, int side) {
if (side == 1) {
TWback[TWbackNum] = edge1;
TWbackNum = TWbackNum + 1;
if (TWbackNum >= TWalloc) { //*TODO:** goto found: GoTo lRealloc; }
else {
TWforw[TWforwNum] = edge1;
TWforwNum = TWforwNum + 1;
if (TWforwNum >= TWalloc) {
//*TODO:** label found: lRealloc:;
//realloc if needed
TWalloc = TWalloc * 2;
G.redimPreserve(TWforw, TWalloc);
G.redimPreserve(TWback, TWalloc);
}
}
}
//Start point
public static void optimizeRouting(String inputFile) {
String outFile = "";
//Dim OutFile2 As String 'temp file for debug
double time1 = 0;
//'nothing to do
if (inputFile.isEmpty()) { return; }
//'output file
outFile = inputFile + "_opt.mp";
//OutFile2 = InputFile + "_p.mp" 'output2 - for intermediate results
//'start measure time
time1 = Timer;
//Init module (all arrays)
init();
//Load data from file
load_MP(inputFile);
DoEvents;
//Join nodes by NodeID
joinNodesByID();
DoEvents;
//Join two way roads into bidirectional ways
joinDirections3(70, -0.996, -0.95, 100, 2);
//70 metres between directions (Ex: Universitetskii pr, Moscow - 68m)
//-0.996 -> (175, 180) degrees for start contradirectional check
//-0.95 -> (161.8, 180) degrees for further contradirectional checks
//100 metres min two way road
//2 metres for joining nodes into one
DoEvents;
filterVoidEdges();
DoEvents;
//Call Save_MP(OutFile2) 'temp file for debug
//DoEvents
//Optimize all roads by (Ramer)DouglasPeucker algorithm with limiting edge len
douglasPeucker_total_split(5, 100);
//Epsilon = 5 metres
//Max edge - 100 metres
DoEvents;
collapseJunctions2(1000, 1200, 0.13);
//Slide allowed up to 1000 metres
//Max junction loop is 1200 metres
//0.13 -> ~ 7.46 degress
DoEvents;
filterVoidEdges();
DoEvents;
//Optimize all roads by (Ramer)DouglasPeucker algorithm
douglasPeucker_total(5);
//Epsilon = 5 metres
DoEvents;
//Join edges with very acute angle into one
joinAcute(100, 3);
//100 metres for joining nodes
//AcuteKoeff = 3 => 18.4 degrees
DoEvents;
//Optimize all roads by (Ramer)DouglasPeucker algorithm
douglasPeucker_total(5);
//Epsilon = 5 metres
DoEvents;
//Save result
save_MP_2(outFile);
//'display timing
Form1.Caption = "Done " + Format(Timer - time1, "0.00") + " s";
}
}
public class node {
public Double lat;//'Latitude
public Double lon;//'Longitude
public Long nodeID;//'NodeID from source .mp, -1 - not set, -2 - node killed
public Long[20] edge;//'all edges (values - indexes in Edges array)
public Long edges;//'number of edges, -1 means "not counted"
public Long mark;//'internal marker for all-network algo-s
public Double temp_dist;//'internal value for for all-network algo-s
}
public class edge {
public Long node1;//'first node (index in Nodes array)
public Long node2;//'second node
public Byte roadtype;//'roadtype, see HIGHWAY_ consts
public Byte oneway;//'0 - no, 1 - yes ( goes from node1 to node2 )
public Integer mark;//'internal marker for all-network algo-s
public Byte speed;//'speed class (in .mp terms)
public String label;//'label of road (only ref= values currently, not name= )
}
public class aimedge {
public Double lat1;
public Double lon1;
public Double lat2;
public Double lon2;
public Double a;//'matrix equation elements
public Double b;
public Double c;
public Double d;
}
public class bbox {
public Double lat_min;
public Double lat_max;
public Double lon_min;
public Double lon_max;
}
public class LabelStat {
public String text;
public Long count;
}Offline