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

geo-algos مشروعي التعليمي للنظر إلى الداخل. ينفّذ خوارزميات جغرافية مكانية (geospatial) كلاسيكية من الصفر بلغة Rust، دون أي اعتماديات وقت التشغيل (runtime dependencies). وكل واحدة تُفحص أمام مرجع مستقل أو مرجع بالقوة الغاشمة (brute force) باستعمال property tests. الـ README يقولها بوضوح وسأقولها أنا أيضًا: للعمل الحقيقي استعمل الـ crates المسماة geo و rstar. هذا المشروع للتعلّم.

ماذا يقدّم

فيه أربع وحدات (modules):

الوحدة ماذا تفعل
pip نقطة داخل مضلع مع ثقوب: ray casting (قاعدة even-odd) و winding number (قاعدة non-zero)، مع نتيجة صريحة Boundary
distance Haversine (كرة) و Vincenty inverse (المجسم الإهليلجي WGS84) مع الاتجاهات وخطأ عدم التقارب
simplify تبسيط الخطوط بـ Douglas-Peucker، بشكل تكراري دون حد لعمق الاستدعاء
rtree R-tree: إدراج Guttman مع تقسيم خطي أو تربيعي، وتحميل بالجملة STR، واستعلام المجال، و kNN بطريقة best-first

ما بنيته من الصفر، وما يعلّمه

نقطة داخل مضلع: قاعدتان، والحالات الطرفية. طريقة ray casting تعدّ كم ضلعًا يقطعه شعاع أفقي ينطلق من النقطة: العدد الفردي يعني أنها في الداخل. والفخ هو شعاع يمر تمامًا برأس من رؤوس المضلع. والحل قاعدة نصف مفتوحة (half-open)، فيُحسب ذلك الرأس مرة واحدة. أما winding number (نسخة Sunday) فتستعمل اختبارات الاتجاه فقط. الطريقتان تتفقان في الحلقات البسيطة وتختلفان في التي تقطع نفسها: مركز النجمة الخماسية (pentagram) خارج المضلع حسب even-odd وداخله حسب non-zero، ويوجد اختبار لذلك. والدالة Polygon::locate تفحص الحلقات أولًا، فالنقطة الواقعة تمامًا على ضلع ترجع Boundary بدل جواب اعتباطي.

المسافات: كرة أم مجسم إهليلجي. Haversine تعامل الأرض ككرة نصف قطرها المتوسط 6,371,008.8 متر. هي بسيطة، وخطؤها يصل إلى حوالي 0.5% مقارنة بالمجسم الإهليلجي. أما صيغة Vincenty العكسية فتعمل على المجسم WGS84 وتكرّر الحساب على فرق خط الطول. تعطي دقة أقل من الميليمتر، وهي مفحوصة أمام الخط الذي استعمله Vincenty نفسه بين Flinders Peak و Buninyong (54,972.271 متر). ولها ضعف معروف: النقاط شبه المتقابلة على طرفي الأرض (antipodal) قد لا يتقارب حسابها. وهنا تُرجَع هذه الحالة كـ VincentyError::NoConvergence بدل رقم خاطئ.

Douglas-Peucker: ضمان يمكن اختباره. الخوارزمية تحتفظ بنقطتَي الطرفين، وتجد أبعد نقطة عن الوتر الواصل بينهما، وتكرّر ما دامت تلك النقطة أبعد من epsilon. النسخة المعروفة في الكتب تعاودية (recursive)؛ وهذه تستعمل stack صريحًا، فلا يستطيع خط طويل جدًا تجاوز حد الـ call stack. والـ property test يتحقق من الضمان نفسه: كل نقطة محذوفة تبعد أقل من epsilon عن القطعة التي عوّضتها.

الـ R-tree: فهرس مكاني. العُقد مخزّنة في arena (أي Vec) ويُشار إليها بالفهرس، وهذا يجنّب الصراع مع الـ borrow checker حول مؤشرات الأب والابن. الدالة insert تتبع ورقة Guttman: ChooseLeaf بأقل توسيع، ثم تقسيم عند الامتلاء (PickSeeds/PickNext التربيعي، أو البذور الخطية)، ثم تعديل المستطيلات المحيطة صعودًا إلى الجذر. و bulk_load هي Sort-Tile-Recursive (STR)، وتملأ العُقد كاملة حين تملك كل البيانات مسبقًا. و nearest بحث best-first بـ min-heap مفتاحه MINDIST، فتخرج المدخلات بترتيب المسافة الدقيق. و validate() تتحقق من الثوابت: تساوي عمق الأوراق، وحدود عدد الأبناء، وإحكام المستطيلات المحيطة.

طريقة الاستعمال

أضِفه إلى مشروع Rust من GitHub:

cargo add --git https://github.com/AbdeldjalilChougui/geo-algos 

أو انسخ المستودع وشغّل ما فيه:

cargo test # unit tests + proptest checks cargo run --example demo # small tour of every module cargo bench # criterion benchmarks 

ومثال قصير من الـ README يُظهر ثلاثًا من الوحدات:

use geo_algos::{haversine, LonLat, Point, Polygon, RTree, Entry, Rect}; let d = haversine(LonLat::new(3.0588, 36.7538), LonLat::new(-0.6417, 35.6971)); // ~352 km let sq = |a: f64, b: f64| vec![Point::new(a, a), Point::new(b, a), Point::new(b, b), Point::new(a, b)]; let donut = Polygon::new(sq(0.0, 10.0), vec![sq(4.0, 6.0)]); assert!(donut.contains(Point::new(1.0, 1.0))); assert!(!donut.contains(Point::new(5.0, 5.0))); // in the hole let tree = RTree::bulk_load(vec![Entry::point(Point::new(1.0, 2.0), "a")], 16); let near = tree.nearest(Point::new(0.0, 0.0), 1); 

السطر الأول يقيس المسافة بين زوجين من خط الطول وخط العرض، حوالي 352 كم. والمضلع مربع فيه ثقب مربع، فالنقطة الواقعة في الثقب ليست داخله. والسطران الأخيران يبنيان R-tree بسعة 16 لكل عقدة ويطلبان أقرب مدخل إلى نقطة الأصل.

كيف اختُبر

في الاختبارات يتحقق وعد "مفحوص أمام مرجع". يوجد 39 اختبار وحدة (unit test) بجانب الكود: حالات طرفية، وحدود، وثقوب، ونجمة خماسية، ومدخلات شاذة، ومسافات معروفة.

ثم توجد 8 خصائص proptest في tests/properties.rs. الـ property tests تولّد مدخلات عشوائية وتتحقق أن قاعدة ما تصح دائمًا:

  • نقطة داخل مضلع أمام مرجع تحليلي لمضلع نجمي، مع مقارنة ray casting بـ winding number؛
  • الثقوب أمام صيغة مغلقة؛
  • بديهيات المسافة (metric axioms) لـ Haversine؛
  • Vincenty ضمن 0.6% من Haversine؛
  • ضمان التسامح في Douglas-Peucker؛
  • نتائج استعلام المجال و kNN في الـ R-tree أمام القوة الغاشمة، للأشجار المبنية بالإدراج (بنوعَي التقسيم) ولأشجار STR.

والأخيرة هي النمط الذي أحبه أكثر. المسح الخطي لكل النقاط بطيء وصحته واضحة، فهو الحَكَم المثالي لفهرس سريع ومن السهل أن يخطئ خطأً خفيًا.

وفي الـ README جدول قياسات أداء مع تنبيه صريح: قيس بـ cargo bench -- --quick على حاسوب محمول كان مشغولًا بعمليات بناء أخرى، فالأرقام تدل على مراتب المقدار فقط. ومع هذا التنبيه: Haversine حوالي 0.23 ميكروثانية و Vincenty حوالي 2 ميكروثانية لكل استدعاء، وتحميل 50 ألف نقطة بالجملة بطريقة STR يأخذ حوالي 52 ميلي ثانية، وإدراج نفس النقاط واحدة واحدة يأخذ بين 0.3 و 0.5 ثانية تقريبًا.

أشياء يجب معرفتها

الـ README يذكر الحدود، وهي مهمة إن فكرت في استعماله خارج التعلّم:

  • هذا مشروع تعليمي. للعمل الحقيقي استعمل geo و rstar.
  • كل شيء بأعداد f64 عادية دون robust predicates. كشف الحدود دقيق فقط حين يكون الحساب دقيقًا: الرؤوس والأضلاع الموازية للمحاور تعمل، لكن نقطة محسوبة على ضلع مائل قد تقع داخله أو خارجه بفارق ضئيل جدًا.
  • الخوارزميات المستوية تعامل درجات خط الطول والعرض كإحداثيات x/y مسطحة. لا شيء يتعامل مع خط الطول 180 (antimeridian)، وقيمة epsilon في Douglas-Peucker بوحدات المدخل.
  • الـ R-tree دون حذف ودون إعادة الإدراج الخاصة بـ R*-tree. ومسافة kNN تُقاس إلى المستطيل المحيط بكل مدخل.
  • صحة الثقوب (أن تكون داخل المضلع الخارجي وغير متداخلة) مفترضة ولا تُفحص.

ما تعلّمته

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

الثاني أن المرجع البطيء أداة ممتازة. كل وحدة هنا تقريبًا تُختبر بمقارنتها بشيء أبسط: القوة الغاشمة للـ R-tree، وصيغة مغلقة للثقوب، و Haversine كحدّ معقول لـ Vincenty. وحين يختلف الاثنان في مدخل عشوائي، يقلّصه proptest إلى مثال صغير، ويظهر الخطأ غالبًا من أول نظرة.

الثالث خاص بـ Rust. الشجرة ذات روابط الأب والابن مزعجة مع الـ references ومريحة في arena مع الفهارس.

وإرجاع Boundary أو NoConvergence كنتائج صريحة علّمني شيئًا عامًا: حين يكون للخوارزمية مدخل لا تستطيع الإجابة عنه جيدًا، فصرّح بذلك في النوع (type) بدل إرجاع تخمين.

احصل على الكود

المصدر والمثال والاختبارات وقياسات الأداء على GitHub: https://github.com/AbdeldjalilChougui/geo-algos. المشروع برخصة MIT، ولا يستعمل أي بيانات خارجية.

نُشر في الأصل على abdeldjalilchougui.biz.