امتحان هندسه محاسباتی
مال یه دانشگاه دیگه است: http://www.cs.iastate.edu/~cs518/exams/midterm.pdf
1- سه نقطه ی p1 و p2 و p3 داریم، شرط اینکه p3 روی پاره خط p1p2 باشد با ضرب برداری چیست؟
p1p2xp1p3=0
چون وقتی دو بردار هم خط باشند ضرب خارجی شون (سینوس زاویه بین) صفر میشه.
اصلاحیه: این کافی نیست، چون ممکنه نقطه p3 در ادامه ی نیم خط p1p2 بیفته، پس باید یه چک دیگه هم بکنیم که این طوری میشه که از p1 و p2 به p3 دو تا بردار رسم کنیم، اگر همجهت بودن یعنی p3 بیرون پاره خطه، و اگر مخالف جهت هم بودن یعنی روی پاره خط بوده. این هم با ضرب داخلی میشه چک کرد چون کسینوس همجهت ها کسینوس صفره که میشه یک و کسینوس خلاف جهت ها کسینوس 180 درجه است که میشه منفی یک.
2- کدامیک از مجموعه های زیر محدب اند؟
تعریف مجموعه محدب اینه که هر دو نقطه ای اش رو که به هم وصل کنی تو خودش بیفته.
الف) یک نقطه : به انتفای مقدم هست! (چون دو تا نقطه نداره!)
ب) یک مثلث تو خالی: نیست چون دو تا نقطه که رای نیستن به هم وصل کنیم تو این مجموعه (محیط مثلث) نیست.
ج) سهمی: نیست چون اصلا تو نداره که بخواد توش بیفته!
د) بیضی تو پر: هست
3-صحیح/غلط
الف) ؟؟
ب) جواب یک سوال برنامه ریزی خطی اگر یکتا باشه باید روی یک راس ناحیه مجاز باشه = درسته!
ج) تقاطع n تا نیم صفحه (شامل مرزها) نمی تونه یه نقطه بشه! غلطه. مثال نقضش محور مختصات!
4-تعداد مثلثهای یک مثلث بندی چند ضلعی ساده با n راس چیست؟
سه تا راس که برای یه مثلث می خوایم، هر راسی اضافه بشه یه مثلث اضافه میشه. کلا میشه n-3 به علاوه یکی میشه n-2
5- نخوندیم!
6-نخوندیم!
7-نخوندیم!
-----------------
*- doubly connected edge lists
1- فرض کنید e یک نیم یال باشه که یک قسمت مسطح رو مشخص میکنه، کدوم یکی از موارد زیر همیشه درست اند؟
DCEL کلا چهار تا چیز نگه میداره: عنصر بعدی اش، عنصر قبلی اش و راسی که نیم یال بهش وصل شده و نیم یال اون سر یال. هر نیم یال یه فیس (وجه) رو مشخص میکنه. همه رو هم ccw نگه میداره.
الف) اون سر نیم یال e عنصر بعدی اش هیچ وقت e نیست. خب ما میدونیم اون سر نیم یال next(e) قبلی next(e) است و در یک جهت نگه میداره و میتونه هیچی نباشه و بعدش دوباره رو همین برگرده و یه خط بسازه. پس غلطه.
ب) قبلی بعدی e خود e میشه. درسته!
ج) نیم یال e جزو فیس مجاور e هست. درسته انگار غلطه! :))
د) فیس مجاور e = فیس مجاور بعدی e. درسته دیگه تا وقتی دوباره به e برسه همه دور یه فیس اند.
2- یه قسمت دادن بهتون که 7 تا یال e1,..,e7 داره، و سه تا فیس f1,..,f3. هر یال ei به صورت ei,a و ei,b به دو تا نیم یال تقسیم میشه. جدولها رو با توجه به شکل پر کنید.
face -- outer component -- inner component
f1 -- e3a, e1a, e2a -- e2b, e1b, e3b
f2 -- e61, e4a, e5a -- e5b, e4b, e6b
f3 -- e7a, e7b -- e7b, e7a
half-edge -- twin -- incident face -- next -- prev
e1a -- e1b -- f2 -- e2a -- e3a
e1b -- e1a -- f1 -- e3b -- e2b
e3a -- e3b -- f2 -- e1a -- e2a
e3b -- e3a -- f1 -- e2b--e1b
e5a -- e5b -- f3-- e6a -- e4a
e5b -- e5a -- f2 -- e4b--e6b
e7a--e7b--f3--e7b--e7b
e7b--e7a--f3--e7a--e7a
3- مساله موزه هنری!
الف) گراف دوگان مثلث بندی بالا رو بکشید.
خلاصه این طوریه که باید به ازای هر دو تا فیس مجاور یه یال بکشید و هر فیس خودش یه راسه.
ب) با سه تا رنگ (اعداد 1 و 2 و3) راسهای گراف رو رنگ کنید. (دو تا از قبل رنگ شده) - این کار رو با دی اف اس انجام بدید.
این دی اف اس ای که میگه باید روی فیس ها بزنید. (راسهای گراف دوگان!)
** در این لحظه ی خاص کشف کردم که حل سوالها روی همون سایت بود! (نمی دونم چرا قبلش ندیده بودم! :دی)
این لینک: http://www.cs.iastate.edu/~cs518/exams/midterm-soln.pdf
4- الف) از رو جواب ببینید دیگه! شبیه آپدیت کردن لینک لیست میمونه فقط باید قبلی رو از روی ccw روی فیس اش تشخیص بدید!
چیزهایی که باید درست کنید: next و prev و origin و twin هستند. (حواستون باشه مثلا prev راس بعدی رو هم تغییر بدید!)
ب) گفته برای تقاطع دو یال چند تا آپدیت باید انجام بشه؟ کلا 4 تا فیس هست، هر کدوم طبق قسمت الف 12 تا آپدیت داره میشه 48 تا.
5-الف) با n تا نقطه ی داده شده یه چند ضلعی (ساده = نه لزوما محدب) بسازید که راسهاش اینها باشند. (با فرض اینکه هیچ سه نقطه ای همخط نیستند)و n>=3
خب تنها چیزی که توی این مهمه اینه که دو تا یال از روی هم رد نشن! (گراف که نیست که چند ضلعیه!). خب برای این دو تا نقطه رو به هم وصل می کنیم و نزدیک ترین نقطه رو به این پاره خط به دست میاریم. بعد از دو سر پاره خط به این وصل می کنیم یه مثلث میشه. این کار رو ادامه میدیم و اینکه نزدیک ترین نقطه است باعث میشه هیچ نقطه ای توی این چند ضلعیه نیفته. فقط باید هر بار که یه نقطه اضافه می کنیم اون نزدیک ترین ضلع بهش رو حذف کنیم!
خودش یه راه بهتری داده که شبیه کادوپیچیه، گفته پایین ترین نقطه (راست ترین در صورت چندتا بودن) رو پیدا کنید، بعد نقطه ها رو بر اساس زاویه شون نسبت به این نقطه مرتب کنید. بعد به ترتیب شروع کنید اینها رو هر کدوم رو به بعدی وصل کنید. اثباتش هم باید مثل اون باشه که می خوایم ببینیم یه نقطه توی یه چند ضلعی هست یا نه بعد میایم زاویه ها رو جمع می زنیم میبینیم اگه 360 شد یعنی بیرونه وگرنه توی چند ضلعیه. پس مهمه که نقطه ای که بر اساسش مرتب می کنیم توی چند ضلعی نیفته!
ب) زمان الگوریتمتون چقدره؟ زمانش میشه زمان مرتب کردن نقاط میشه O(nlogn) چون بعدش فقط یه وصل کردنه که O(n) زمان می بره.
(زمان مال من میشه O(n3) چون باید همه ی ضلع ها رو با همه ی نقاط باقیمونده حساب کنه تا هر راسی رو اضافه کنه!)
ج) چرا این زمان بهینه است؟
( مال من که بهینه نبود! :)) )
خب من ایده ای نداشتم دیدم خودش reduce کرده sort کردن n تا عدد (x) رو به ساختن این چند ضلعی برای نقاط (x,x^2). خب اگه این چند ضلعی رو برای این نقطه ها بسازیم، چرا x ها مرتب میشن؟؟ (کسی ایده ای داره؟ :)) ) خب اگه بیایم زاویه رو حساب کنیم با یه نقطه ی گوشه میشه انتقال مبدا مختصات میشه (x-x0, x^2-x0^2) بعد زاویه اش میشه arctan(x^2-x0^2)/(x-x0) که میشه arctan(x+x0) که خب x0 که ثابته، تانژانت هم که صعودیه، پس اگه این مرتب بشه اون هم مرتب میشه! (پس ایده ای اش همون حساب کردن زاویه بود)
خودش گفته از چپ به راست نقاط چند ضلعی رو چاپ کنید مرتب شده است و چون مرتب کردن امگای nlogn است (کران پایین) پس این هم بهتر از این حل نمیشه.
*** چه عجب تموم شد!
