Більше

Побудова багатокутника над досяжною територією


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

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

Але почекайте ... перш за все!
Ось візуалізація країв, які я є результатом розрахунку моєї ізохрони: Ці краї зберігаються в таблиці бази даних PostGIS і є простими рядками.

Те, що я хочу показати користувачеві, виглядає так: Зверніть увагу на від’єднані ділянки на самому півдні та на сході від зображення. Їх слід накреслити як окремі області (тому тут не дозволяється об’єднання :-))

Наразі я використовую такий запит:

SELECT ST_AsGeoJson (St_Transform (ST_Multi (ST_Collect (багатокутники)), 4326)) AS AS покриття FROM (SELECT ST_MakePolygon (ST_ExteriorRing (ST_GeometryN (сегменти, генерація_серій (1, ST_NumGeometries (segment)) (сегмент)) "ГЕОМЕТРІЯ", 20, 'quad_segs = 2')) ЯК сегменти ВІД моїх_країн ЯК а) ЯК б) ЯК в

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

SELECT ST_AsGeoJson (St_Transform (ST_Multi (ST_Collect (полігони)), 4326)) AS покриття FROM (SELECT ST_Buffer (ST_Collect (ST_LineMerge ("GEOMETRY") ")", 20, 'quad_segs = 2') AS полігони FM

У моїй системі це займає приблизно 3,8 секунди (тобто майже вдвічі більше часу). Мій перший висновок з цього невеликого еталону полягає в тому, що ST_Buffer стає несподівано повільним, коли справа доходить до MultiLineStrings (навіть повільніше, ніж при створенні буферів для кожного рядка та об'єднанні буферів - що на мої очі просто дивно)

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

Чи є кращий спосіб створити область, показану в PostGIS? Можливо, також за допомогою коду java (jts) або коду javascript на стороні клієнта (jsts)? Насправді я міг би жити, втрачаючи деякі деталі, до тих пір, поки області, показані в моєму результаті, залишаться розділеними, а розрахунок стане (набагато) швидшим.


Якщо відмінити серіалізацію 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. полігонізуйте зовнішнє кільце та належним чином його занурите.