الهندسة الحسابية في بايثون: من النظرية إلى التطبيق

عندما يفكر الناس في الهندسة الحسابية ، من واقع خبرتي ، فإنهم يفكرون عادةً في أحد أمرين:

1. واو ، هذا يبدو معقدًا.
2. أوه نعم ، بدن محدب.

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

ما كل هذا العناء؟

في حين يتم تضمين خوارزميات الهندسة الحاسوبية للبدن المحدب عادةً في دورة الخوارزميات التمهيدية ، تعد الهندسة الحسابية موضوعًا أكثر ثراءً ونادرًا ما يحظى باهتمام كافٍ من المطور العادي / عالم الكمبيوتر (ما لم تكن تصنع ألعابًا أو شيء من هذا القبيل).

مثير للفضول من الناحية النظرية ...

من وجهة النظر النظرية ، غالبًا ما تكون الأسئلة في الهندسة الحسابية مثيرة جدًا للاهتمام ؛ الإجابات مقنعة. وتنوعت المسارات التي يتم الوصول إليها. هذه الصفات وحدها تجعله مجالًا يستحق الدراسة ، في رأيي.

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

عندما نترجم هذا إلى تدوين هندسي حسابي ، فإن "مخطط الأرضية" للمعرض هو مجرد مضلع بسيط. وباستخدام بعض دهن الكوع ، يمكننا إثبات أن الكاميرات n / 3 كافية دائمًا لمضلع على رؤوس n ، بغض النظر عن مدى فوضى ذلك. يستخدم الإثبات نفسه الرسوم البيانية المزدوجة ، وبعض نظريات الرسم البياني ، والمثلثات ، وأكثر من ذلك.

هنا ، نرى تقنية برهان ذكية ونتيجة مثيرة للفضول بما يكفي لتقديرها بمفردها. ولكن إذا لم تكن الملاءمة النظرية كافية بالنسبة لك ...

ومهم في الممارسة

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

لماذا هو صعب جدا؟

لنأخذ مسألة هندسة حسابية مباشرة إلى حد ما: عند إعطاء نقطة ومضلع ، هل تقع النقطة داخل المضلع؟ (وهذا ما يسمى مشكلة النقطة في المضلع ، أو مشكلة PIP.)

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

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

 poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point)

ما هو بديهي للعقل البشري لا يترجم بسهولة إلى لغة الكمبيوتر.

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

صعب ولكنه ليس مستحيلاً. على سبيل المثال ، يمكنك تشديد النقطة في المضلع بالتعريفات التالية:

• تكون النقطة داخل مضلع إذا تقاطع أي شعاع لانهائي يبدأ عند النقطة مع عدد فردي من حواف المضلع (المعروفة باسم قاعدة زوجي-فردي).
• تكون النقطة داخل مضلع إذا كان له رقم متعرج غير صفري (يُعرَّف بأنه عدد المرات التي ينتقل فيها المنحنى الذي يحدد المضلع حول النقطة).

ما لم تكن لديك بعض الخبرة في الهندسة الحسابية ، فمن المحتمل ألا تكون هذه التعريفات جزءًا من مفرداتك الحالية. وربما يكون هذا رمزًا للكيفية التي يمكن أن تدفعك بها الهندسة الحسابية للتفكير بشكل مختلف .

إدخال اتفاقية الأسلحة التقليدية

الآن بعد أن أصبح لدينا إحساس بأهمية وصعوبة مشاكل الهندسة الحسابية ، فقد حان الوقت لتبليل أيدينا.

يوجد في العمود الفقري للموضوع عملية بدائية قوية بشكل مخادع: عكس اتجاه عقارب الساعة ، أو اختصارًا "CCW". (سأحذرك الآن: ستظهر اتفاقية الأسلحة التقليدية مرارًا وتكرارًا.)

يأخذ CCW ثلاث نقاط A و B و C كوسيطات ويسأل: هل تؤلف هذه النقاط الثلاث انعطافًا في عكس اتجاه عقارب الساعة (مقابل انعطاف في اتجاه عقارب الساعة)؟ بمعنى آخر ، هل أ -> ب -> ج زاوية عكس اتجاه عقارب الساعة؟

على سبيل المثال ، النقاط الخضراء هي CCW ، بينما النقاط الحمراء ليست:

لماذا مسائل اتفاقية الأسلحة التقليدية

يمنحنا قانون الأسلحة التقليدية عملية بدائية يمكننا البناء عليها. إنه يعطينا مكانًا لبدء صرامة وحل مشكلات الهندسة الحسابية.

لإعطائك فكرة عن قوتها ، دعنا نفكر في مثالين.

تحديد التحدب

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

بشكل حدسي ، هذه الفجوة منطقية: الأشكال المحدبة "لطيفة" ، بينما الأشكال المقعرة يمكن أن يكون لها حواف حادة بارزة من الداخل والخارج - فهي لا تتبع نفس القواعد.

تتمثل إحدى خوارزمية الهندسة الحسابية البسيطة (ولكن غير الواضحة) لتحديد التحدب في التحقق من أن كل ثلاثة رؤوس متتالية هي CCW. لا يتطلب هذا سوى بضعة أسطر من كود Python الهندسي (بافتراض أن points يتم تقديمها بترتيب عكس اتجاه عقارب الساعة - إذا كانت points بترتيب اتجاه عقارب الساعة ، فستريد أن تكون جميع المجموعات الثلاثية في اتجاه عقارب الساعة):

 class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True

جرب هذا على الورق مع بعض الأمثلة. يمكنك حتى استخدام هذه النتيجة لتحديد التحدب. (لجعل الأمور أكثر سهولة ، لاحظ أن منحنى CCW من A -> B -> C يتوافق مع زاوية أقل من 180 ، وهي طريقة مدروسة على نطاق واسع لتعريف التحدب.)

تقاطع الخط

كمثال ثان ، ضع في اعتبارك تقاطع مقطع خط ، والذي يمكن حله أيضًا باستخدام اتفاقية الأسلحة التقليدية وحدها:

 def intersect(a1, b1, a2, b2): """Returns True if line segments a1b1 and a2b2 intersect.""" return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1)

لماذا هذا هو الحال؟ يمكن أيضًا صياغة تقاطع قطعة مستقيمة على النحو التالي: بالنظر إلى مقطع بنقطتي نهاية A و B ، هل تقع نقطتا النهاية C و D لقطعة أخرى على نفس الجانب من AB؟ بمعنى آخر ، إذا كانت المنعطفات من A -> B -> C و A -> B -> D في نفس الاتجاه ، فلا يمكن أن تتقاطع المقاطع. عندما نستخدم هذا النوع من اللغة ، يتضح لنا أن هذه المشكلة تكمن في الخبز والزبدة في اتفاقية الأسلحة التقليدية.

تعريف صارم

الآن بعد أن تذوقنا أهمية اتفاقية الأسلحة التقليدية ، دعونا نرى كيف يتم حسابها. بالنظر إلى النقاط A و B و C:

 def ccw(A, B, C): """Tests whether the turn formed by A, B, and C is ccw""" return (Bx - Ax) * (Cy - Ay) > (By - Ay) * (Cx - Ax)

لفهم من أين يأتي هذا التعريف ، ضع في اعتبارك المتجهين AB و BC. إذا أخذنا حاصل الضرب الاتجاهي ، AB x BC ، فسيكون هذا متجهًا على المحور z. لكن في أي اتجاه (على سبيل المثال ، + z أو -z)؟ كما اتضح ، إذا كان المنتج العرضي موجبًا ، يكون الدوران عكس اتجاه عقارب الساعة ؛ خلاف ذلك ، فهو في اتجاه عقارب الساعة.

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

غوصتي في الهندسة والبرمجة الحاسوبية باستخدام بايثون

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

ملاحظة: تجربتي محدودة باعتراف الجميع. نظرًا لأنني أعمل على هذه الأشياء لأشهر بدلاً من سنوات ، خذ نصيحتي بحذر. بعد قولي هذا ، تعلمت الكثير في تلك الأشهر القليلة ، لذلك آمل أن تكون هذه النصائح مفيدة.

خوارزمية كيركباتريك

كان جوهر عملي هو تطبيق خوارزمية كيركباتريك لتحديد موقع النقطة. سيكون بيان المشكلة شيئًا مثل: بالنظر إلى تقسيم فرعي مستو (مجموعة من المضلعات غير المتداخلة في المستوى) والنقطة P ، أي مضلع يحتوي على P؟ فكر في مضلع النقطة في المنشطات - بدلاً من مضلع واحد ، لديك مستوى كامل منها.

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

بينما لن أناقش الخوارزمية بتعمق ، يمكنك معرفة المزيد هنا.

مثلث الحد الأدنى

كمهمة فرعية ، قمت أيضًا بتطبيق خوارزمية O'Rourke لحساب الحد الأدنى من مثلث الإحاطة / المحيط (أي العثور على أصغر مثلث يحتوي على مجموعة محدبة من النقاط) في الوقت الخطي.

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

نصائح عملية وتطبيقات ومخاوف

ركزت الأقسام السابقة على سبب صعوبة التفكير في الهندسة الحسابية بدقة.

في الممارسة العملية ، علينا التعامل مع مجموعة جديدة كاملة من المخاوف.

تذكر CCW؟ كقصة لطيفة ، دعنا نرى واحدة أخرى من صفاتها العظيمة: إنها تحمينا من مخاطر أخطاء الفاصلة العائمة.

أخطاء النقطة العائمة: لماذا تعتبر اتفاقية الأسلحة التقليدية ملكًا

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

لماذا ا؟ الزوايا فوضوية. الزوايا "قذرة". عندما يتعين عليك حساب زاوية ، فأنت بحاجة إلى القسمة أو استخدام بعض التقريب (أي شيء يتضمن Pi ، على سبيل المثال) أو بعض الدوال المثلثية.

عندما يتعين عليك حساب زاوية في الكود ، فستكون تقريبًا دائمًا تقريبًا. ستكون بعيدًا عن بعض درجات الدقة الفاصلة العائمة الصغيرة - وهو أمر مهم عند اختبار المساواة. يمكنك حل نقطة ما في المستوى من خلال طريقتين مختلفتين ، وبالطبع تتوقع أن p1.x == p2.x and p1.y == p2.y لكن ، في الواقع ، سيفشل هذا الفحص كثيرًا . علاوة على ذلك (ومن الواضح تمامًا) ، سيكون لهذه النقاط بعد ذلك تجزئات مختلفة.

لجعل الأمور أسوأ ، ستزداد درجة الخطأ مع انتشار الاختلافات الصغيرة من خلال حساباتك. (بالنسبة لبعض الأمثلة العلمية ، تتناول هذه الورقة ما يمكن أن يحدث خطأ عند حساب الهيكل المحدب أو تثليث Delaunay.)

اذا مالذي يمكننا القيام به حيال ذلك؟

تقريبا

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

 # Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print "Error!" # Error!

في الواقع ، سيطبع هذا الرمز "خطأ!" ما يقرب من 70٪ من الوقت (تجريبيًا). يمكننا معالجة هذا القلق بأن نكون أكثر تساهلاً مع تعريفنا للمساواة ؛ أي بالتضحية بدرجة من الدقة.

أحد الأساليب التي استخدمتها (وشاهدتها ، على سبيل المثال ، بعض وحدات OpenCV النمطية) هو تحديد رقمين على أنهما متساويان إذا كانا يختلفان فقط عن طريق بعض epsilon ذي القيمة الصغيرة. في بايثون ، قد يكون لديك:

 def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) < EPSILON class Point(object): ... def __eq__(self, that): return (almostEqual(self.x, that.x) and almostEqual(self.y, that.y))

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

 class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept))

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

CCW هو الملك

على مستوى أعلى ، من الصعب (يمكن القول) أن نحدد حلولنا من حيث الكميات الحسابية الدقيقة مثل الزوايا أو إحداثيات النقاط. بدلاً من معالجة الأعراض بمفردها (أي غسل أخطاء الفاصلة العائمة مع almostEqual ) ، لماذا لا تعالج السبب؟ الحل: بدلاً من التفكير من منظور الزوايا ، فكر في اتفاقية الأسلحة التقليدية ، والتي ستساعد على تجريد المخاوف المرتبطة بحساب النقطة العائمة.

إليك مثالًا ملموسًا: لنفترض أن لديك بعض المضلع المحدب P ، والرأس v ، ونقطة ما خارج المضلع . كيف يمكنك معرفة ما إذا كان الخط فوق البنفسجي يتقاطع مع P أعلى أو أسفل v ، أم لا على الإطلاق ، في وقت ثابت؟

سيكون حل القوة الغاشمة (إلى جانب كونه وقتًا خطيًا ، وليس ثابتًا) مشكلة حيث سيتعين عليك حساب بعض نقاط تقاطع الخط الدقيقة.

يتضمن نهج الوقت الثابت الذي رأيته ما يلي:

• حساب بعض الزوايا باستخدام arctan2 .
• تحويل هذه الزوايا إلى درجات بالضرب في 180 / Pi.
• فحص العلاقات بين هذه الزوايا المختلفة.

لحسن الحظ ، استخدم المؤلف تقنية almostEqual أعلاه للتخفيف من أخطاء الفاصلة العائمة.

في رأيي ، سيكون من الأفضل تجنب مشكلة أخطاء الفاصلة العائمة تمامًا. إذا استغرقت بضع دقائق للنظر في المشكلة على الورق ، فيمكنك الحصول على حل يعتمد بالكامل على اتفاقية الأسلحة التقليدية. الحدس: إذا كانت الرؤوس المجاورة لـ v على نفس الجانب من الأشعة فوق البنفسجية ، فإن الخط لا يتقاطع ؛ وإلا ، انظر إذا كان u و v على نفس الجانب من الخط الفاصل بين الرؤوس المتجاورة ، واعتمادًا على النتيجة ، قارن ارتفاعاتهما.

إليك كود Python لاختبار التقاطع أعلاه v (التقاطع أدناه يعكس اتجاه المقارنات):

 def intersectsAbove(verts, v, u): """ Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. """ n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return uy > verts[v].y else: return uy < verts[v].y

الحل ليس واضحًا على الفور للعين المجردة ، لكنه بلغة خوارزمية هندسية حسابية: "نفس الجانب من الخط" هو عنصر كلاسيكي من تلك الخوارزمية الموثوقة.

فعل خير من الكمال

في الأدبيات الهندسية الحسابية ، غالبًا ما يكون هناك قدر لا بأس به من السحر الذي يشارك في عمليات تبدو بسيطة. يمنحك هذا خيارًا: يمكنك القيام بالأشياء بالطريقة الصعبة ، باتباع بعض الأوراق التي تحدد حلاً متقدمًا بشكل لا يصدق لمشكلة غير متقدمة جدًا - أو يمكنك القيام بالأشياء بالطريقة السهلة بقليل من القوة الغاشمة.

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

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

على سبيل المثال ، قد نفقد مرتين ونجد عينة صالحة في النقطة الثالثة فقط:

ها هو الكود:

 class Polygon(object): ... def interiorPoint(self): """Returns a random point interior point""" min_x = min([px for p in self.points]) max_x = max([px for p in self.points]) min_y = min([py for p in self.points]) max_y = max([py for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True

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

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

1. قم بتثليث المضلع الخاص بك (على سبيل المثال ، قسّمه إلى مثلثات).
2. اختر مثلثًا باحتمالية تناسب مساحته.
3. خذ نقطة عشوائية من داخل المثلث المختار (عملية ثابتة الوقت).

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

 from p2t import CDT class Triangle(object): ... def area(self): return abs((Bx * Ay - Ax * By) + (Cx * By - Bx * Cy) + (Ax * Cy - Cx * Ay)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(tax, tay) B = Point(tbx, tby) C = Point(tcx, tcy) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint()

نأمل أن يكون الجهد الإضافي واضحًا من الكود. تذكر: كما يقولون في Facebook ، "القيام به أفضل من الكمال". الشيء نفسه ينطبق على مشاكل الهندسة الحسابية.

الاختبار المرئي والآلي

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

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

من الصعب للغاية التحقق من أن هذا التثليث قد تم تنفيذه بشكل صحيح من خلال الكود ، ولكنه يتضح على الفور للعين البشرية. ملاحظة: أقترح بشدة استخدام Matplotlib للمساعدة في الاختبار البصري - هناك دليل جيد هنا.

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

 class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target))

يمكننا بعد ذلك استخدام طريقة runLocator على مجموعات مختلفة من المضلعات ، مما يمنحنا مجموعة اختبار متنوعة جيدًا.

حلول مفتوحة المصدر

تحتوي الهندسة الحسابية على مجموعة رائعة من المكتبات والحلول مفتوحة المصدر المتاحة بغض النظر عن لغة البرمجة التي تختارها (على الرغم من أن مكتبات C ++ يبدو أنها تحقق قدرًا غير متناسب).

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

• poly2tri: مكتبة رائعة لعمليات المثلثات السريعة للمضلعات. يدعم أيضًا (وهذا غالبًا ما يكون حاسمًا) المضلعات التي بها ثقوب . مكتوب بلغة C ++ ، يحتوي poly2tri أيضًا على روابط Python وكان من السهل جدًا تشغيله وتشغيله. انظر طريقة triangulate الخاصة بي أعلاه للتعرف على استدعاءات الوظائف.
• scipy.spatial: تتضمن وظائف لحساب الهياكل المحدبة و Delaunay Triangulations والمزيد. سريع (كالعادة) ، موثوق ، إلخ. ملاحظة: وجدت أنه من المفيد استخدام نوع بيانات Point الخاص بي مع طريقة toNumpy : def np(self): return [self.x, self.y] . بعد ذلك ، يمكنني بسهولة استدعاء طرق scipy.spatial ، على سبيل المثال: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: تحتوي مكتبة رؤية الكمبيوتر مفتوحة المصدر على بعض الوحدات النمطية الرائعة للهندسة الحسابية المستقلة. على وجه الخصوص ، لقد استخدمت وظيفة مثلث التضمين الدنيا لفترة من الوقت قبل تنفيذها بنفسي.

خاتمة

آمل أن يكون هذا المنشور قد أعطاك طعمًا لجمال الهندسة الحسابية كمطور Python ، وهو موضوع غني بالمشاكل الرائعة والتطبيقات الرائعة بنفس القدر.

من الناحية العملية ، تقدم التطبيقات الهندسية الحسابية تحديات فريدة ستدفعك لممارسة مهارات جديدة ومثيرة في حل المشكلات.

إذا كنت مهتمًا بمعرفة المزيد أو لديك أي أسئلة ، فيمكن التواصل معي على [email protected].