المفاهيم الأساسية للهندسة الحسابية (1) computational geometry

الهندسة الحسابية computational geometry (CG) : هي فرع من فروع علوم الحاسب وتركز على الخوارزميات الهندسية ، وللهندسة الحسابية نوعان :

• الهندسة الحسابية التوافقية وتعرف ايضا بالهندسة الخوارزمية وتتعامل مع الاشكال الهندسية ككائنات منفصلة على سبيل المثال : نشرح مثال لطريق او شارع باستخدام الايمائات او النقاط (nods) وتوصيل هذه النقاط او الايمائات ببعضها البعض وهذه الايمائات تكون نقاط بيانية على محوري x-y  ونوجد المساحة بينها باستخدام الهندسة الحسابية

خريطة الجامعة

خريطة الهواتف

• الهندسة الحسابية العددية وتعرف ايضا بهندسة الآلات او التصميم الهندسي بالكمبيوتر (CAGD) او نمذجة الهندسة وتتعامل بالدرجة الأولى مع وصف كائنات العالم الحقيقي في نماذج متكافئة لحسابات الكمبيوتر في انظمة (CAD/CAM).

على سبيل المثال :  تمثيل جبل في صورة مثلث ثلاثي الابعاد ، اونمذجة وتمثيل الكافيين "القهوه"  ككسر جزئي مثلا!! ،، ونمثل هذه الامثلة على رسم بياني ولكن باضافة نقاط اضافية الى  محوري x-y منها محور z ويمثل الجزء العلوي دائما .

الرسوم البيانية من الممكن ان تستخدم في الهندسة الحسابية في طلب تنظيم البيانات ولإيجاد حلول للمشاكل المشتركة . 

صورة توضيحية "لكشك الهاتف"

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

الهندسة الحسابية من الممكن ايضا ان تستخدم الروبوتات بحيث ان الخوارزميات يمكن ان تصمم بطلب مساعدة الروبوتات لتجنب العقبات وتسمى " التخطيط الحركي او تخطيط الحركة motion planning" شاهد  "صورة خريطة الهواتف المرمزة بـb " هذا النوع من الخوارزميات يجعل من الروبوتات المستقله امر ممكن .

عندما تحتاج نوعين من البيانات الى الاشتراك او الاندماج، هذه العملية تسمى "overlay الغطاء" .

الغطاء  مفيد جدا للمواقع المختلفه لكل الخرائط .

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

• النقاط ، الخطوط ، الأشكال الهندسية

الشكل1-1

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

الخط الواحد collinear و متحد المستوى coplanar
الخط الواحد يكون ثلاث نقاط او اكثر على نفس الخط اما اذا كان غير ذلك يسمى خط غير واحد non collinear

الشكل السابق يعرض خطين (L&M) الخط L يمر من جميع النقاط a&B&c لذلك يمكننا القول بانه خط مستقيم اما في الخط الذي يعبر من خلال P&Q لا يمكننا القول انه خط واحد لانه لا يمر من جميع النقاط 

وعلى نفس المنوال فان النقاط والخطوط التي تمر خلال نفس الشكل الهندسي يمكننا تسميتها " متحد المستوى " اما اذا كانت لا تمر من خلال نفس الشكل الهندسي فتسمى غير متحد المستوى 

رسم المثال 1

مثال1: خذ اي ثلاثة نقاط non colinear A وB وC على ورقة كم خط مختلف تستطيع رسمها تمر من خلال النقاط ؟ وسم هذه الخطوط 

الحل : نستطيع رسم ثلاثة خطوط واسمائها AB,BC AND AC

مثال 2 :

من الصورة السابقة اجب عن الاتي : 

1. سم الخطوط الموازية للخط AB
2. هل الخط AO والنقطة R متحد المستوى coplanar ؟ ولماذا
3. هل النقاط A,S,B و R متحدة المستوى coplanar ؟ ولماذا
4. سم ثلاثة اشكال هندسية تمر من خلال A 

الحل : 

1. الخط CD ، الخط SR ، والخط PQ
2. نعم ، اي خط و نقطة خارجية تسمى متحد المستوى coplanar 
3. نعم ، الخطان المتوازيان دائما متحدة المستوى coplanar
4. ABCD,ADSP و ABPQ

line segment القطعة المستقيمة : 

القطعة المستقيمة هو جزء من الخط طوله ثابت بناء على نقطتي النهاية واللتان تستخدام لتسمية القطعة المستقيمة 

pq قطعة من الخط AB والخط يظم قطع غير محدودة واذا كانت هانك قطعتان على الخط لها نقطتي نهاية مشتركة يمكن اضافتها 

pq و والقطعة QR هما قطعتان على الخط l و لهما نقطة نهاية مشتركة q وبالتالي القطعة pq + والقطعة qr = القطعة PR 

على القطعة pr توجد النقطة M بالتالي القطعة PM + القطعة MR = القطعة PR او القطعة PM = القطعة MR تدل على ان القطعة pr = قطعتان pm = قطعتان MR وبعبارة اخرى تعني ان الـ M متساوية البعد من P و R وبالتالي M هي نقطة المنتصف للقطعة PR ، كل القطع لها نقطة انتصاف واحدة ووحيدة .

هل التالي صحيح ام خاطئ ؟ 

1. اي عدد للخطوط يمكنه المرور من خلال نقطة معطاة واحدة 
2. اذا كان هناك نقطتين تقعان على مسطح وهناك خط يربط بينهم يقع ايضا في نفس المسطح 
3. اي عدد من الخطوط يمكنها المرور من خلال نقطتين
4. خطان يمكنها التقاطع على اكثر من نقطة 
5. مسطحان يمكنها التقاطع على خطين 
6. اذا كان هناك خطين يمكن ان تقاطع مسطح يضم كلا الخطين 
7. القطعة المستقيمة لها نقطتي نهاية وبالتالي طول ثابت 
8. المسافة بين نقطة منتصف القطعة وبين نقطة نهاية واحدة من الممكن او غير الممكن ان تساوي المسافة لنقطة النهاية الاخرى 

الاجابات : 

1. صح
2. صح
3. خطأ ، خط واحد فقط يمكنه العبور من خلال نقطتين معطاة
4. خطأ ، خطان فقط يمكنها التقاطع على نقطة واحدة
5. خطأ، مسطحان يمكنها التقاطع على خط واحد 
6. صح
7. صح
8. خطأ ، نقطة المنتصف متساوية المسافة لكلا نهايتي القطعة

الشعاعات والزوايا rays and angles

الشعاع  له نقطة نهاية واحدة يمتد الى الاتجاه الاخر بشكل لانهائي ويتمثل بتسمية نقطة النهاية على المتجه او "الشعاع" وبتسمية النقاط الاخرى على المتجه ويرمز للشعاع بالرمز →

حرف j يمثل نقطة النهاية و k نقطة على الشعاع بالتالي يرمز للشعاع بالرمز ￫JK *ويكون السهم اعلى الحروف* ويمتد الشعاع الى اتجاه واحد فقط 

شعاعين متجهه الى اتجاهين مختلفين ولكن لها نقطة نهاية مشتركة على شكل زاوية ، نقطة النهاية المشتركة تسمى السمت  vertex  للزاوية واضلاع الشعاع او جوانبه تسمى arms والزاوية يرمز لها بالرمز ∟ وتتم تسميته باستخدام كلا جانبي الشعاعين او باستخدام الـ السمت vertex فقط 

بالتالي نرمز للشكل السابق اما بالرمز ┙xyz  او ┙Y حيث ان y هي الـ vertex

الزوايا الداخلية والزوايا الخارجية Interior and Exterior of an angle 

الزوايا الداخلية للشكل التالي ┙PQR هي الجزء المضلل حيث ان الـ s نقطة داخلية للزاوية ┙Q لانها تقع على الجانب -R للمتجه PQ ، وضلع الـ p- للمتجه QR ، فمجموع النقاط تعتبر داخلية لـ ┙PQR .

وفي الشكل التالي الجهة المضللة تعرض الجزء الخارجي للزاوية ┙ XYZ والجزء الخارجي للزاوية يمكن تعريفه بمجموع النقاط في الشكل الهندسي للزوية المعطاه التي لا تكون في الجانب الداخلي للزاوية .

قياس الزاوية Measure of an angle

كل زاوية لها قياس بالدرجات من 0⁰ الى 180⁰ ويرمز لها بـ  m ∠. A والخط ايضا يمكن اعتباره زاوية لانه يستوفي شروط القياس وله متجهين تتجه الى اتجاهين مختلفين ونقطة نهاية مشتركة 

وقياس الشكل السابق: M∠AOB=180⁰

جميع المتجهات تبدأ من o وتذهب للاعلى فوق الخط AB على شكل زوايا وقياسها جميعا بين 0⁰ الى 180⁰  eg. ∠ COB , ∠ DOB and ∠ EOB. 

الخصائص الاضافية للزوايا 

زاويتان لها جانب مشترك و vertex مشترك متجاور اذا كانت عناصره الداخلية منفصلة ، قياس زاويتان متجاورة يمكن جمعها لايجاد قياس ناتج الزاوية ، وهذا يسمى خصائص جمع الزوايا ، لاحظ الصورة السابقة .

 m ∠ COB + m ∠ DOC = m ∠ DOB.

منصف الزاوية Angle Bisectors

هو المتجه الذي يمر من خلال السمت او مايسمى  "vertex" على الزاوية ويقسم الزاوية الى زاويتان متساوية القياس مثل الشكل التالي

AOB and ∠ COB  ∠ متساوية القياس و OB يسمى منصف الزاوية ∠ COA  ومثل اي خط يكون له نقطة نهاية واحدة فإن الزاوية ايضا يكون لها منصف واحد فقط 

أنواع الزوايا  types of angles

• الزاوية القائمة right angle

الزاوية القائمة لها قياس90⁰ ويرمز لها بالرمز ⊾ وفي الشكل التالي جميع الزوايا القائمة متساوية ∠ AOB 

• الزاوية الحادة Acute angle

هي اي زاوية قياسها بين 0⁰ الى 90⁰ 

0 < a < 90

• الزاوية المنفرجة Obtuse angle

اي زاوية قياسها بين 90⁰ الى 180⁰

90⁰  < b < 180⁰

• بعض الزوايا الخاصة Some special angles

1. الزوايا التامة Complementary angle

 اذا كان مجموع زاويتين يساوي  90⁰ فان هذه الزاويتان تسمى تامة ، والزوايا التامة نوعان: اذا كان للزاوية التامة جانب واحد مشترك تسمى زاوية تامة متجاورة adjacent complementary angles (الشكل 1.20a)

واذا لم يكن هناك جانب مشترك تسمى زاوية تامة غير متجاورة non-adjacent complementary angles(الشكل 1.20b)

بالتالى قياس الزوايا التامة دائما المجموع يصل الى 90⁰ اذا كان قياس زاوية واحدة معلوم فبالتالي يمكن قياس الزاوية التامة بسهولة ، في الشكل السابق الزوايا تامة وقياس الزاوية a معلومه وهي معطاه m ∠ a = 30⁰. 

ويتضح القياس اكثر في المعادلة التالية :

m ∠ a + m ∠ b = 90⁰

    30⁰ + m ∠ b = 90⁰  

              m ∠ b = 90⁰ −30⁰ 

              m ∠ b = 60⁰

حيث ان كل زاوية تساوي 30 ومجموع الثلاث زوايا مجتمعة يساوي 90 بينما مجموع زاويتان يساوي 60 وهكذا

نظرية : اذا كانت الزوايتان تامة على الزاوية الثالثة فبالتي فان كل زاوية منهم تساوي الاخرى 

اثبات: 

: ∠ a and ∠ b are both complementary to ∠ c. 

∴ m ∠ a + m ∠ c =  90⁰ and also 

m ∠ b + m ∠ c =  90⁰  

∴ m ∠ a + m ∠ c = m ∠ b + m ∠ c OR 

m ∠ a = m ∠ b 

ملاحظة الكاتب : الزوايا التامة تسمى ايضا في المناهج الهندسية العربية متتامة او متكاملة  لذا انصح عند البحث استخدام المصطلح الانجليزي " complementary angle"

• الزوايا التكميلية Supplementary angles

اذا كان مجموع قياس زاويتان يصل الى 180⁰ فانها تسمى زوايا تكميلية والزوايا التكميلية نوعان :

1. زوايا تكميلية غير متجاورة  Non adjacent supplementary angles 
2. زوايا تكميلية متجاورة  Adjacent supplementary angles

الزاوية التكميلية غير المتجاورة منفصلة  distinct وليس لها اضلاع مشتركة 

 A and ∠ B are supplementary and non adjacent. الزوايا A وB تكميلية وغير متجاورة 

الزوية التكميلية المتجاورة تسمى زوايا بخط مزدوج ولها ضلع مشترك 

الزوايا المتقاطعة Vertical angles

عندما يتقاطع خطين AB و CD على النقطة O عندها ستنشأ 4 زوايا ويعتبر O السمت 

الزوايا المتقاطعة دائما متساوية القياس

اثبات: لاثبات  m ∠ AOC = m ∠ BOD 

m ∠ AOC + m ∠ COB = 180⁰ ( supplementary angles زاوية تكميلية ) 

m ∠ BOD + m ∠ COB = 180⁰( supplementary angles زاوية تكميلية) 

i.e. m ∠ AOC + m ∠ COB = m ∠ BOD + m ∠ COB 

or m ∠ AOC = m ∠ BOD. 

  تابع جميع تدوينات السلسلة على الرابط :  مــــن هـــــــــــــنا

المرجع :   Computational Geometry - Algorithms and Applications 3rd Ed

تمت ترجمة المرجع لصالح مدونة فاب fab2.info بواسطة : فيصل عسيري