نقطة داخل مضلع

في الهندسة الحسابية ، تسأل مسألة تحديد موقع نقطة داخل مضلع ( PIP ) عما إذا كانت نقطة معينة في المستوى تقع داخل مضلع أو خارجه أو على حدوده . وهي حالة خاصة من مسائل تحديد موقع النقاط ، وتجد تطبيقات في مجالات تتعامل مع معالجة البيانات الهندسية، مثل رسومات الحاسوب ، ورؤية الحاسوب ، ونظم المعلومات الجغرافية (GIS)، وتخطيط الحركة ، والتصميم بمساعدة الحاسوب (CAD).

يُظهر وصف مبكر للمشكلة في رسومات الحاسوب نهجين شائعين ( إسقاط الأشعة وجمع الزوايا) قيد الاستخدام في وقت مبكر من عام 1974. ^{[ 1 ]}

يمكن الاطلاع على محاولة من قبل خبراء رسومات الحاسوب لتتبع تاريخ المشكلة وبعض الحيل لحلها في عدد من مجلة Ray Tracing News . ^{[ 2 ]}

خوارزمية إسقاط الأشعة

عدد نقاط تقاطع شعاع يمر من خارج المضلع إلى أي نقطة: إذا كان العدد فرديًا، فهذا يدل على أن النقطة تقع داخل المضلع؛ وإذا كان زوجيًا، فهذا يدل على أن النقطة تقع خارجه. ينطبق هذا الاختبار أيضًا في ثلاثة أبعاد.

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

تُعرف هذه الخوارزمية أحيانًا باسم خوارزمية عدد التقاطعات أو خوارزمية قاعدة الزوجي والفردي ، وقد عُرفت منذ عام 1962. ^[³^] تعتمد الخوارزمية على ملاحظة بسيطة مفادها أنه إذا تحركت نقطة على طول شعاع من اللانهاية إلى نقطة القياس، ثم عبرت حدود مضلع، ربما عدة مرات، فإنها تنتقل بالتناوب من الخارج إلى الداخل، ثم من الداخل إلى الخارج، وهكذا. ونتيجة لذلك، بعد كل عبورين للحدود، تعود النقطة المتحركة إلى الخارج. ويمكن إثبات هذه الملاحظة رياضيًا باستخدام نظرية منحنى جوردان .

دقة محدودة

إذا طُبِّقَت هذه الخوارزمية على حاسوب ذي دقة حسابية محدودة ، فقد تكون النتائج غير صحيحة إذا كانت النقطة قريبة جدًا من الحد، وذلك بسبب أخطاء التقريب. بالنسبة لبعض التطبيقات، مثل ألعاب الفيديو أو غيرها من المنتجات الترفيهية، لا يُعدّ هذا الأمر مصدر قلق كبير لأنها غالبًا ما تُفضِّل السرعة على الدقة. مع ذلك، لكي يكون البرنامج الحاسوبي صحيحًا من الناحية النظرية ، يجب تحديد هامش سماحية عددية ε، واختبار ما إذا كانت النقطة P تقع ضمن ε من الخط L ، وفي هذه الحالة يجب أن تتوقف الخوارزمية وتُبلغ بأن " P تقع قريبة جدًا من الحد".

معظم تطبيقات خوارزمية إسقاط الأشعة تتحقق تباعًا من تقاطعات الشعاع مع جميع أضلاع المضلع. في هذه الحالة، يجب معالجة المشكلة التالية: إذا مر الشعاع تمامًا عبر رأس من رؤوس المضلع، فإنه سيتقاطع مع قطعتين مستقيمتين عند طرفيهما. بينما يكون هذا مقبولًا في حالة الرأس العلوي في المثال أو الرأس الواقع بين نقطتي التقاطع 4 و5، فإن حالة الرأس الأيمن (في المثال) تتطلب احتساب تقاطع واحد لكي تعمل الخوارزمية بشكل صحيح. تظهر مشكلة مماثلة مع القطع المستقيمة الأفقية التي تقع على الشعاع. يتم حل هذه المشكلة كما يلي: إذا كانت نقطة التقاطع رأسًا من رؤوس أحد أضلاع المضلع المختبر، فإن التقاطع يُحتسب فقط إذا كان الرأس الآخر من الضلع يقع أسفل الشعاع. هذا يُعادل فعليًا اعتبار رؤوس الشعاع وكأنها تقع فوقه قليلًا .

مرة أخرى، قد تُثير حالة مرور شعاع عبر رأسٍ ما مشاكل حسابية في العمليات الحسابية ذات الدقة المحدودة : فبالنسبة لضلعين متجاورين لنفس الرأس، قد لا يُعطي الحساب المباشر لنقطة التقاطع مع الشعاع الرأسَ في كلتا الحالتين. إذا تم تحديد المضلع برؤوسه، يُمكن التغلب على هذه المشكلة بالتحقق من إحداثيات y للشعاع ونهايتي ضلع المضلع المُختَبَر قبل الحساب الفعلي لنقطة التقاطع. في حالات أخرى، عندما تُحسب أطوال أضلاع المضلع من أنواع بيانات أخرى، يجب تطبيق حيل أخرى لضمان متانة الخوارزمية من الناحية العددية.

خوارزمية رقم اللف

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

إحدى طرق حساب عدد اللفات هي جمع الزوايا المحصورة بين كل ضلع من أضلاع المضلع. ^{[ 4 ]} مع ذلك، تتضمن هذه الطريقة دوال مثلثية عكسية مكلفة ، مما يجعل أداء هذه الخوارزمية أقل كفاءة (أبطأ) مقارنةً بخوارزمية إسقاط الأشعة. لحسن الحظ، لا حاجة لحساب هذه الدوال المثلثية العكسية، لأن مجموع جميع الزوايا يمكن أن يساوي صفرًا أو $2\pi$ (أو مضاعفات $2\pi$ ) فقط، يكفي تتبع الأرباع التي يمر بها المضلع، ^{[ 5 ]} أثناء دورانه حول نقطة الاختبار، مما يجعل خوارزمية عدد اللفات قابلة للمقارنة في السرعة مع حساب عبور الحدود.

طوّر دان صنداي في عام 2001 خوارزمية محسّنة لحساب عدد اللفات. ^{[ 6 ]} لا تستخدم هذه الخوارزمية الزوايا في حساباتها، ولا أي حسابات مثلثية، وتعمل تمامًا مثل خوارزميات إسقاط الأشعة المذكورة أعلاه. تعتمد خوارزمية صنداي على افتراض شعاع أفقي لانهائي مُسقط من النقطة المراد فحصها. عندما يتقاطع هذا الشعاع مع أحد أضلاع المضلع، تُستخدم خوارزمية خوان بينيدا لتقاطع الأضلاع (1988) ^{[ 7 ]} لتحديد تأثير هذا التقاطع على عدد اللفات. وكما يوضح صنداي، إذا تقاطع الشعاع مع الحافة متجهًا للأعلى، يزداد عدد اللفات؛ وإذا تقاطع مع الحافة متجهًا للأسفل، ينقص العدد. تُعطي خوارزمية صنداي الإجابة الصحيحة للمضلعات غير البسيطة، بينما تفشل خوارزمية تقاطع الحدود في هذه الحالة. ^{[ 6 ]}

طريقة المضلع المعدل

تغطي طريقة المضلع المعدلة، التي نُشرت عام 2019، الحالات المحدبة والمقعرة على حد سواء، وتعتمد على التعريف الأساسي لحجم المضلع (خط/مساحة/حجم) بناءً على الأبعاد المكانية للشكل. والنتيجة هي طريقة سريعة ودقيقة للغاية مقارنةً بالتقنيات الحالية. ^{[ 8 ]}

التطبيقات

SVG

تُستخدم أساليب مشابهة في SVG لتحديد طريقة تلوين الأشكال المختلفة (مثل المسارات والخطوط المتعددة والمضلعات والنصوص، إلخ). ^{[ 9 ]} تتأثر خوارزمية التلوين بالخاصية "fill-rule". قد تكون قيمتها إما فارغة nonzeroأو غير evenoddفارغة. على سبيل المثال، في النجمة الخماسية ، توجد "فتحة" مركزية (خلفية مرئية) عند استخدام الخاصية فارغة evenodd، ولا توجد فتحة عند استخدام nonzeroالخاصية غير الفارغة. ^{[ 10 ]}

بالنسبة للمضلعات البسيطة ، تُعطي الخوارزميات النتيجة نفسها. أما بالنسبة للمضلعات المعقدة ، فقد تُعطي الخوارزميات نتائج مختلفة للنقاط في المناطق التي يتقاطع فيها المضلع مع نفسه، حيث لا يكون للمضلع حدود داخلية وخارجية واضحة. أحد الحلول باستخدام قاعدة الزوجي-الفردي هو تحويل المضلعات (المعقدة) إلى مضلعات أبسط مكافئة لها في قاعدة الزوجي-الفردي قبل فحص التقاطع. ^{[ 11 ]} إلا أن هذا الحل مُكلف حسابيًا. يُعد استخدام خوارزمية عدد اللفات غير الصفرية السريعة أقل تكلفة، إذ تُعطي النتيجة الصحيحة حتى عندما يتداخل المضلع مع نفسه.

استعلامات النقاط داخل المضلع

يمكن النظر إلى مسألة تحديد موقع نقطة داخل مضلع ضمن سياق الاستعلام الهندسي المتكرر العام : عند إعطاء مضلع واحد وسلسلة من نقاط الاستعلام، يتم إيجاد الإجابات لكل نقطة استعلام بسرعة. من الواضح أنه يمكن استخدام أي من الطرق العامة لتحديد موقع النقاط المستوية . تتوفر حلول أبسط لبعض المضلعات الخاصة.

حالات خاصة

توجد خوارزميات أبسط للمضلعات الرتيبة ، والمضلعات النجمية الشكل ، والمضلعات المحدبة ، والمثلثات .

يمكن حل حالة المثلث بسهولة باستخدام نظام إحداثيات مركزي ، أو معادلة وسيطية ، أو الضرب النقطي . ^{[ 12 ]} تمتد طريقة الضرب النقطي بشكل طبيعي إلى أي مضلع محدب.

مراجع

↑ إيفان ساذرلاند وآخرون، "توصيف لعشر خوارزميات للسطح المخفي" 1974، ACM Computing Surveys المجلد 6 العدد 1.
↑ مارك فاندويتيرينغ؛ إريك هاينز؛ إدوارد جون كاليندا؛ وآخرون . (1 أكتوبر 1990)، "نقطة في مضلع، مرة أخرى..." ، أخبار تتبع الأشعة ، 3 (4)
↑ شيمرات، م.، "الخوارزمية 112: موضع النقطة بالنسبة للمضلع"، 1962، مجلة اتصالات رابطة مكائن الحوسبة، المجلد 5، العدد 8، أغسطس 1962. https://dl.acm.org/doi/10.1145/368637.368653
↑ هورمان، ك.؛ أغاثوس، أ. (2001). "مسألة النقطة في المضلع للمضلعات العشوائية" . الهندسة الحسابية . 20 (3): 131. doi : 10.1016/S0925-7721(01)00012-8 .
↑ ويلر، كيفن (1994)، "اختبار نقطة الزاوية المتزايدة في المضلع"، في هيكبرت، بول س. (محرر)، جواهر الرسومات IV ، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية: أكاديميك برس بروفيشنال، ص 16-23 ، ISBN 0-12-336155-9
1 2 صنداي، دان (2001). "تضمين نقطة في مضلع" . مؤرشف من الأصل في 26 يناير 2013.
↑ بينيدا، خوان (أغسطس 1988). خوارزمية متوازية لتحويل المضلعات إلى صور نقطية (ملف PDF) . سيغراف 88. رسومات الحاسوب . المجلد 22، العدد 4. أتلانتا . تاريخ الاسترجاع: 8 أغسطس 2021 .
↑ السلاموني، مصطفى (2019). "طريقة المضلع المعدلة لمسألة النقطة داخل المضلع" (ملف PDF) . المؤتمر الأوروبي الثامن لعلوم الطيران والفضاء (EUCASS) . 1 (1): 1-9 .
↑ "الرسم: التعبئة، والتحديد، والألوان، وخوادم الألوان - SVG Tiny 1.2" . www.w3.org . تم الاطلاع عليه بتاريخ 24 يوليو 2021 .
↑ "الرسم: التعبئة، والتحديد، والألوان، وخوادم الألوان - SVG Tiny 1.2" . www.w3.org . تم الاطلاع عليه بتاريخ 24 يوليو 2021 .
↑ مايكل غاليتزكا، باتريك غلاونر (2017). خوارزمية بسيطة وصحيحة للأعداد الزوجية والفردية لمسألة النقطة داخل المضلع للمضلعات المعقدة . وقائع المؤتمر الدولي المشترك الثاني عشر حول رؤية الحاسوب والتصوير ونظرية وتطبيقات رسومات الحاسوب ( VISIGRAPP 2017)، المجلد 1: GRAPP.
↑ تحديد النقطة الدقيقة في اختبار المثلث " ...أشهر الطرق لحله "

انظر أيضاً

مجموعة أدوات طوبولوجيا جافا (JTS)
للمناقشة: https://www.ics.uci.edu/~eppstein/161/960307.html
طرق حساب عدد اللفات مقابل عدد التقاطعات: https://web.archive.org/web/20131210180851/http://geomalgorithms.com/a03-_inclusion.html ، متوفرة أيضاً على Scribd https://www.scribd.com/document/735206906/Inclusion-of-a-Point-in-a-Polygon (يتطلب اشتراكاً).

[1] إيفان ساذرلاند وآخرون، "توصيف لعشر خوارزميات للسطح المخفي" 1974، ACM Computing Surveys المجلد 6 العدد 1.

[2] مارك فاندويتيرينغ؛ إريك هاينز؛ إدوارد جون كاليندا؛ وآخرون . (1 أكتوبر 1990)، "نقطة في مضلع، مرة أخرى..." ، أخبار تتبع الأشعة ، 3 (4)

[3] شيمرات، م.، "الخوارزمية 112: موضع النقطة بالنسبة للمضلع"، 1962، مجلة اتصالات رابطة مكائن الحوسبة، المجلد 5، العدد 8، أغسطس 1962. https://dl.acm.org/doi/10.1145/368637.368653

[Hormann-4] هورمان، ك.؛ أغاثوس، أ. (2001). "مسألة النقطة في المضلع للمضلعات العشوائية" . الهندسة الحسابية . 20 (3): 131. doi : 10.1016/S0925-7721(01)00012-8 .

[5] ويلر، كيفن (1994)، "اختبار نقطة الزاوية المتزايدة في المضلع"، في هيكبرت، بول س. (محرر)، جواهر الرسومات IV ، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية: أكاديميك برس بروفيشنال، ص 16-23 ، ISBN 0-12-336155-9

[sunday-6] 1 2 صنداي، دان (2001). "تضمين نقطة في مضلع" . مؤرشف من الأصل في 26 يناير 2013.

[7] بينيدا، خوان (أغسطس 1988). خوارزمية متوازية لتحويل المضلعات إلى صور نقطية (ملف PDF) . سيغراف 88. رسومات الحاسوب . المجلد 22، العدد 4. أتلانتا . تاريخ الاسترجاع: 8 أغسطس 2021 .

[8] السلاموني، مصطفى (2019). "طريقة المضلع المعدلة لمسألة النقطة داخل المضلع" (ملف PDF) . المؤتمر الأوروبي الثامن لعلوم الطيران والفضاء (EUCASS) . 1 (1): 1-9 .

[9] "الرسم: التعبئة، والتحديد، والألوان، وخوادم الألوان - SVG Tiny 1.2" . www.w3.org . تم الاطلاع عليه بتاريخ 24 يوليو 2021 .

[10] "الرسم: التعبئة، والتحديد، والألوان، وخوادم الألوان - SVG Tiny 1.2" . www.w3.org . تم الاطلاع عليه بتاريخ 24 يوليو 2021 .

[11] مايكل غاليتزكا، باتريك غلاونر (2017). خوارزمية بسيطة وصحيحة للأعداد الزوجية والفردية لمسألة النقطة داخل المضلع للمضلعات المعقدة . وقائع المؤتمر الدولي المشترك الثاني عشر حول رؤية الحاسوب والتصوير ونظرية وتطبيقات رسومات الحاسوب ( VISIGRAPP 2017)، المجلد 1: GRAPP.

[12] تحديد النقطة الدقيقة في اختبار المثلث " ...أشهر الطرق لحله "

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗