автоматическое разбиение каталога перевалов на районы

[slazav]

Поигрался сейчас в такую штуку:

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

Действую так:
* Начинаю с некоторой точки, создаю вокруг нее маленький прямоугольник
* Пытаюсь добавить в этот прямоугольник другие точки, расширяя его. Точку добавляю, только если прямоугольник расширяется не более чем на значение параметра D по ширине или высоте.
* Повторяю, пока точки не перестанут добавляться.
* Для оставшихся точек тем же способом создаю другие прямоугольники, пока точек не останется...

(Все вычисление - в градусах долготы и широты).

Картинка 1. Зависимость числа и суммарной площади полученных прямоугольников от параметра D.



Видно, что разумное значение для размера нашего типичного горного района -- около 0.5 градусов, а таких районов получается .всего 20 :)

Далее произвожу разбиение с параметром D=0.5

Таблица 1. Координаты прямоугольника (WxH+X0+Y0),
его площадь, число перевалов в нем.

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

# rectangle in lon-lat coords          area     N
2.200856x3.176794+71.512443+36.818888  6.991666 411 # Памир
4.545794x1.417788+40.188666+42.423602  6.444971 139 # Кавказ
2.431046x0.874564+67.780538+38.703715  2.126105 341 # Фаны
1.449383x1.136165+98.656750+51.732808  1.646739 21  # Большой Саян
1.282654x1.114382+77.672717+41.216499  1.429367 182 # Терскей и к.
1.711986x0.628921+95.203309+53.705504  1.076704 24  # Центральный Саян
1.140615x0.352878+110.597333+56.128995 0.402498 51  # Верхнеангарский хр.
1.209365x0.291400+101.279992+51.785148 0.352409 181 # Тунки
0.708838x0.356418+76.751574+42.799969  0.252643 107
0.484074x0.502869+87.402777+49.739632  0.243426 14
0.768719x0.199744+74.167777+42.401757  0.153547 153
0.696356x0.194832+33.285555+67.676129  0.135673 33  # Хибины
0.685002x0.165891+85.924443+49.795082  0.113636 7
0.488318x0.159322+72.716661+41.466018  0.077800 8
0.212530x0.350015+35.001582+37.568066  0.074389 16  # Турция
0.115835x0.216504+89.550555+49.785277  0.025079 10
0.123752x0.090872+79.316109+44.870599  0.011246 8
0.000002x0.000002+79.663693+42.234999  0.000000 1
0.000002x0.000002+77.672716+40.336982  0.000000 1
0.000002x0.000002+100.690104+51.783240 0.000000 1


Картинка 2. Эти самые 20 районов на карте (совсем маленькие прямоугольники специально увеличены):
[/code]

[Alexander Purikov]

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

[slazav]

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

Это то же самое, что прогонять алгоритм по всем перевалам, но с меньшим параметром...

Вот, например, как Кавказ распадается при D=0.1 гр.:


У меня скорее была идея, имея все привязанные топографические карты на нужные места, автоматически делать эти 20 картинок с актуальным состоянием каталога. Если, я хочу, например, километровки, то размер районов должен быть маленьким... Вот я их и подбираю :)