بهینه‌سازی مثلث‌بندی نقشه‌ها: چطور الگوریتم earstrip از earcut سریع‌تر شد — Faster than earcut: triangulating 3.7M map polygons in 489 ms
خلاصه
توسعه‌دهندگان موتور نقشه Globus کتابخانه earstrip را برای مثلث‌بندی چندضلعی‌های نقشه معرفی کرده‌اند. با تغییر الگوریتم از Delaunay به ear clipping و اعمال بهینه‌سازی‌های مختلف روی ۳.۷ میلیون چندضلعی، این کتابخانه موفق شد عملکردی بسیار سریع‌تر از earcut در C و مرورگر ثبت کند.
موتورهای رندر نقشه برای پر کردن فضاهایی مثل ساختمان‌ها، پارک‌ها و فضای سبز با GPU، نیازمند این هستند که تمامی چندضلعی‌های نقشه به مثلث تبدیل شوند. کتابخانه earstrip که اخیراً تحت مجوز ISC منتشر شده، تلاش دارد این فرآیند را به شکل چشمگیری سرعت ببخشد. این کتابخانه در قالب یک هدر C++ و یک بیلد WebAssembly روی npm عرضه شده و دقیقاً از همان آرگومان‌های کتابخانه معروف earcut پشتیبانی می‌کند.
زمینه و چالش مثلث‌بندی نقشه
پیش‌تر، موتور نقشه مذکور از یک مثلث‌بندconstrained Delaunay استفاده می‌کرد. روی نسخه آفلاین نقشه منطقه ماسوویان (شامل بیش از ۳.۷ میلیون چندضلعی)، این الگوریتم روی یک هسته پردازنده نیازمند زمان قابل توجهی بود. بخش عمده‌ای از این زمان صرف چندضلعی‌های ساده‌ای می‌شود که اصلاً نیازی به برش‌های پیچیده ندارند؛ برای مثال، نزدیک به نیمی از چندضلعی‌های این نقشه ۴ راس یا کمتر دارند.
الگوریتم Delaunay تلاش می‌کند مثلث‌بندی را به گونه‌ای انجام دهد که کمترین زاویه مثلث‌ها حداکثر مقدار ممکن را داشته باشد. این ویژگی برای شبیه‌سازی‌های مهندسی یا درون‌یابی عالی است، اما کارت‌های گرافیک برای رنگ‌آمیزی ساده (Flat Fill) تفاوتی میان مثلث‌های مختلف قائل نیستند.
گذار به Ear Clipping
برای حل این مشکل، توسعه‌دهندگان به سراغ روش کلاسیک ear clipping رفتند. گوشه‌ای از یک چندضلعی که با یک خط مستقیم بریده می‌شود و مثلثی بدون تداخل با سایر بخش‌ها ایجاد می‌کند، یک «گوش» (Ear) نامیده می‌شود. اثبات شده است که هر چندضلعی ساده با بیش از سه راس حداقل دو گوش غیرمتداخل دارد و می‌توان آن را گام به گام تجزیه کرد.
مراحل بهینه‌سازی کلیدی این کتابخانه شامل موارد زیر است:
- مدیریت سوراخ‌ها (Holes): برای چندضلعی‌هایی که دارای حیاط یا فضاهای خالی درون خود هستند (مانند محوطه‌ها)، الگوریتم با ایجاد یک پل (Bridge) سوراخ‌ها را به حلقه بیرونی متصل می‌کند تا کل ساختار به یک حلقه واحد تبدیل شود.
- آزمون تنها روی نقاط فرورفته (Dents): بجز بررسی تمام راس‌ها برای تست گوش بودن، سیستم تنها راس‌های فرورفته (Reflex vertices) را بررسی می‌کند، چرا که فقط آن‌ها می‌توانند مانع از گوش بودن یک زاویه شوند.
- رد کردن چندضلعی‌های محدب (Convex): چندضلعی‌های بدون فرورفتگی به هیچ آزمونی نیاز ندارند و مستقیماً پردازش می‌شوند.
- تولید نوارها (Strips): به‌جای ذخیره سه ایندکس برای هر مثلث منفرد، الگوریتم از نوارهای مثلثی (Triangle Strips) استفاده می‌کند تا حجم ایندکس‌ها کاهش یابد و رندرing بهینه‌تر شود.
چرا این مسئله برای مهندسان اهمیت دارد؟
این مقاله نشان می‌دهد که چگونه بررسی دقیق پروفایل عملکرد و حذف محاسبات غیرضروری (مثلست‌بندی سنگین برای چندضلعی‌های ساده) می‌تواند کارایی اپلیکیشن‌های سمت کاربر و پردازش‌های سنگین جغرافیایی را متحول کند. کتابخانه earstrip نشان داد که در محیط C++ حدود ۱۴ درصد سریع‌تر از earcut.hpp عمل می‌کند و این سرعت در مرورگر و به کمک WebAssembly بین ۱.۴ تا ۲.۱ برابر نسخه جاوااسکریپتی earcut.js است.
این مطلب به‌صورت کاملاً خودکار و با هوش مصنوعی از مقالهٔ اصلی و بحث هکرنیوز تهیه شده و ممکن است خطا داشته باشد. حقوق مطلب اصلی متعلق به نویسندهٔ آن است. قوانین و گزارش مشکل