Построение многоугольника над достижимой областью

10

В настоящее время я работаю в области изохрон и базовых алгоритмов. В настоящее время возникают проблемы не в расчете самой изохроны, а в визуализации результатов.
Результатом моего изохронного алгоритма являются точки и ребра. На самом деле у меня есть работающее решение, но для 3873 ребер и для 1529 узлов все, кажется, занимает вечность (около 2,0 секунд на моем ноутбуке Lenovo T440s, который содержит процессор Core i7 2015 года и довольно быстрый SSD). Вместо секунд я хочу что-то более похожее на msec :-).

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

Но подождите ... обо всем по порядку!
Вот визуализация ребер, которые я Результат расчета изохроны (существующий каркас из строк) являю результатом вычисления моей изохроны: Эти ребра хранятся в таблице базы данных PostGIS и являются простыми линейными строками.

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

В настоящее время я использую этот запрос:

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_MakePolygon(ST_ExteriorRing(ST_GeometryN(segments, generate_series(1, ST_NumGeometries(segments))))) AS polygons FROM (
        SELECT ST_Union(ST_Buffer("GEOMETRY", 20, 'quad_segs=2')) AS segments FROM my_edges AS a
    ) AS b
) AS c

Я уже провел некоторые эксперименты и прочитал много документации, но просто не могу найти лучшего решения.
На мой взгляд, большая проблема заключается в использовании ST_Union (как указано в документации, эта функция может быть медленной). Очень интересно то, что замена его на ST_Collect, кажется, замедляет вычисление ST_Buffer, так что в целом следующий запрос занимает больше времени, хотя он не заполняет области между краями (он только создает буфер вокруг строк ):

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_Buffer(ST_Collect(ST_LineMerge("GEOMETRY")), 20, 'quad_segs=2') AS polygons FROM my_edges AS a
) AS b

Это занимает около 3,8 секунды в моей системе (так почти вдвое больше). Мой первый вывод из этого небольшого теста состоит в том, что ST_Buffer неожиданно замедляется, когда дело доходит до MultiLineStrings (даже медленнее, чем при создании буферов для каждой строки и объединении буферов - что на мой взгляд просто странно)

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

Есть ли лучший способ создать область, показанную в PostGIS? Может также использовать java-код (jts) или код javascript на стороне клиента (jsts)? Фактически, я мог бы потерять некоторые детали, пока области, показанные в моем результате, остаются разделенными, и вычисление становится (намного) быстрее.

Николаус Крисмер
источник
Можете ли вы не просто использовать ST_Exteriorring (ST_Dump (ST_Union (ST_Buffer (geom, ....))). Geom, видящий как что-либо буферизованное, будет в любом случае многоугольником, а ST_Union соединит все пересекающиеся геометрии, поэтому нет необходимости в MakePolygon или GeometryN. Возможно, вам понадобится проверить строки строк, которые иногда появляются в результате ST_Union после буфера, но это легко сделать с помощью ST_GeometryType (geom). Что касается использования Java или jsts, вы можете, но вряд ли это будет быстрее, учитывая, что Большая часть функций Postgis (GEOS) - это, прежде всего, порты JTS на C / C ++
Джон Пауэлл,
Вы правы, это работает, но на самом деле это не быстрее (занимает ~ 3,1 сек, в то время как использование GeometryN занимает 2 сек). Вот что я использовал: SELECT ST_AsGeoJson (ST_Transform (ST_Exteriorring ((ST_Dump (ST_Union (ST_Buffer ("GEOMETRY", 20)))). Geom), 4326)) FROM my_edges;
Николаус Крисмер
@ john-barça: Оу .. Я запутываю часть quad_segs = 2 в ST_Buffer при попытке вашего подхода ... с этим изменением запросы равны (оба в пределах 2 сек). Тем не менее, это все еще очень медленно (на мой взгляд), есть ли другой способ попробовать это?
Николаус Крисмер
Интересная проблема .... Вы хотите поделиться некоторыми тестовыми данными?
дбастон
Если это поможет, я рад поделиться некоторыми данными. Все, что я делаю здесь, с открытым исходным кодом, так что это не должно быть большой проблемой. Первое, на что следует обратить внимание: веб-приложение для тестирования находится по адресу dbis-isochrone.uibk.ac.at:8080/testing . Более подробную информацию о том, над чем я работаю, можно найти по адресу dbis-isochrone.uibk.ac.at . В разделе «ссылки» на сайте есть некоторые дополнительные ссылки (в том числе некоторые тестовые данные)
Николаус Крисмер

Ответы:

5

Если оставить в стороне сериализацию GeoJSON, на моем ноутбуке примерно 6,3 секунды:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(geom, 20, 2)))).geom))
FROM bz_edges

Глядя на данные в OpenJUMP, я заметил довольно мало деталей в сегментах улиц относительно желаемого уровня детализации в выходных данных. Кажется, что даже упрощение этих линий на лету может привести к значительному ускорению в PostGIS:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(ST_Simplify(geom, 10), 20, 2)))).geom))
FROM bz_edges

что снижает скорость до 2,3 секунд. Я подумал, что мог бы добиться большего успеха, сохранив обобщенную геометрию в отдельном столбце, а не вычисляя ее на лету, но это на самом деле не дало дополнительных преимуществ.

В зависимости от того, сколько кода вы готовы написать, вы почти наверняка сможете добиться большего успеха в Java, если не сказать больше, потому что вы можете использовать преимущества нескольких ядер. (Для чего стоит, JTS выполняет вышеуказанную операцию за 2,8 секунды). Одним из подходов может быть расширение, CascadedPolygonUnionчтобы некоторые операции объединения выполнялись параллельно. (обновление - вот ParallelCascadedPolygonUnion )

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

  1. определить связанные компоненты графика
  2. для каждого подключенного компонента найдите узел с минимальной координатой X (гарантированно находящийся снаружи компонента)
  3. обходите края компонента, всегда поворачивая влево (или вправо), когда это возможно. Это даст вам внешнее кольцо каждого компонента.
  4. полигонизировать внешнее кольцо и буфер соответствующим образом.
dbaston
источник
Спасибо ... упрощение - это большое и даже "простое" улучшение. Потребовалось время, необходимое на моем ноутбуке до 1,5 сек. Это не то, где я хочу быть, но немного лучше.
Николаус Крисмер
Относительно предложенного вами решения (пункты 1-4). Звучит также очень просто и стоит попробовать. Я думал о чем-то похожем, но я застрял в точке 1 (так очень рано :-)). Как определить подключенные компоненты (единственное, о чем я могу думать, это рекурсивный запрос, который также может быть очень медленным).
Николаус Крисмер
@NikolausKrismer Я использую JGraphT и ткацкий станок для подобных задач. Если вместо этого вы напишите свои собственные графовые методы (неплохая идея для лучшей производительности), поиск в глубину найдет вам компоненты. (Вы можете найти их в следующей версии PostGIS 2.2 с, ST_ClusterIntersectingно я думаю, что вы все равно захотите, чтобы любая обработка графов происходила вне базы данных, так что это, вероятно, бесполезно).
дбастон
Вот некоторые отличные советы. Я посмотрел на JGraphT, и это, безусловно, может помочь решить мою проблему. Тем не менее, я также посмотрел на Postgis 2.2 и функцию ST_ClusterIntersecting -> требуется около 200-250 мсек для идентификации различных кластеров в вышеописанном случае. Это нормально для меня (JGraphT, безусловно, мог бы сделать лучше). Теперь мне нужно разобраться с созданием externalRing (ST_ExteriorRing завершается ошибкой, поскольку ST_MakePolygon говорит, что мои ссылки не являются оболочкой)
Николаус Крисмер
Я вижу две сложности: (а) вам нужны не только внешнее кольцо, но и любые сегменты, которые выходят наружу из этого кольца, и (б) похоже, что ваши линии на самом деле не пересекаются на некоторых пересечениях. Вам нужно исправить (b), если вы собираетесь попытаться построить геометрию по результатам обхода графика.
dbaston