أصدرنا earstrip، وهو مثلِّث المضلعات من محرك الخرائط لدينا، بوصفه مكتبة صغيرة مفتوحة المصدر تحت ترخيص ISC، وهو الترخيص نفسه المستخدم في earcut. وهو يتألف من ملف رأس واحد بلغة C++ ونسخة WebAssembly منشورة على npm، وتقبل الوسائط نفسها التي يقبلها earcut. في C++ يعمل أسرع بنسبة 14% من earcut.hpp، وفي المتصفح يعمل بسرعة تتراوح بين 1.4 و2.1 ضعف من earcut.js.
لا تستطيع وحدة معالجة الرسوميات ملء سوى المثلثات، بينما تتكون الخريطة في معظمها من مضلعات: المباني والحدائق وساحات وقوف السيارات وأشرطة العشب بين خطوط الترام. وقبل ملء أي مضلع، يجب تقسيم محيطه إلى مثلثات. تحتوي خريطتنا غير المتصلة بالإنترنت لمقاطعة مازوفيا، المنطقة المحيطة بوارسو، على 3,740,425 مضلعاً عند مستوى التكبير 13. وعلى نواة واحدة من معالج M4 Pro، احتاج المثلِّث المقيّد بتقنية Delaunay في محركنا إلى 2.93 ثانية لمعالجتها جميعاً.
في أكتوبر الماضي استبدلناه بقطع الأذن. إذ يتجنب تثليث Delaunay المثلثات الرفيعة وهو مفيد في الاستيفاء والمحاكاة، لكن التعبئة المسطحة لا تحتاج إلى هذا المستوى من الجودة، ومعظم العمل كان ينفق على الأشكال البسيطة. ما يقارب نصف مضلعات مازوفيا، أي 1.8 مليون مضلع، لها أربع رؤوس أو أقل، ومع ذلك أنفق كود Delaunay 419 ms في بناء تثليثاتها من الصفر. ويزيل قطع الأذن زاوية واحدة في كل مرة، وكل مضلع بسيط له أكثر من ثلاثة رؤوس يملك على الأقل أذنين غير متداخلتين، لذا يوجد دائماً قطع آخر يمكن إجراؤه.
ولتوثيق العمل، أعدنا بناء قاطع الأذن بفكرة واحدة لكل التزام (commit)، وقست كل خطوة على مجموعة الـ 3.7 مليون مضلع نفسها. تعالج النسخة النهائية المجموعة الكاملة في 489 ms، وهو الرقم الوارد في العنوان الرئيسي.
المصدر: Hacker News · لخّصه HeadlinesBriefing