هندسه محاسباتی
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
هندسهٔ محاسباتی[۱] یکی از شاخههای علوم رایانه است. هندسهٔ محاسباتی علم حل مسائل هندسی به روش الگوریتمی و با استفاده از ساختمان دادهها (Data Structures) است. بعضی از مسائل کاملاً هندسی، برآمده از مطالعهٔ الگوریتمهای هندسهٔ محاسباتی است و مطالعه اینگونه مسائل نیز به عنوان بخشی از هندسهٔ محاسباتی به حساب میآیند.
انگیزهٔ اصلی برای قلمداد کردن هندسهٔ محاسباتی به عنوان یک رشتهٔ علمی، پیشرفت در گرافیک رایانهای، طراحی و تولیدات با کمک رایانه (بهوسیلهٔ نرمافزارهایی مانند کد[۲]/کم[۳]) بود؛ ولی طبیعتاً بسیاری از مسائل در هندسهٔ محاسباتی، قدیمی هستند.
کاربردهای مهم دیگر هندسهٔ محاسباتی در دانش روباتیک (برنامهریزی حرکتی)، سیستمهای اطلاعات جغرافیایی[۴](جستجو و مکانیابی هندسی، نقشهکشی راهها)، طراحی مدار مجتمع[۵](طراحی و بازبینی هندسی مدارهای مجتمع) و مهندسی با کمک رایانه[۶] (برنامهریزی ماشینهای کنترل عددی)[۷] است.
شاخههای اصلی هندسهٔ محاسباتی عبارتاند از:
- هندسهٔ محاسباتی ترکیبی (هندسهٔ الگوریتمی): این هندسهٔ محاسباتی اشیای هندسی را بهعنوان موجودات گسسته در نظر میگیرد. براساس کتابی که توسط پرپاراتا[۸] و شاموس[۹] نوشته شدهاست، اصطلاح «هندسهٔ محاسباتی» با این مفهوم، نخستین بار در سال ۱۹۷۵ بیان شدهاست.
- هندسهٔ محاسباتی عددی (هندسهٔ ماشینی، طراحی هندسی با کمک رایانه یا مدلسازی هندسی): اساس کار این هندسهٔ محاسباتی به این صورت است که اشیای دنیای واقعی را بهصورت مناسبی برای محاسبات رایانهای در سیستمهای کد/کم درمیآورد. این شاخه ممکن است بهعنوان هندسهٔ توصیفی پیشرفته در نظر گرفته شود و اغلب یکی از شاخههای گرافیک کامپیوتری یا کَد به حساب میآید. هندسهٔ محاسباتی با این معنا، از سال ۱۹۷۱ مورد استفاده قرار گرفت.
هندسهٔ محاسباتی ترکیبیاتی
[ویرایش]هدف اصلی از پژوهش در زمینهٔ هندسهٔ محاسباتی ترکیبیاتی این است که، برای حل مسائلی که در زمینه اشیای پایه هندسی (نقاط، خطها، چندضلعیها، چندوجهیها[۱۰] و…) مطرح میشوند، الگوریتمها و ساختارهای دادهٔ[۱۱] مناسبی تولید شود.
برخی از این مسائل به قدری آسان به نظر میرسند که تا زمان پیدایش رایانهها مشکل به حساب نمیآمدند. برای مثال به مسئلهٔ نزدیکترین زوج[۱۲] توجه کنید:
- n نقطه در صفحه داریم. دو نقطهای که کمترین فاصله را از یکدیگر دارند، پیدا کنید.
میتوان فاصلهٔ بین جفت نقطهها، که تعدادشان معلوم هست را پیدا کرد و بعد کوچکترین عدد را انتخاب کرد. این الگوریتم از مرتبهٔ[۱۳] n۲ است. منظور این است که زمان اجرایش به مربع تعداد نقاط بستگی دارد. یک نتیجهٔ کلاسیک در هندسهٔ محاسباتی ایجاد الگوریتمی بود که از مرتبهٔ n log n زمان بگیرد. الگوریتمهای تصادفی که از مرتبهٔ n زمان میبرند، علاوه بر الگوریتمهای تعیینکنندهای که از مرتبهٔ n log n زمان میبرند نیز کشف شدهاند.
برای GIS جدید،[۱۴] گرافیک کامپیوتری و سیستمهای طراحی مدارهای مجتمع که روزانه دهها و صدها میلیون نقطه را به کار میگیرند، تفاوت بین مرتبهٔ n۲و مرتبهٔ n log n میتواند تفاوت بین روزها و ثانیهها محاسبه، باشد. به همین دلیل است که در هندسهٔ محاسباتی تأکید زیادی روی پیچیدگی محاسباتی شدهاست.
انواع سؤالات
[ویرایش]مسائل اساسی در هندسهٔ محاسباتی را میتوان با در نظر گرفتن معیارهای گوناگون، به روشهای گوناگونی طبقهبندی کرد. یکی از این ردهبندیها در زیر آمدهاست.
مسائل ایستا
[ویرایش]در این گروه از مسائل، نوعی ورودی داده میشود و خروجی متناسب باید به دست بیاید یا پیدا شود. برخی مسائل اساسی این نوع عبارتاند از:
- رویه محدب:[۱۵] تعدادی نقطه داریم، کوچکترین چندضلعی یا چندوجهی محدبی را پیدا کنید که دربرگیرندهٔ همه نقطههاست.
- تقاطع پاره خطها:[۱۶] تقاطعهای بین تعدادی پارهخط را پیدا کنید.
- مثلثبندی دلونی[۱۷]
- نمودارهای ورونوی:[۱۸] با دریافت مجموعهای از نقاط، فضا را بر اساس نزدیکترین نقطه تقسیمبندی کنید.
- برنامهریزی خطی:[۱۹] برنامهریزی خطی، یا همان بهینهسازی خطی، روشی در ریاضیات است که به پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی روی یک چندضلعی محدب میپردازد.
- نزدیکترین زوج نقاط:[۲۰] با دریافت مجموعهای از نقاط، دونقطهای را بیابید که کمترین فاصله را دارند.
- کوتاهترین مسیر اقلیدسی:[۲۱] دو نقطه را در فضای اقلیدسی (با یک مانع چند وجهی) با کوتاهترین مسیر به هم وصل کنید.
- مثلثبندی چندضلعی:[۲۲] با دریافت یک چندضلعی، سطح داخل آن را به تعدادی مثلث تقسیم کنید.
پیچیدگی محاسباتی برای این دسته از مسائل براساس زمان و فضای (حافظهٔ کامپیوتری) لازم برای حل مسئله تقریب زده میشود.
مسائل جستجوی هندسی
[ویرایش]در مسائل جستجوی هندسی[۲۳] ورودی از دو قسمت تشکیل شدهاست: قسمت فضای جستجو و قسمت جستجو، که در هر مسئله تغییر میکند. قسمت فضای جستجو باید به گونهای پیشپردازش[۲۴] شود که بتواند به نحو مطلوبی به سوالات متعدد جواب دهد.
برخی مسائل اساسی جستجوی هندسی عبارتاند از:
- جستجوی محدوده:[۲۵] مجموعهای از نقاط را پیشپردازش میکند برای اینکه درون محدودهٔ مطلوب، تعداد نقاط را بشمارد.
- محلیابی نقطه:[۲۶] با دریافت فضایی که تقسیمبندی شده، یک ساختار داده تولید میکند که به ما میگوید نقطهٔ مورد نظر، در کدام قسمت قرار دارد.
- نزدیکترین همسایه:[۲۷] مجموعهای از نقاط را به این منظور پیشپردازش میکند که تعیین کند کدام نقطه، به نقطهٔ مورد نظر نزدیکتر است.
- ردیابی پرتو:[۲۸] با دریافت مجموعهای از اجسام در فضا، یک ساختار داده تولید میکند تا تعیین کند که پرتوی جستجوی[۲۹] مورد نظر، نخستین بار با کدام جسم برخورد میکند.
اگر فضای جستجو ثابت باشد، پیچیدگی محاسباتی برای این دسته از مسائل بر اساس مطالب زیر تخمین زده میشود:
- زمان و حافظهٔ لازم برای ساختن ساختار دادهای که باید در داخل آن جستجو شود.
- زمان (و برخی مواقع یک حافظهٔ اضافی) برای پاسخ به جستجوها.
برای حالتی که فضای جستجو تغییر میکند، به مسائل پویا[۳۰] رجوع شود.
مسائل پویا
[ویرایش]یکی دیگر از گروههای اصلی مسائل، مسائل پویا هستند که در آنها هدف، یافتن الگوریتمی مناسب برای یافتن راه حلی است که بعد از هر تغییر دادهٔ ورودی (اضافه یا حذف کردن عناصر هندسی) تکرار شود. الگوریتمهای این نوع مسائل اغلب شامل ساختارهای دادهٔ پویا[۳۱] است. هر کدام از مسائل هندسهٔ محاسباتی را میتوان به مسئلهٔ پویا تبدیل کرد. برای مثال، مسئلهٔ جستجوی محدوده را میتوان با اضافه کردن امکان اضافه یا حذف کردن نقطهها به مسئلهٔ جستجوی پویای محدوده تبدیل کرد. مسئلهٔ پوستهٔ محدب پویا همان کار مسئلهٔ پوستهٔ محدب را برای مجموعهٔ نقاطی که بهطور پویا تغییر میکنند انجام میدهد.
پیچیدگی محاسباتی این دسته از مسائل با توجه به عوامل زیر تخمین زده میشود:
- زمان و حافظهٔ لازم برای ساختن ساختار دادهای که باید در داخل آن جستجو شود.
- زمان و حافظهٔ لازم برای تغییر دادن ساختار دادهٔ مورد جستجو، بعد از یک تغییر در فضای جستجو.
- زمان (و برخی مواقع یک حافظهٔ اضافی) برای پاسخ به جستجوها.
حالتهای گوناگون
[ویرایش]میتوان با برخی دادهها به گونهای برخورد کرد که با توجه به محتوایشان جزو هر کدام از گروههای معرفی شده قرار گیرند. برای مثال، مسئله زیر را در نظر بگیرید: نقطه در چند ضلعی:[۳۲] مشخص کنید که یک نقطهٔ مورد نظر داخل چند ضلعی است یا خارج آن. در بسیاری از موارد با این مسئله به عنوان یک تکتیر[۳۳] برخورد میشود، یعنی اینکه مربوط به گروه اول است. برای مثال، در بسیاری از نمونههای گرافیک کامپیوتری یک مسئلهٔ رایج این است که مشخص کند کدام ناحیه از صفحه توسط نشانهگر ماوس[۳۴] کلیک شدهاست. اما در برخی موارد چند ضلعی مورد نظر تغییرناپذیر است در حالی که نقطه مورد جستجو را به نمایش میگذارد. برای مثال، چند ضلعی وارد شده میتواند نمایندهٔ مرز یک کشور باشد و نقطه، مکان یک هواپیما و مسئله تعیین کردن این است که آیا هواپیما از مرز عبور کردهاست یا نه. در نهایت، در مثالهای بیان شده در گرافیک کامپیوتری ورودیهای متغیر در ساختارهای دادهٔ پویا ذخیره میشوند، تا به حل سوالاتی که مربوط به نقاط داخل چندضلعی است، سرعت بخشد.
هندسهٔ محاسباتی عددی
[ویرایش]این شاخه به مدلسازی هندسی و طراحی هندسی با کمک کامپیوتر[۳۵] نیز معروف است و اغلب تحت کلیدواژهٔ[۳۶] منحنیها و سطحها دیده میشود. مسئلههای اصلی در این نوع از هندسهٔ محاسباتی، مدلسازی و ارائهٔ منحنی و سطح است.
در اینجا مهمترین ابزارها، منحنیهای پارامتری[۳۷] و سطحهای پارامتری[۳۸] هستند، مانند خمهای بزیر،[۳۹] خمها و سطحهای نواری.[۴۰] از مهمترین روشهای غیرپارامتری، روش تنظیم رده[۴۱] است.
از نخستین و مهمترین کاربردهای هندسهٔ محاسباتی عددی، کاربرد در کشتیسازی، هواپیماسازی و صنایع ماشینآلات است. اما امروزه، به دلیل حضور گستردهٔ رایانهها و پیشرفتهتر شدن آنها حتی جعبههای عطر و شامپو نیز با تکنیکهایی که برای کشتیسازان دههٔ ۱۹۶۰ ناشناخته بود طراحی میشوند.
مطالعهٔ بیشتر
[ویرایش]مجلات
[ویرایش]هندسهٔ محاسباتی الگوریتمی/ترکیبی
[ویرایش]در پیوند زیر:
مجلات در زمینهٔ الگوریتمهای هندسی
فهرستی از مجلههای معتبر که در زمینهٔ الگوریتمهای هندسی، پژوهشهایی را چاپ کردهاند، آمدهاست. توجه شود که با آمدن مجلههایی که به هندسهٔ محاسباتی اختصاص یافتهاند، سهم انتشارات هندسی در مجلههای علوم کامپیوتر با هدف عمومی و مجلههای گرافیک کامپیوتری کاهش یافت.
مدلسازی هندسی/طراحی هندسی به کمک کامپیوتر
[ویرایش]فهرست مجلات در زمینهٔ مدلسازی هندسی
کتابها
[ویرایش]منابع لاتین
[ویرایش]1. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, ۲۰۰۸.
2. .2011,Satyan L. Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University
3. J. O'Rourke, Computational Geometry in C, 2nd edition, Cambridge University Press, ۱۹۹۸
منابع فارسی
[ویرایش]۱. هندسهٔ محاسباتی: الگوریتمها و کاربردها (ویراست سوم)، تألیف: مارک دی برگ، اوتفرید چیونگ، مارک وان کریولد، مارک اُورمارس- ترجمه: مهدی ایمانپرست، انتشارات دانش نگار، تهران، چاپ اول، ۱۳۹۴.
پانوشتها
[ویرایش]- ↑ computational geometry
- ↑ CAD
- ↑ CAM
- ↑ geographic information systems(GIS)
- ↑ integrated circuit (IC)
- ↑ computer-aided engineering(CAE)
- ↑ numerically controlled(NC)
- ↑ Preparata
- ↑ Shamos
- ↑ polyhedra
- ↑ data structures
- ↑ closest pair problem
- ↑ Order (O)
- ↑ modern GIS
- ↑ Convex hull
- ↑ Line segment intersection
- ↑ Delaunay triangulation
- ↑ Voronoi diagram
- ↑ Linear programming
- ↑ Closest pair of points
- ↑ Euclidean shortest path
- ↑ Polygon triangulation
- ↑ geometric query problems, geometric search problems
- ↑ preprocess
- ↑ Range searching
- ↑ Point location
- ↑ Nearest neighbor
- ↑ Ray tracing
- ↑ query ray
- ↑ Dynamic problems
- ↑ dynamic data structures
- ↑ point in polygon
- ↑ single-shot
- ↑ mouse curser
- ↑ computer-aided geometric design (CAGD)
- ↑ keyword
- ↑ parametric curves
- ↑ parametric surfaces
- ↑ Bezier curves
- ↑ spline
- ↑ level set method
منابع
[ویرایش]- ایران سازه (انگلیسی) https://web.archive.org/web/20131215134129/http://www.iransaze.com/article-print-841.html
- مشارکتکنندگان ویکیپدیا. «Computational geometry». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲ مه ۲۰۱۱.
Note: This template roughly follows the 2012 ACM Computing Classification System. | |
| سختافزار | |
| سازمان سامانههای رایانه | |
| شبکه رایانهای | |
| سازمان نرمافزار | |
| نظریه زبانهای برنامهنویسی و ابزار توسعه نرمافزار | |
| توسعه نرمافزار | |
| نظریه محاسبات | |
| الگوریتمها | |
| ریاضیات رایانه | |
| سامانه اطلاعاتی | |
| امنیت رایانه | |
| تعامل انسان و رایانه | |
| همروندی | |
| هوش مصنوعی | |
| یادگیری ماشین | |
| گرافیک رایانهای | |
| رایانش کاربردی | |
توجه: بنا بر سامانه ردهبندی رایانش ایسیام علم رایانه همچنین میتواند به موضوعها یا زمینههای گوناگون تقسیم شود.
| |
