23. الصلاحية

في 90% من الحالات تكون الإجابة عن السؤال "لماذا يعطيني استعلامي الخطأ 'TopologyException'" هي "واحد أو أكثر من المدخلات غير صالح". وهذا يطرح السؤال: ما معنى أن يكون الشكل الهندسي غير صالح، ولماذا ينبغي أن نهتم بذلك؟

23.1. ما هي الصلاحية

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

تبدو بعض قواعد صلاحية المضلعات بديهية، ويبدو بعضها الآخر اعتباطيًا (وهي في الواقع اعتباطية).

  • يجب أن تكون حلقات المضلع مغلقة.

  • يجب أن تقع الحلقات التي تعرّف الثقوب داخل الحلقات التي تعرّف الحدود الخارجية.

  • لا يجوز أن تتقاطع الحلقات ذاتيًا (فلا يجوز أن تلمس نفسها أو تعبر نفسها).

  • لا يجوز أن تلمس الحلقات حلقات أخرى، إلا في نقطة واحدة.

  • لا يجوز أن تتلامس عناصر المضلعات المتعددة (multi-polygons) مع بعضها.

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

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

إليك مثالًا يوضح أهمية البنية. هذا المضلع غير صالح:

POLYGON((0 0, 0 1, 2 1, 2 2, 1 2, 1 0, 0 0));

يمكنك رؤية عدم الصلاحية بوضوح أكبر قليلًا في هذا المخطط:

_images/figure_eight.png

الحلقة الخارجية في الواقع على شكل الرقم ثمانية (8)، مع تقاطع ذاتي في المنتصف. لاحظ أن إجراءات الرسم تعرض تعبئة المضلع بنجاح، بحيث يبدو بصريًا أنه "مساحة": مربعان طول ضلع كل منهما وحدة واحدة، أي مساحة إجمالية قدرها وحدتا مساحة.

لنرَ ما تعتقده قاعدة البيانات بشأن مساحة مضلعنا:

SELECT ST_Area(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

 st_area
---------
       0

ما الذي يحدث هنا؟ تفترض الخوارزمية التي تحسب المساحة أن الحلقات لا تتقاطع ذاتيًا. فالحلقة السليمة تكون المساحة المحدودة (الداخل) فيها دائمًا على جانب واحد من الخط المحيط (لا يهم أي جانب، المهم أن تكون على جانب واحد). أما في حلقتنا (غير السليمة) ذات شكل الرقم ثمانية، فالمساحة المحدودة تقع على يمين الخط في أحد الفصّين وعلى يساره في الفص الآخر. وهذا يجعل المساحتين المحسوبتين لكل فص تلغي إحداهما الأخرى (إحداهما 1 والأخرى -1)، ومن هنا نتيجة "المساحة الصفرية".

23.2. الكشف عن الصلاحية

في المثال السابق كان لدينا مضلع واحد نعرف أنه غير صالح. فكيف نكشف عدم الصلاحية في جدول يضم ملايين الأشكال الهندسية؟ باستخدام الدالة ST_IsValid(geometry). وعند تطبيقها على شكلنا ذي الرقم ثمانية نحصل على إجابة سريعة:

SELECT ST_IsValid(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

f

نعرف الآن أن المعلم غير صالح، لكننا لا نعرف السبب. يمكننا استخدام الدالة ST_IsValidReason(geometry) لمعرفة مصدر عدم الصلاحية:

SELECT ST_IsValidReason(ST_GeometryFromText(
         'POLYGON((0 0, 0 1, 1 1, 2 1, 2 2, 1 2, 1 1, 1 0, 0 0))'
       ));

Self-intersection[1 1]

لاحظ أنه بالإضافة إلى السبب (التقاطع الذاتي) يُعاد أيضًا موقع عدم الصلاحية (الإحداثي (1 1)).

يمكننا استخدام الدالة ST_IsValid(geometry) لاختبار جداولنا أيضًا:

-- Find all the invalid polygons and what their problem is
SELECT name, boroname, ST_IsValidReason(geom)
FROM nyc_neighborhoods
WHERE NOT ST_IsValid(geom);

          name           |   boroname    |          st_isvalidreason
-------------------------+---------------+-----------------------------------------
 Howard Beach            | Queens        | Self-intersection[597264.08 4499924.54]
 Corona                  | Queens        | Self-intersection[595483.05 4513817.95]
 Steinway                | Queens        | Self-intersection[593545.57 4514735.20]
 Red Hook                | Brooklyn      | Self-intersection[584306.82 4502360.51]

23.3. إصلاح عدم الصلاحية

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

على سبيل المثال، إليك حالة كلاسيكية لعدم الصلاحية -- "مضلع الموزة" -- وهو حلقة واحدة تحيط بمساحة لكنها تنحني لتلمس نفسها، تاركةً "ثقبًا" ليس ثقبًا في الحقيقة.

POLYGON((0 0, 2 0, 1 1, 2 2, 3 1, 2 0, 4 0, 4 4, 0 4, 0 0))
_images/banana.png

تشغيل ST_MakeValid على المضلع يُعيد مضلعًا صالحًا وفق OGC، يتكون من حلقة خارجية وحلقة داخلية تتلامسان في نقطة واحدة.

SELECT ST_AsText(
         ST_MakeValid(
           ST_GeometryFromText('POLYGON((0 0, 2 0, 1 1, 2 2, 3 1, 2 0, 4 0, 4 4, 0 4, 0 0))')
         )
       );

POLYGON((0 0,0 4,4 4,4 0,2 0,0 0),(2 0,3 1,2 2,1 1,2 0))

ملاحظة

"مضلع الموزة" (أو "الغلاف المقلوب") حالة يختلف فيها نموذج الطوبولوجيا الخاص بـ OGC للأشكال الهندسية الصالحة عن النموذج الذي تستخدمه ESRI داخليًا. فنموذج ESRI يعدّ الحلقات المتلامسة غير صالحة، ويفضّل شكل الموزة لهذا النوع من الأشكال. ونموذج OGC على العكس من ذلك. وليس أي منهما هو "الصحيح"، بل هما مجرد طريقتين مختلفتين لنمذجة الحالة نفسها.

23.4. الإصلاح الجماعي للصلاحية

إليك مثالًا على SQL لوسم الأشكال الهندسية غير الصالحة لمراجعتها، مع إضافة نسخة مُصلَحة منها إلى الجدول.

-- Column for old invalid form
ALTER TABLE nyc_neighborhoods
  ADD COLUMN geom_invalid geometry
  DEFAULT NULL;

-- Fix invalid and save the original
UPDATE nyc_neighborhoods
  SET geom = ST_MakeValid(geom),
      geom_invalid = geom
  WHERE NOT ST_IsValid(geom);

-- Review the invalid cases
SELECT geom, ST_IsValidReason(geom_invalid)
  FROM nyc_neighborhoods
  WHERE geom_invalid IS NOT NULL;

من الأدوات الجيدة لإصلاح الأشكال الهندسية غير الصالحة بصريًا OpenJump (http://openjump.org)، التي تتضمن إجراء تحقق ضمن Tools->QA->Validate Selected Layers.

23.5. قائمة الدوال

ST_IsValid(geometry A): تُعيد قيمة منطقية (boolean) تبيّن ما إذا كان الشكل الهندسي صالحًا.

ST_IsValidReason(geometry A): تُعيد سلسلة نصية تتضمن سبب عدم الصلاحية وإحداثي موقع عدم الصلاحية.

ST_MakeValid(geometry A): تُعيد شكلًا هندسيًا مُعاد البناء ليلتزم بقواعد الصلاحية.