پاورپوینت هندسه ی محاسباتی

بخشی از پاورپوینت

اسلاید 2 :

به نام حضرت دوست
هندسه ي محاسباتي

اسلاید 3 :

بسياري از اجسام اطراف ما، مانند شكل ماشينها، كاپ هاي پلاستيكي و . با استفاده از شكل دهي اتوماتيكي ساخته مي شوند. كامپيوترها نقش مهمي را هم در فاز طراحي و هم در فاز ساختاربندي ايجاد مي كنند، بنابراين امكانات CAD/CAM بخش حياتي هر كارخانه مدرن مي باشد. فاز ساختاربندي در واقع به بيان ساختن يك شئ خاص باتوجه به فاكتورهايي مثل: ماده شئ اي كه بايد ساخته شود، شكل شئ، اينكه آيا شئ به مقدار زياد قابل ساختن مي باشد يا نه و. مي پردازد.
در اين فصل به مطالعه منظرهاي هندسي ساختن با قالبها، كه يك پروسه رايج استفاده شده براي اشياء فلزي يا پلاستيكي است، پرداخته مي شود. براي اشياء فلزي اين پروسه به عنوان ريخته گري بيان مي شود.

اسلاید 4 :

شكل 1-4 پروسه ريخته گري را شرح مي دهد. فلز مايع داخل يك قالب ريخته مي شود، منجمد مي گردد و شئ از قالب بيرون مي آيد. مرحله آخر به همين سادگي انجام نمي شود، ممكن است بدون شكستن قالب شئ بيرون نيايد. ممكن است تنها با چرخاندن قالب شئ بيرون بيايد، وگاهي اشيائي وجود دارند كه قالبي براي آنها وجود ندارد، مثل كره. بنابراين در اين فصل بر روي وجود يا عدم وجود قالبي براي يك شئ كه بتواند از آن خارج شود بحث مي گردد.

اسلاید 5 :

قرارداد 1: شئ چندوجهي درنظرگرفته مي شود.

قرارداد 2: قالبها فقط يك تكه اي درنظر گرفته مي شوند.(قالبهاي دوتكه اي براي ساخت اشيائي مثل كره مورد استفاده قرار مي گيرند.)

قرارداد 3: هر شئ را تنها با يك حركت مي توان از قالب بيرون آورد.(مثلا يك پيچ را نمي توان از قالبش بيرون آورد.) براي اين كار حركت انتقالي مناسب است.

اسلاید 6 :

مسئله: يك شئ با ريخته گري قابل ساخت است يا نه؟
پاسخ اول: بايد براي آن يك قالب مناسب بيابيم كه از آن خارج شود. شكل حفره داخل قالب توسط شكل شئ معين مي شود ولي جهتهاي مختلف شئ قالب هاي متمايزي را ايجاد مي كنند، كه اين انتخاب جهت مي تواند سخت باشد، چون در بسياري از جهتها شئ از قالبش خارج نمي شود، درحاليكه در جهتهاي ديگر ممكن است خارج شود.
يك محدوديت روي جهت اين است كه شئ بايد يك top facet افقي داشته باشد. اين سطح تنها جايي است كه درتماس با قالب نخواهد بود.
پاسخ دوم: شئ قابل ريخته گري است
اگرحداقل از يك جهت با top facet
متناسب با آن جهت قابل بيرون آمدن
از قالبش باشد.

اسلاید 7 :

در ادامه بر روي تعيين اينكه ”آيا يك شئ با يك انتقال قابل بيرون آمدن از يك قالب معين مي باشد يا نه“ بحث مي شود و براي تصميم گيري روي قابليت ريخته گري يك شئ ”هر جهت ممكن“ مورد بررسي واقع مي شود.
فرض كنيد P يك چندوجهي سه بعدي است كه با سطوح دو بعدي و يك top facet معين طراحي شده است.(دراينجا نيازي نيست كه يك تعريف دقيق از polyhedron ارائه شود.)
قالب يك بلوك مستطيلي با حفره اي دقيقا مطابق P مي باشد. وقتي چندوجهي داخل قالب قرار مي گيرد، top facet آن بايد هم سطح با بالاترين سطح قالب باشد، يعني قالب هيچ قسمت اضافي كه ممكن است مانع خروج شئ شود در سطح بالايي اش ندارد.

اسلاید 8 :

 1-4 هندسه ي ريخته گري

هر سطح P به غير از top facet سطح ordinary ناميده مي شود.
هر سطح ordinary به نام ƒ با يك سطح از قالب به نام ‘ƒ’ متناظر است.
آيا يك بردار جهت وجود دارد كه P بتواند بدون برخورد با سطوح داخلي قالب در طول انتقال خارج شود؟ (لغزيدن درطول قالب ايرادي ندارد.)
ازآنجا كه تنها سطح بدون تماس با قالب top facet است، جهت خروج بايد در جهت مثبت محور zها باشد و اين تنها شرط موجود بر روي جهت است.

اسلاید 9 :

اگر ƒ يك سطح ordinary، P باشد، آنگاه اين سطح يا بايد از يك طرف سطح متناظر ‘ƒ’ قالب حركت كند و يا بر روي ‘ƒ’ بلغزد. براي ايجاد اين دقت نياز است به زاويه بين دو بردار در فضاي سه بعدي.
زاويه بين دو بردار: دو بردار از يك مبدا درنظر گرفته شده و صفحه گذرنده از آن دو را ساخته، كوچكترين زاويه بين دو بردار زاويه موردنظر است.
شرط لازم روي : زاويه آن با بردار نرمال خارجي هر سطح ordinary،p حداقل 90 باشد.(لم 1-4)

اسلاید 10 :

لم 1-4: چندوجهي P مي تواند در جهت از قالبش خارج شود، اگر و فقط اگر زاويه حداقل 90 با نرمال خارجي تمام سطوح ordinary، P بسازد.
اثبات: طرف رفت
اگر با نرمال خارجي يكي از سطوح ordinary، Pيعني زاويه كمتر از 90 بسازد، هنگام انتقال تمام نقاط داخل f با قالب برخورد مي كند.

اسلاید 11 :

طرف برگشت
فرض خلف: در جايي P با قالب برخورد كند، بايد نشان دهيم كه يك نرمال خارجي كه زاويه كمتر از 90 با مي سازد، وجود دارد. فرض كنيد p نقطه اي از P است كه با يك سطح ‘ƒ’ قالب برخورد كرده است، اين بدين معني است كه p نمی تواند به سمت بیرون حرکت کند، پس بايد زاويه بزرگتر از 90 با بسازد، در نتيجه با زاويه كمتر از 90 مي سازد.
لم 1-4: چندوجهي P مي تواند در جهت از قالبش خارج شود، اگر و فقط اگر زاويه حداقل 90 با نرمال خارجي تمام سطوح ordinary، P بسازد.

اسلاید 12 :

يك نتيجه جالب لم: اگر P را بتوان با دنباله اي از انتقال هاي كوچك از قالبش بيرون آورد، با يك انتقال هم مي توان. پس امكان استفاده بيش از يك انتقال كمكي به حل مسئله نمي كند.
هدف: يافتن بردار با ويژگي بيان شده در لم 1-4.
يك جهت در فضاي سه بعدي با يك بردار كه
از مبدا مختصات شروع مي شود، معين
مي گردد. با توجه به مثبت بودن z بردار
اين بردارها را به عنوان نقاطي در صفحه z=1 درنظر مي گيريم.
نتيجه: هر نقطه در صفحه z=1 مثل (x,y,1)معرف بردار منحصر بفرد(x,y,1) مي باشد و برعكس.

اسلاید 13 :

سؤال: لم 1-4 شرايط لازم و كافي را روي جهت ارائه داد، چگونه اين شرايط به صفحه جهت( صفحه z=1) انتقال يابد؟
فرض كنيد نرمال خارجي يك سطح ordinary باشد، بردار يك زاويه حداقل 90 با مي سازد، اگر و فقط اگر ضرب داخلي و غيرمثبت شود:

اين نامساوي توصيف كننده يك نيم صفحه روي صفحه z=1 مي باشد كه در طرف راست يا چپ يك خط روي اين صفحه مي باشد.
نكته: اين شرط براي سطوح افقي صحيح نمي باشد، چون . درنتيجه يا كه همواره برقرار است و شرط بررسي نمي شود و يا كه هيچگاه برقرار نيست.

اسلاید 14 :

بنابراين هر سطح غير افقي P معرف يك نيم صفحه روي صفحه z=1 است، كه هر نقطه در تقاطع مشترك اين نيم صفحه ها معادل بردار جهتي است كه با آن مي توان شئ را از قالبش درآورد. اين تقاطع مشترك مي تواند تهي نيز باشد كه بدين معني است كه شئ قابل خارج شدن از قالبش نمي باشد.
تبديل مسئله به يك مسئله هندسي: يافتن يك نقطه در تقاطع مشترك يك مجموعه داده شده از نيم صفحه ها و يا تصميم گيري اينكه تقاطع تهي است.
اگر چندوجهي موردنظر n سطح داشته باشد، حداكثر n-1 نيم صفحه مورد بحث است.(حداكثر به دليل عدم حضور سطوح افقي و منهاي 1 به دليل عدم حضور top facet )

اسلاید 15 :

از آنجا كه گفته شد براي تست قابليت ريخته گري P بايد تمام سطوح به عنوان top facet در نظر گرفته شوند، قضيه زير بيان مي شود.
قضيه 2-4: اگر Pچندوجهي با n سطح باشد در زمان مورد انتظار o(n2) و حافظه مورد نياز o(n) براي ذخيره سازي مي توان تصميم گرفت كه آيا P قابل ريخته گري است يا نه. به علاوه اگر P قابل ريخته گري باشد در زمان مشابهي مي توان يك قالب و يك جهت مناسب براي خروج آن يافت.

اسلاید 16 :

فرض كنيد كه H={h1,h2,..,hn} مجموعه اي از معادلات خطي دومتغيره باشد، كه هر معادله به صورت aix+biy ≤ ci است. ci وbi و ai ثابت هستند و bi و ai همزمان نمي توانند صفر باشند.

از لحاظ هندسي يك معادله به عنوان يك نيم صفحه بسته در R2 كه با خط aix+biy = ci كراندار شده بيان مي شود.

مسئله: يافتن ”تمام“ نقاط R2 (x,y) ∊ كه در همه n معادله صدق كند، به عبارت ديگر يافتن تمام نقاط واقع شده در تقاطع مشترك نيم صفحه هاي H.(در اين قسمت مسئله نسبت به قبل كلي تر مي شود.)

2-4 تقاطع نيم صفحه ها

اسلاید 17 :

تعيين شكل ناحيه مشترك نيم صفحه ها:
هر نيم صفحه يك ناحيه محدب است واشتراك نواحي محدب نيز محدب است.
هر نقطه روي مرز تقاطع مشترك بايد روي مرز يكي ازنيم صفحه ها واقع شود، درنتيجه يالهاي سازنده ناحيه مشترك همان خطهاي مرزي بعضي از نيم صفحه ها مي باشند.
از آنجا كه ناحيه تقاطع محدب است، هر خط مرزي يك نيم صفحه مي تواند حداكثر سازنده يك يال باشد.
نتيجه: تقاطع مشترك n نيم صفحه يك
چندضلعي محدب است كه حداكثر با
n يال محدود شده است.

اسلاید 18 :

شكل فوق (2-4) چند مورد از اين تقاطع ها را نشان مي دهد. تقاطع هم مي تواند نامحدود باشد(شكل iiو iii)، هم مي تواند به صورت يك نقطه يا خط باشد(شكلiv) و هم مي تواند تهي باشد(شكل v).

اسلاید 19 :

الگوريتم divide-and-conquer براي يافتن تقاطع مشترك n نيم صفحه ارائه مي شود، كه بر پايه يك INTERSECTREGIONCONVEX عادي براي محاسبه تقاطع دو ناحيه محدب است.

اسلاید 20 :

در نتيجه 7-2 ديده شد كه نقاط اشتراك دو چندضلعي در زمان o(nlogn+klogn) قابل محاسبه است، كه n مجموع تعداد رئوس در دو چندضلعي و k تعداد نقاط اشتراك بين دو ناحيه مي باشد. البته در اينجا بايد توجه كرد كه نواحي مشترك مي توانند خط و يا نقطه هم باشند يعني لزوما چندضلعي نمي باشند.
اگرv نقطه مشترك يال e1 از C1 و يال e2 از C2 باشد، بدون توجه به چگونگي اشتراك e1وe2 ،v بايد يك راس c1 ⋂c2 باشد،
و از آنجا كه c1 ⋂c2 اشتراك n نيم صفحه است،
حداكثر n يال و n راس دارد. اين نتيجه مي دهد كه
n ≤ k ،پس زمان اجرا برابر است با:o(nlogn).