Изогнутые двухточечные «карты маршрутов»

39

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

Пути полета

В PostGIS, есть ли реализация ST_MakeLine, которая позволила бы вам указать количество кривой, которая будет использоваться при соединении 2 точек?

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

RyanDalton
источник
Кто-нибудь знает какие-нибудь хорошие реализации этого? Примеры или еще что?
Марк Боулдер

Ответы:

26

Создание больших кругов может дать вам желаемый эффект.

Может быть, что-то вроде того, что обсуждается на http://lists.osgeo.org/pipermail/postgis-users/2008-F February/018620.html

Обновить:

Я развил эту идею в «Визуализации глобальных связей» . Это чисто PostGIS-решение, использующее перепроектирование для создания дуг.

SELECT ST_Transform(
  ST_Segmentize(
    ST_MakeLine(
      ST_Transform(a.the_geom, 953027),
      ST_Transform(b.the_geom, 953027)
    ), 
  100000), 
4326)

(Определение CRS для 953027 можно найти здесь: http://spatialreference.org/ref/esri/53027/ )

введите описание изображения здесь

Подземье
источник
4
Мне нравится идея, хотя с большими кругами проблема, с которой вы сталкиваетесь, заключается в том, что на более коротких расстояниях вы все равно будете иметь в целом прямую линию. Я хотел бы иметь возможность контролировать количество дуги, которую я помещаю в линию (т.е. длина дуги = расстояние * 2).
RyanDalton
1
Вот хороший пример проблемы с использованием просто больших кругов: gc.kls2.com/cgi-bin/…
RyanDalton
1
После некоторых дополнительных исследований я обнаружил, что этот пост может быть полезен для помощи этому методу. mail-archive.com/postgis-users@postgis.refractions.net/…
RyanDalton
Для будущего читателя я подумал, что я просто пойду и сошлюсь на недавнюю запись в блоге @ underdark, посвященную этой теме. underdark.wordpress.com/2011/08/20/…
RyanDalton
Замечательно!! Используется в моем проекте для рисования линий между пользовательскими регистрациями и местами проведения мероприятий, взятыми из Forsquare
Lorenzo Barbagli
24

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

Вот одно из решений (среди множества возможных). Давайте рассмотрим все дуги, происходящие из общего происхождения. Здесь дуги самые многолюдные. Чтобы разделить их наилучшим образом, давайте расположим их так, чтобы они распределялись под равными углами . Это проблема, если мы рисуем отрезки прямых линий от источника до пунктов назначения, потому что обычно в разных направлениях будут кластеры пунктов назначения. Давайте использовать нашу свободу, чтобы изгибать дуги, чтобы расположить исходящие углы как можно более равномерно.

Для простоты давайте используем круговые дуги на карте. Естественной мерой «изгиба» в дуге от точки y к точке x является разность между ее направлением в y и подшипником непосредственно от y до x . Такая дуга является сектором круга, на котором лежат оба y и x ; элементарная геометрия показывает, что угол изгиба равен половине включенного угла в дуге.

Для описания алгоритма нам понадобится немного больше обозначений. Пусть y будет исходной точкой (как спроецировано на карту), и пусть x_1 , x_2 , ..., x_n будут точками назначения. Определите a_i как отношение от y к x_i , i = 1, 2, ..., n .

В качестве предварительного шага предположим, что подшипники (все от 0 до 360 градусов) расположены в порядке возрастания: для этого необходимо рассчитать подшипники и затем отсортировать их; оба простые задачи.

В идеале мы хотели бы, чтобы подшипники дуг равнялись 360 / n , 2 * 360 / n и т. Д. Относительно некоторого начального подшипника. Таким образом, различия между требуемыми подшипниками и действительными подшипниками равны i * 360 / n - a_i плюс начальный подшипник, a0 . Наибольшая разница - это максимум этих n различий, а наименьшая разница - их минимум. Давайте установим a0 на полпути между максимумом и минимумом; это хороший кандидат на пусковой подшипник, поскольку он сводит к минимуму максимальный изгиб, который может произойти . Следовательно, определить

b_i = i * 360 / n - a0 - a_i:

это изгиб, чтобы использовать .

Элементарной геометрией является рисование дуги окружности от y до x, которая составляет угол 2 b_i, поэтому я пропущу детали и перейду прямо к примеру. Вот иллюстрации решений для 64, 16 и 4 случайных точек, помещенных в прямоугольную карту

альтернативный текст

альтернативный текст

альтернативный текст

Как вы можете видеть, решения, кажется, становятся лучше с увеличением количества пунктов назначения. Решение для n = 4 ясно показывает, как подшипники расположены на одинаковом расстоянии, поскольку в этом случае расстояние равно 360/4 = 90 градусов, и очевидно, что расстояние точно достигнуто.

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

Алгоритм также имеет преимущество простоты: самая сложная часть состоит в сортировке пунктов назначения в соответствии с их ориентирами.


кодирование

Я не знаю PostGIS, но, возможно, код, который я использовал для рисования примеров, может служить руководством для реализации этого алгоритма в PostGIS (или любой другой ГИС).

Считайте следующее псевдокодом (но Mathematica выполнит его :-). (Если бы этот сайт поддерживал TeX, как это делают математика, статистика и TCS, я мог бы сделать это намного более читабельным.) Нотация включает в себя:

  • Имена переменных и функций чувствительны к регистру.
  • [Альфа] - это строчный греческий символ. ([Пи] имеет значение, которое, как вы думаете, должно иметь.)
  • x [[i]] является элементом i массива x (индексируется начиная с 1).
  • f [a, b] применяет функцию f к аргументам a и b. Функции в собственном случае, такие как «Min» и «Table», определяются системой; функции с начальной строчной буквой, такие как «angles» и «offset», определяются пользователем. Комментарии объясняют любые неясные функции системы (например, «Arg»).
  • Таблица [f [i], {i, 1, n}] создает массив {f [1], f [2], ..., f [n]}.
  • Круг [o, r, {a, b}] создает дугу окружности с центром в o радиуса r от угла a к углу b (оба в радианах против часовой стрелки от восточного направления).
  • Ordering [x] возвращает массив индексов отсортированных элементов x. x [[Ordering [x]]] - отсортированная версия x. Если длина y равна x, y [[Ordering [x]]] сортирует y параллельно с x.

Исполняемая часть кода, к счастью, короткая - менее 20 строк - потому что более половины ее составляют либо декларативные накладные расходы, либо комментарии.

Нарисуй карту

zэто список направлений и yявляется источником.

circleMap[z_List, y_] := 
Module[{\[Alpha] = angles[y,z], \[Beta], \[Delta], n},
    (* Sort the destinations by bearing *)
    \[Beta] = Ordering[\[Alpha]];
    x = z[[\[Beta] ]]; (* Destinations, sorted by bearing from y *)
    \[Alpha] = \[Alpha][[\[Beta]]]; (* Bearings, in sorted order *)
    \[Delta] = offset[\[Alpha]];
    n = Length[\[Alpha]];
    Graphics[{(* Draw the lines *)
        Gray, Table[circle[y, x[[i]],2 \[Pi] i / n + \[Delta] - \[Alpha][[i]]], 
             {i, 1, Length[\[Alpha]]}],
        (* Draw the destination points *)
        Red, PointSize[0.02], Table[Point[u], {u, x}]
    }]
]

Создайте дугу окружности от точки xк точке, yначиная под углом \[Beta]относительно подшипника x -> y.

circle[x_, y_, \[Beta]_] /; -\[Pi] < \[Beta] < \[Pi] := 
Module[{v,  \[Rho], r, o, \[Theta], sign},
    If[\[Beta]==0, Return[Line[{x,y}]]];

    (* Obtain the vector from x to y in polar coordinates. *)
    v = y - x; (* Vector from x to y *)
    \[Rho] = Norm[v]; (* Length of v *)
    \[Theta] = Arg[Complex @@ v]; (* Bearing from x to y *)

    (* Compute the radius and center of the circle.*)
    r = \[Rho] / (2 Sin[\[Beta]]); (* Circle radius, up to sign *)
    If[r < 0, sign = \[Pi], sign = 0];
    o = (x+y)/2 + (r/\[Rho]) Cos[\[Beta]]{v[[2]], -v[[1]]}; (* Circle center *)

    (* Create a sector of the circle. *)
    Circle[o, Abs[r], {\[Pi]/2 - \[Beta] + \[Theta] + sign, \[Pi] /2 + \[Beta] + \[Theta] + sign}]
]

Вычислить подшипники от начала координат до списка точек.

angles[origin_, x_] := Arg[Complex@@(#-origin)] & /@ x;

Вычислите средние значения остатков набора подшипников.

xэто список подшипников в отсортированном порядке. В идеале, x [[i]] ~ 2 [Pi] i / n.

offset[x_List] :=
Module[
    {n = Length[x], y},
    (* Compute the residuals. *)
    y = Table[x[[i]] - 2 \[Pi] i / n, {i, 1, n}];
    (* Return their midrange. *)
    (Max[y] + Min[y])/2
]
Whuber
источник
Я должен упомянуть, что это решение предполагает, что пункты назначения более или менее окружают источник. Когда это не так, вся идея (одинаково расположенных подшипников) не является хорошей. Но это может быть легко исправлено путем введения некоторых поддельных пунктов назначения в угловые промежутки и последующего удаления этих пунктов назначения (и их дуг). Этот процесс может быть автоматизирован путем вычисления среднего расстояния между подшипниками и его использования для определения больших зазоров и т . Д.
whuber
Приятная графика. Интересно, используют ли авиакомпании автоматизированный инструмент, когда они составляют карты маршрутов, показанные в конце их бортового журнала.
Кирк Куйкендалл
1
@Kirk Они, вероятно, платят кому-то, чтобы сделать картографию вручную :-). Этот вопрос меня вдохновил, чтобы понять, может ли простой подход создать достаточно хорошую графику. Ответ выглядит многообещающим. Эти графики, кстати, были созданы Mathematica 8 с использованием примитивов Circle и Point и небольшой векторной арифметики для нахождения центров окружностей.
whuber
Мне нравится результат, который вы показали, и мне это путь. Я буду честен, хотя я считаю себя техническим, но я немного потерял в формуле, которую вы дали, и поэтому превращение этого в код PostGIS становится практически невозможным. У кого-нибудь есть идеи о том, как перевести концепцию Whuber в работоспособный код? Я постараюсь просмотреть и попробовать, но помощь будет принята с благодарностью.
RyanDalton
@ whuber - Спасибо за обновленный псевдокод. Посмотрим, сможем ли мы реализовать это в PostGIS.
RyanDalton
5

Попробуйте ST_CurveToLine

Что-то вроде например:

SELECT ST_CurveToLine('CIRCULARSTRING(1 1,5 3,10 1)'::geometry) as the_geom;

Вы можете визуализировать это, скопировав запрос в текстовое поле и нажав Map1 на http://www.postgisonline.org/map.php

Никлас Авен
источник
Я закончил тем, что попробовал это изогнуть ряд "двухточечных" линий.
Брент Эдвардс
3

Я бы подумал, что вы просто захотите свернуть свою собственную ломаную с какой-нибудь векторной математикой, http://en.wikipedia.org/wiki/B%C3%A9zier_curve , или если ваш gis имеет интерфейс ICurve .

Стив
источник
3

Я закончил тем, что попытался изогнуть набор «двухточечных» строк, используя функцию ST_CurveToLine, как предложено @Nicklas Avén.

Я передал следующие 3 набора координат в функцию ST_OffsetCurve:

  1. Начало оригинальной линии
  2. Средняя точка смещения линии, параллельной исходной линии
  3. Конец оригинальной строки

Я использовал функцию ST_OffsetCurve для вычисления смещения - 1/10-й длины исходной линии в моем примере.

Вот SQL, который я использовал для генерации кривых линий из исходных прямых линий:

    ST_CurveToLine('CIRCULARSTRING(' || st_x(st_startpoint(the_geom)) || ' ' || st_y(st_startpoint(the_geom)) || ', ' || st_x(st_centroid(ST_OffsetCurve(the_geom, st_length(the_geom)/10, 'quad_segs=4 join=bevel'))) || ' ' || st_y(st_centroid(ST_OffsetCurve(the_geom, st_length(the_geom)/10, 'quad_segs=4 join=bevel'))) || ', ' || st_x(st_endpoint(the_geom)) || ' ' ||  st_y(st_endpoint(the_geom)) || ')') AS the_curved_geom
Брент Эдвардс
источник
Действительно полезно, но по какой-то причине результат не уважает мой srid. Есть идеи почему?
DMS02
Не могли бы вы предоставить более подробную информацию - srid входной геометрии, srid вывода отсутствует, отличается, сгенерированы ошибки (какие приложения - QGIS, PostgreSQL).
Брент Эдвардс
Таблица, в которую я хочу вставить результирующие изогнутые линии, имеет ограничение forcece_srid_geom. Когда я выполняю запрос, я получаю сообщение о том, что этот запрос нарушает это ограничение. С таблицей без этого ограничения она работает, но затем при добавлении ее в QGIS она указывается с srid 0. Мой запрос: INSERT INTO test (the_curved_geom) SELECT [здесь ваш SQL] FROM строк
DMS02
Попробуйте запустить функции postgis.net/docs/ST_GeometryType.html и postgis.net/docs/ST_SRID.html в столбце геометрии (the_curved_geom) и проверьте, есть ли конфликты с вашей тестовой таблицей иорачиванием_srid_geom. Если это так, вы можете преобразовать геометрию / srid по мере необходимости или изменить свою тестовую таблицу / ограничение.
Брент Эдвардс