40. بناء الأشكال الهندسية المتقدم¶

قدّمت لنا الطبقة nyc_subway_stations أمثلة كثيرة مثيرة للاهتمام حتى الآن، لكن فيها أمرًا لافتًا:

رغم أنها قاعدة بيانات لجميع المحطات، فإنها لا تتيح عرض مسارات الخطوط بسهولة! في هذا الفصل سنستخدم ميزات متقدمة في PostgreSQL و PostGIS لبناء طبقة خطية جديدة للمسارات انطلاقًا من طبقة النقاط الخاصة بمحطات المترو.

تزداد مهمتنا صعوبة بسبب مشكلتين:

يحتوي العمود routes في nyc_subway_stations على عدة معرّفات للخطوط في كل صف، لذا فإن المحطة التي قد تظهر في عدة خطوط لا تظهر إلا مرة واحدة في الجدول.
وارتباطًا بالمشكلة السابقة، لا توجد في جدول المحطات معلومات عن ترتيب المحطات على الخط، لذا مع أنه من الممكن إيجاد جميع المحطات في خط معيّن، فلا يمكن باستخدام البيانات الوصفية تحديد الترتيب الذي تمر به القطارات عبر المحطات.

المشكلة الثانية هي الأصعب: إذا كانت لدينا مجموعة غير مرتبة من النقاط على خط ما، فكيف نرتبها لتطابق المسار الفعلي؟

إليك محطات توقف القطار 'Q':

SELECT s.gid, s.geom
FROM nyc_subway_stations s
WHERE (strpos(s.routes, 'Q') <> 0);

في هذه الصورة، وُسمت المحطات بمفتاحها الأساسي الفريد gid.

إذا بدأنا من إحدى محطتي الطرفين، فيبدو أن المحطة التالية على الخط هي دائمًا الأقرب. ويمكننا تكرار العملية في كل مرة ما دمنا نستبعد من بحثنا جميع المحطات التي وجدناها سابقًا.

هناك طريقتان لتشغيل مثل هذا الإجراء التكراري في قاعدة البيانات:

استخدام لغة إجرائية، مثل PL/PgSQL.
استخدام تعبيرات الجداول المشتركة العودية.

تتميز تعبيرات الجداول المشتركة (CTE) بأنها لا تتطلب تعريف دالة لتشغيلها. إليك تعبير CTE لحساب خط مسار القطار 'Q'، بدءًا من المحطة الواقعة في أقصى الشمال (حيث gid يساوي 304).

WITH RECURSIVE next_stop(geom, idlist) AS (
    (SELECT
      geom,
      ARRAY[gid] AS idlist
    FROM nyc_subway_stations
    WHERE gid = 304)
    UNION ALL
    (SELECT
      s.geom,
      array_append(n.idlist, s.gid) AS idlist
    FROM nyc_subway_stations s, next_stop n
    WHERE strpos(s.routes, 'Q') != 0
    AND NOT n.idlist @> ARRAY[s.gid]
    ORDER BY ST_Distance(n.geom, s.geom) ASC
    LIMIT 1)
)
SELECT geom, idlist FROM next_stop;

يتكون تعبير CTE من نصفين مدموجين معًا بالاتحاد (UNION):

يحدد النصف الأول نقطة البداية للتعبير. نحصل على الشكل الهندسي الأولي ونهيّئ مصفوفة المعرّفات التي زرناها، باستخدام السجل ذي "gid" 304 (نهاية الخط).
يكرر النصف الثاني العملية حتى لا يجد سجلات أخرى. وفي كل تكرار يأخذ القيمة من التكرار السابق عبر المرجع الذاتي إلى "next_stop". نبحث في كل محطة على الخط Q ( strpos(s.routes,'Q') ) لم نضفها بعد إلى قائمة المحطات التي زرناها ( NOT n.idlist @> ARRAY[s.gid] )، ونرتبها حسب بعدها عن النقطة السابقة، ونأخذ الأولى منها فقط (الأقرب).

إلى جانب تعبير CTE العودي نفسه، نستخدم هنا عددًا من ميزات المصفوفات المتقدمة في PostgreSQL:

نحن نستخدم ARRAY! يدعم PostgreSQL المصفوفات من أي نوع. لدينا في هذه الحالة مصفوفة من الأعداد الصحيحة، لكن يمكننا أيضًا بناء مصفوفة من الأشكال الهندسية، أو من أي نوع آخر في PostgreSQL.
نستخدم الدالة array_append لبناء مصفوفة المعرّفات التي زرناها.
نستخدم عامل المصفوفات @> ("المصفوفة تحتوي") لمعرفة محطات القطار Q التي زرناها بالفعل. يتطلب العامل @> قيمًا من نوع ARRAY على الجانبين، لذا علينا تحويل أرقام "gid" المفردة إلى مصفوفات ذات عنصر واحد باستخدام الصيغة ARRAY[].

عند تشغيل الاستعلام، تحصل على كل شكل هندسي بالترتيب الذي وُجد به (وهو ترتيب المسار)، إضافة إلى قائمة المعرّفات التي زُرت بالفعل. وعند تمرير الأشكال الهندسية إلى الدالة التجميعية ST_MakeLine في PostGIS تتحول مجموعة الأشكال الهندسية إلى مُخرج خطي واحد، مبني بالترتيب المُعطى.

WITH RECURSIVE next_stop(geom, idlist) AS (
    (SELECT
      geom,
      ARRAY[gid] AS idlist
    FROM nyc_subway_stations
    WHERE gid = 304)
    UNION ALL
    (SELECT
      s.geom,
      array_append(n.idlist, s.gid) AS idlist
    FROM nyc_subway_stations s, next_stop n
    WHERE strpos(s.routes, 'Q') != 0
    AND NOT n.idlist @> ARRAY[s.gid]
    ORDER BY ST_Distance(n.geom, s.geom) ASC
    LIMIT 1)
)
SELECT ST_MakeLine(geom) AS geom FROM next_stop;

ويبدو كالتالي:

نجحنا!

باستثناء مشكلتين:

نحسب هنا مسار خط مترو واحد فقط، بينما نريد حساب جميع المسارات.
يتضمن استعلامنا معرفة مسبقة، وهي معرّف المحطة الأولية الذي يعمل كبذرة لخوارزمية البحث التي تبني المسار.

لنعالج المشكلة الأصعب أولًا: تحديد المحطة الأولى على المسار دون فحص مجموعة المحطات المكوّنة للمسار يدويًا بالنظر.

يمكن أن تكون محطات القطار 'Q' نقطة انطلاق لنا. ما الذي يميّز محطات طرفي المسار؟

إحدى الإجابات هي "إنها المحطات الواقعة في أقصى الشمال وأقصى الجنوب". لكن تخيّل لو أن القطار 'Q' يسير من الشرق إلى الغرب، فهل يظل الشرط صحيحًا؟

هناك وصف أقل ارتباطًا بالاتجاه لمحطات الطرفين وهو "إنها المحطات الأبعد عن منتصف المسار". ومع هذا الوصف لا يهم إن كان المسار يمتد شمالًا/جنوبًا أو شرقًا/غربًا، المهم أن يمتد في اتجاه واحد تقريبًا، لا سيما عند طرفيه.

بما أنه لا توجد قاعدة استدلالية صحيحة بنسبة 100% لتحديد نقاط النهاية، فلنجرّب هذه القاعدة الثانية.

ملاحظة

من الحالات الواضحة التي تفشل فيها قاعدة "الأبعد عن المنتصف" الخط الدائري، مثل Circle Line في لندن بالمملكة المتحدة. لحسن الحظ، لا توجد في نيويورك أي خطوط من هذا النوع!

لتحديد محطات الطرفين لكل مسار، علينا أولًا تحديد المسارات الموجودة! نبحث عن المسارات المتمايزة.

WITH routes AS (
  SELECT DISTINCT unnest(string_to_array(routes,',')) AS route
  FROM nyc_subway_stations ORDER BY route
)
SELECT * FROM routes;

لاحظ استخدام دالتين متقدمتين من دوال ARRAY في PostgreSQL:

تأخذ الدالة string_to_array سلسلة نصية وتقسمها إلى مصفوفة باستخدام حرف فاصل. يدعم PostgreSQL المصفوفات من أي نوع، لذا يمكن بناء مصفوفات من السلاسل النصية كما في هذه الحالة، وكذلك من الأشكال الهندسية (geometry) والجغرافية (geography) كما سنرى لاحقًا في هذا المثال.
تأخذ الدالة unnest مصفوفة وتبني صفًا جديدًا لكل عنصر فيها. والنتيجة تحويل مصفوفة "أفقية" مضمّنة في صف واحد إلى مصفوفة "عمودية" بصف لكل قيمة.

النتيجة قائمة بجميع معرّفات خطوط المترو الفريدة.

 route
-------
 1
 2
 3
 4
 5
 6
 7
 A
 B
 C
 D
 E
 F
 G
 J
 L
 M
 N
 Q
 R
 S
 V
 W
 Z
(24 rows)

يمكننا البناء على هذه النتيجة بربطها مجددًا بالجدول nyc_subway_stations لإنشاء جدول جديد يحتوي، لكل مسار، على صف لكل محطة على ذلك المسار.

WITH routes AS (
  SELECT DISTINCT unnest(string_to_array(routes,',')) AS route
  FROM nyc_subway_stations ORDER BY route
),
stops AS (
  SELECT s.gid, s.geom, r.route
  FROM routes r
  JOIN nyc_subway_stations s
  ON (strpos(s.routes, r.route) <> 0)
)
SELECT * FROM stops;

 gid |                      geom                      | route
-----+----------------------------------------------------+-------
   2 | 010100002026690000CBE327F938CD21415EDBE1572D315141 | 1
   3 | 010100002026690000C676635D10CD2141A0ECDB6975305141 | 1
  20 | 010100002026690000AE59A3F82C132241D835BA14D1435141 | 1
  22 | 0101000020266900003495A303D615224116DA56527D445141 | 1
                            ...etc...

يمكننا الآن إيجاد النقطة المركزية بجمع كل محطات كل مسار في نقطة متعددة (multi-point) واحدة، وحساب مركز الثقل لتلك النقطة المتعددة.

WITH routes AS (
  SELECT DISTINCT unnest(string_to_array(routes,',')) AS route
  FROM nyc_subway_stations ORDER BY route
),
stops AS (
  SELECT s.gid, s.geom, r.route
  FROM routes r
  JOIN nyc_subway_stations s
  ON (strpos(s.routes, r.route) <> 0)
),
centers AS (
  SELECT ST_Centroid(ST_Collect(geom)) AS geom, route
  FROM stops
  GROUP BY route
)
SELECT * FROM centers;

تبدو النقطة المركزية لمجموعة محطات القطار 'Q' كالتالي:

إذن يبدو أن المحطة الواقعة في أقصى الشمال، وهي نقطة النهاية، هي أيضًا المحطة الأبعد عن المركز. لنحسب النقطة الأبعد لكل مسار.

WITH routes AS (
  SELECT DISTINCT unnest(string_to_array(routes,',')) AS route
  FROM nyc_subway_stations ORDER BY route
),
stops AS (
  SELECT s.gid, s.geom, r.route
  FROM routes r
  JOIN nyc_subway_stations s
  ON (strpos(s.routes, r.route) <> 0)
),
centers AS (
  SELECT ST_Centroid(ST_Collect(geom)) AS geom, route
  FROM stops
  GROUP BY route
),
stops_distance AS (
  SELECT s.*, ST_Distance(s.geom, c.geom) AS distance
  FROM stops s JOIN centers c
  ON (s.route = c.route)
  ORDER BY route, distance DESC
),
first_stops AS (
  SELECT DISTINCT ON (route) stops_distance.*
  FROM stops_distance
)
SELECT * FROM first_stops;

أضفنا هذه المرة استعلامين فرعيين:

يربط stops_distance النقاط المركزية مجددًا بجدول المحطات ويحسب المسافة بين المحطات والمركز لكل مسار. وتُرتَّب النتيجة بحيث تخرج السجلات على دفعات لكل مسار، وتكون المحطة الأبعد أول سجل في الدفعة.
يرشّح first_stops مُخرجات stops_distance بأخذ السجل الأول فقط لكل مجموعة متمايزة. وبسبب الطريقة التي رتّبنا بها stops_distance يكون السجل الأول هو الأبعد، أي أنه المحطة التي نريد استخدامها كبذرة بداية لبناء كل خط مترو.

الآن نعرف كل المسارات، ونعرف (تقريبًا) المحطة التي يبدأ منها كل مسار: نحن جاهزون لتوليد خطوط المسارات!

لكن علينا أولًا تحويل تعبير CTE العودي إلى دالة يمكننا استدعاؤها مع معاملات.

CREATE OR REPLACE function walk_subway(integer, text) returns geometry AS
$$
WITH RECURSIVE next_stop(geom, idlist) AS (
    (SELECT
      geom AS geom,
      ARRAY[gid] AS idlist
    FROM nyc_subway_stations
    WHERE gid = $1)
    UNION ALL
    (SELECT
      s.geom AS geom,
      array_append(n.idlist, s.gid) AS idlist
    FROM nyc_subway_stations s, next_stop n
    WHERE strpos(s.routes, $2) != 0
    AND NOT n.idlist @> ARRAY[s.gid]
    ORDER BY ST_Distance(n.geom, s.geom) ASC
    LIMIT 1)
)
SELECT ST_MakeLine(geom) AS geom
FROM next_stop;
$$
language 'sql';

والآن نحن جاهزون للانطلاق!

CREATE TABLE nyc_subway_lines AS
-- Distinct route identifiers!
WITH routes AS (
  SELECT DISTINCT unnest(string_to_array(routes,',')) AS route
  FROM nyc_subway_stations ORDER BY route
),
-- Joined back to stops! Every route has all its stops!
stops AS (
  SELECT s.gid, s.geom, r.route
  FROM routes r
  JOIN nyc_subway_stations s
  ON (strpos(s.routes, r.route) <> 0)
),
-- Collects stops by routes and calculate centroid!
centers AS (
  SELECT ST_Centroid(ST_Collect(geom)) AS geom, route
  FROM stops
  GROUP BY route
),
-- Calculate stop/center distance for each stop in each route.
stops_distance AS (
  SELECT s.*, ST_Distance(s.geom, c.geom) AS distance
  FROM stops s JOIN centers c
  ON (s.route = c.route)
  ORDER BY route, distance DESC
),
-- Filter out just the furthest stop/center pairs.
first_stops AS (
  SELECT DISTINCT ON (route) stops_distance.*
  FROM stops_distance
)
-- Pass the route/stop information into the linear route generation function!
SELECT
  ascii(route) AS gid, -- QGIS likes numeric primary keys
  route,
  walk_subway(gid, route) AS geom
FROM first_stops;

-- Do some housekeeping too
ALTER TABLE nyc_subway_lines ADD PRIMARY KEY (gid);

إليك شكل جدولنا النهائي عند عرضه في QGIS:

كالعادة، هناك بعض المشكلات في فهمنا البسيط للبيانات:

هناك في الواقع قطاران 'S' (قطار "مكوكي" لمسافات قصيرة)، أحدهما في Manhattan والآخر في Rockaways، ونحن ندمجهما معًا لأن كليهما يُسمى 'S'؛
القطار '4' (وبعض القطارات الأخرى) يتفرّع عند نهاية أحد الخطوط إلى محطتين نهائيتين، فتنهار فرضية "تتبّع خط واحد" وتظهر في النتيجة خطاف غريب عند النهاية.

نأمل أن يكون هذا المثال قد قدّم لمحة عن بعض عمليات معالجة البيانات المعقدة الممكنة بالجمع بين الميزات المتقدمة في PostgreSQL و PostGIS.

40. بناء الأشكال الهندسية المتقدم¶

40.1. انظر أيضًا¶