26. نموذج التقاطعات التسعة الموسَّع بالأبعاد

"نموذج التقاطعات التسعة الموسَّع بالأبعاد" (DE9IM) إطار عمل لنمذجة كيفية تفاعل كائنين مكانيين.

أولًا، لكل كائن مكاني:

• داخل

• حدود

• خارج

في المضلعات، يكون الداخل والحدود والخارج واضحة:

الداخل هو الجزء المحصور بالحلقات؛ والحدود هي الحلقات نفسها؛ والخارج هو كل ما سوى ذلك في المستوى.

أما في المعالم الخطية، فالداخل والحدود والخارج أقل شيوعًا:

الداخل هو جزء الخط المحصور بين طرفيه؛ والحدود هي طرفا المعلم الخطي؛ والخارج هو كل ما سوى ذلك في المستوى.

وفي النقاط تبدو الأمور أغرب: فالداخل هو النقطة نفسها؛ والحدود مجموعة خالية؛ والخارج هو كل ما سوى ذلك في المستوى.

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

في المضلعين في المثال أعلاه، يكون تقاطع الداخلين مساحة ثنائية الأبعاد، لذا يُملأ ذلك الجزء من المصفوفة بالقيمة "2". أما الحدود فلا تتقاطع إلا في نقاط، وهي صفرية الأبعاد، لذا يُملأ ذلك الجزء من المصفوفة بالقيمة 0.

عندما لا يوجد تقاطع بين المكونات، تُملأ خانة المصفوفة بالقيمة "F".

إليك مثالًا آخر لخط يدخل جزئيًا في مضلع:

مصفوفة DE9IM لهذا التفاعل هي:

لاحظ أن حدود الكائنين لا تتقاطع فعليًا على الإطلاق (إذ تتفاعل نقطة نهاية الخط مع داخل المضلع لا مع حدوده، والعكس صحيح)، لذا تُملأ الخلية B/B بالقيمة "F".

مع أن ملء مصفوفات DE9IM بصريًا أمر ممتع، فسيكون من الجيد أن يتمكن الحاسوب من فعل ذلك، وهذا هو الغرض من الدالة ST_Relate.

يمكن تبسيط المثال السابق باستخدام مربع وخط بسيطين، لهما العلاقة المكانية نفسها التي بين المضلع والخط في مثالنا:

ويمكننا توليد معلومات DE9IM باستخدام SQL:

SELECT ST_Relate(
         'LINESTRING(0 0, 2 0)',
         'POLYGON((1 -1, 1 1, 3 1, 3 -1, 1 -1))'
       );

الإجابة (1010F0212) هي نفسها التي حسبناها بصريًا، لكنها تُعاد كسلسلة نصية من 9 محارف، يُلحق فيها الصف الأول والثاني والثالث من الجدول بعضها ببعض.

101
0F0
212

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

CREATE TABLE lakes ( id serial primary key, geom geometry );
CREATE TABLE docks ( id serial primary key, good boolean, geom geometry );

INSERT INTO lakes ( geom )
  VALUES ( 'POLYGON ((100 200, 140 230, 180 310, 280 310, 390 270, 400 210, 320 140, 215 141, 150 170, 100 200))');

INSERT INTO docks ( geom, good )
  VALUES
        ('LINESTRING (170 290, 205 272)',true),
        ('LINESTRING (120 215, 176 197)',true),
        ('LINESTRING (290 260, 340 250)',false),
        ('LINESTRING (350 300, 400 320)',false),
        ('LINESTRING (370 230, 420 240)',false),
        ('LINESTRING (370 180, 390 160)',false);

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

تتسم أرصفتنا النظامية بالخصائص التالية:

• لدواخلها تقاطع خطي (1D) مع داخل البحيرة

• لحدودها تقاطع نقطي (0D) مع داخل البحيرة

• لحدودها أيضًا تقاطع نقطي (0D) مع حدود البحيرة

• لا تقاطع (F) بين دواخلها وخارج البحيرة

لذا تبدو مصفوفة DE9IM الخاصة بها هكذا:

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

SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1FF00F212');

-- Answer: our two good docks

لاحظ استخدام صيغة ST_Relate ذات المعاملات الثلاثة، التي تُعيد true إذا تطابق النمط و false إذا لم يتطابق. وفي نمط محدد بالكامل كهذا، لا حاجة إلى الصيغة ذات المعاملات الثلاثة -- إذ كان بإمكاننا ببساطة استخدام عامل تساوي السلاسل النصية.

لكن في عمليات البحث عن أنماط أقل صرامة، تتيح الصيغة ذات المعاملات الثلاثة استخدام محارف بديلة في سلسلة النمط:

• "*" تعني "أي قيمة في هذه الخلية مقبولة"

• "T" تعني "أي قيمة غير false (0 أو 1 أو 2) مقبولة"

على سبيل المثال، من الأرصفة الممكنة التي لم نُدرجها في الرسم التوضيحي لمثالنا رصيف له تقاطع ثنائي الأبعاد مع حدود البحيرة:

INSERT INTO docks ( geom, good )
  VALUES ('LINESTRING (140 230, 150 250, 210 230)',true);

إذا أردنا إدراج هذه الحالة ضمن مجموعة الأرصفة "النظامية"، فعلينا تغيير نمط العلاقة في استعلامنا. وتحديدًا، يمكن الآن أن يكون تقاطع داخل الرصيف مع حدود البحيرة إما 1 (حالتنا الجديدة) أو F (حالتنا الأصلية). لذا نستخدم المحرف الشامل "*" في النمط.

ويبدو استعلام SQL هكذا:

SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1*F00F212');

-- Answer: our (now) three good docks

تحقق من أن استعلام SQL الأكثر صرامة من المثال السابق لا يُعيد الرصيف الجديد.

26.1. اختبار جودة البيانات

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

بالتأكيد!

SELECT a.gid, b.gid
FROM nyc_census_blocks a, nyc_census_blocks b
WHERE ST_Intersects(a.geom, b.geom)
  AND ST_Relate(a.geom, b.geom, '2********')
  AND a.gid != b.gid
LIMIT 10;

-- Answer: 10, there's some funny business

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

يمكننا اختبار ذلك بالبحث عن الشوارع التي تتقاطع (فيكون لدينا ربط) لكن التقاطع بين حدودها ليس صفري الأبعاد (أي أن نقاط النهاية لا تتلامس):

SELECT a.gid, b.gid
FROM nyc_streets a, nyc_streets b
WHERE ST_Intersects(a.geom, b.geom)
  AND NOT ST_Relate(a.geom, b.geom, '****0****')
  AND a.gid != b.gid
LIMIT 10;

-- Answer: This happens, so the data is not end-noded.

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

ST_Relate(geometry A, geometry B): تُعيد سلسلة نصية تمثّل علاقة DE9IM بين الشكلين الهندسيين.