حساب محيط الغلاف المحدب للنقاط الديكارتية

أدخلوا نقاطًا ديكارتية ضمن نظام إحداثيات موحد

أرسلوا النقاط في صورة سجلات تحتوي على إحداثيين عدديين منتهيين x وy. يجب أن تستخدم جميع النقاط نظام الإحداثيات الديكارتي نفسه ووحدة القياس نفسها. إذا كانت الإحداثيات بالأمتار كان المحيط بالأمتار، وإذا كانت بالبكسل كانت النتيجة بالبكسل. لا تحول الحاسبة خطوط العرض والطول إلى إسقاط خرائطي ولا تراعي انحناء الأرض، ولذلك ينبغي تحويل البيانات الجغرافية أولًا إلى نظام إسقاط مناسب عند الحاجة إلى مسافة فعلية. لا يؤثر ترتيب الإدخال في النتيجة، لأن الخوارزمية ترتب الإحداثيات قبل بناء الحد. تُقبل الإحداثيات المتكررة وتُحذف لأغراض الحساب الهندسي، مع بقاء عدد نقاط الإدخال الأصلي وعدد النقاط الفريدة ظاهرين في الاستجابة. يلزم إدخال نقطة واحدة على الأقل، والحد الأقصى المعلن هو 100,000 سجل. يحول الاحتفاظ بالدقة الأصلية دون التقريب المبكر قبل حساب المسافات. يبدأ الغلاف من أصغر نقطة حدية وفق الترتيب المعجمي ويتقدم عكس اتجاه عقارب الساعة، وبذلك يعطي تمثيلًا ثابتًا قابلًا لإعادة الإنتاج.

تعرفوا على طريقة حساب الحد والمحيط

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

اقرؤوا النتيجة واستخدموها على نحو سليم

يعرض الحقل perimeter طول الحد الكامل بالوحدة نفسها المستخدمة في إحداثيات الإدخال. وتسرد المصفوفة hull الرؤوس الحدية المحتفظ بها وفق ترتيب المرور، من دون تكرار النقطة الأولى في النهاية. كما تتضمن الاستجابة الحقول input_points وunique_points وhull_points، وهي تساعدكم على فهم سبب غياب النقاط الداخلية أو المكررة أو الوسطية الواقعة على خط واحد عن الحد. لرسم المضلع، صِلوا كل رأس بالرأس المجاور ثم أغلقوا المسار صراحةً من الأخير إلى الأول. نظرًا إلى استخدام حساب الفاصلة العائمة في JavaScript، قد تتضمن المسافات غير النسبية تقريبًا ثنائيًا طفيفًا معتادًا؛ لا تطبقوا التقريب إلا عند عرض النتيجة. تلائم الأداة المخططات المستوية وإحداثيات الصور والشبكات الهندسية المحلية وبيانات الخرائط المسقطة. وهي لا تحسب محيطًا جيوديسيًا كرويًا أو إهليلجيًا، ولا تصلح أخطاء النظام المرجعي، ولا تحتفظ بالنقاط الواقعة على خط واحد لمجرد العرض. تبلغ كلفة طلب API مقدار $0.002؛ ويستخدم التنفيذ في المتصفح منطق الحساب النقي نفسه لضمان اتساق النتائج بين القنوات.