Кіріспе
журналы
Компьютерлік ғылымның саласы
Компьютерлік геометрия — геометриялық терминдермен тұжырымдалған алгоритмдерді зерттейтін компьютерлік ғылымның саласы. Компьютерлік геометриялық алгоритмдерді зерттеу барысында туындайтын кейбір таза геометриялық мәселелер де компьютерлік геометрияның бір бөлігі саналады. Қазіргі заманғы компьютерлік геометрия жақында ғана дамығанмен, ол ежелгі заманға дейін созылатын тарихы бар ең көне есептеу салаларының бірі. Компьютерлік күрделілік компьютерлік геометрияның орталық мәселесі болып табылады, әсіресе алгоритмдер ондаған немесе жүздеген миллион нүктеден тұратын өте үлкен деректер жиынтығында қолданылғанда маңызды. Мұндай жиынтықтар үшін O(n²) мен O(n log n) арасындағы айырмашылық есептеу уақытының күндер мен секундтар арасындағы айырмашылықты білдіруі мүмкін. Компьютерлік геометрияның дамуына түрткіс болған негізгі фактор компьютерлік графика және компьютерлік көмекпен жобалау және өндіру (CAD/CAM) саласындағы жетістіктер болды, бірақ компьютерлік геометриядағы көптеген мәселелер классикалық сипатқа ие және математикалық визуализациядан туындауы мүмкін. Компьютерлік геометрияның маңызды қолданыс аймақтарына робототехника (қозғалыс жоспарлау және көріну мәселелері), географиялық ақпараттық жүйелер (ГИС) (геометриялық орналасу және іздеу, маршрутты жоспарлау), интегралды схемаларды жобалау (IC геометриясын жобалау және тексеру), компьютерлік көмекші инженерия (CAE) (тор генерациясы) және компьютерлік көру (3D реконструкция) жатады. Компьютерлік геометрияның негізгі салалары:
Branch of computer science
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity. Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(n2) and O(n log n) may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come from mathematical visualization. Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer aided engineering (CAE) (mesh generation), and computer vision (3D reconstruction). The main branches of computational geometry are:
Комбинаторлық компьютерлік геометрия, сондай-ақ алгоритмдік геометрия деп аталады, ол геометриялық объектілерді дискретті бірліктер ретінде қарастырады. Preparata және Shamos-тың осы тақырыпқа арналған негізгі кітабы 1975 жылы «компьютерлік геометрия» терминін осы мағынада алғаш рет қолданғанын көрсетеді. Сандық компьютерлік геометрия, сондай-ақ машина геометриясы, компьютерлік көмекпен геометриялық жобалау (CAGD) немесе геометриялық модельдеу деп аталады, ол негізінен CAD/CAM жүйелерінде компьютерлік есептеулерге қолайлы формада нақты әлем объектілерін бейнелеумен айналысады. Бұл сала сипаттамалық геометрияның одан әрі дамуы ретінде қарастырылады және көбінесе компьютерлік графиканың немесе CAD саласы ретінде қарастырылады. Осы мағынадағы «компьютерлік геометрия» термині 1971 жылдан бері қолданыста. Көптеген компьютерлік геометрия алгоритмдері (және әзірленуде) электрондық компьютерлер үшін әзірленгенімен, кейбір алгоритмдер дәстүрлі емес компьютерлер үшін (мысалы, оптикалық компьютерлер) әзірленді.
Комбинаторлық есептеу геометриясы
Комбинаторлық есептеу геометриясындағы зерттеулердің негізгі мақсаты – негізгі геометриялық нысандар: нүктелер, сызық сегменттері, көпбұрыштар, полиэдрлер және т.б. арқылы қойылған мәселелерді шешу үшін тиімді алгоритмдер мен дерек құрылымдарын жасау. Осы мәселелердің кейбіреуі соншалықты қарапайым көрінеді, тіпті компьютерлер пайда болғанға дейін оларды мәселе деп санамаған. Мысалы, ең жақын жұп мәселесін қарастырайық: жазықтықта n нүкте берілген болса, бір-біріне ең жақын қашықтықта орналасқан екі нүктені табыңыз. Барлық нүктелер жұптары арасындағы қашықтықты есептеуге болады, мұндай жұптардың саны n(n-1)/2-ге тең, содан кейін ең кіші қашықтықтың жұбын таңдауға болады. Бұл қарапайым алгоритмге O(n²) уақыт кетеді, яғни оның орындалу уақыты нүктелер санының квадратына пропорционалды. Есептеу геометриясының классикалық нәтижесі – O(n log n) уақыт алатын алгоритмнің құрылуы. Сондай-ақ, O(n) күтілетін уақытты алатын кездейсоқ алгоритмдер және O(n log log n) уақытты алатын детерминистік алгоритмдер де ашылды.
Given n points in the plane, find the two with the smallest distance from each other. One could compute the distances between all the pairs of points, of which there are n(n 1)/2, then pick the pair with the smallest distance. This brute force algorithm takes O(n2) time; i. e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O(n log n). Randomized algorithms that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered.
Проблемалық кластар
Есептеу геометриясының негізгі мәселелері әртүрлі критерийлер бойынша әртүрлі тәсілдермен жіктелуі мүмкін. Келесі жалпы санаттарды бөліп қарастыруға болады.
Вариациялар
Кейбір проблемалар, контекстке байланысты, осы екі санаттың біріне жатуы мүмкін. Мысалы, келесі мәселені қарастырайық. Көпбұрыштағы нүкте: нүкте берілген көпбұрыштың ішінде ме, сыртында ма, анықтаңыз. Көптеген қолданбаларда бұл мәселе бір реттік, яғни бірінші классқа жататын мәселе ретінде қарастырылады. Мысалы, компьютерлік графиканың көптеген қолданбаларында экрандағы қай аймаққа көрсеткіш басылғанын табу – кең таралған мәселе. Дегенмен, кейбір қолданбаларда сөз болатын көпбұрыш өзгермейтін, ал нүкте сұранысты білдіреді. Мысалы, кіріс көпбұрыш бір елдің шекарасын көрсете алады, ал нүкте – ұшақтың орны, және мәселе ұшақтың шекараны бұзғанын анықтау болып табылады. Соңында, компьютерлік графиканың бұрын айтылған мысалында, CAD қолданбаларында өзгермелі кіріс деректері көбінесе динамикалық дерек құрылымдарында сақталады, оларды көпбұрыштағы нүктелерді анықтау сұраныстарын жылдамдату үшін пайдалануға болады. Сұраныс мәселелерінің кейбір контексттерінде сұраныстар тізбегі туралы негізді күтулер бар, оларды тиімді дерек құрылымдары немесе есептеу күрделігін бағалау үшін қолдануға болады. Мысалы, кейбір жағдайларда жалғыз сұранысқа емес, N сұраныстың барлық тізбегі үшін ең нашар жағдайды білу маңызды. Сондай-ақ "амортизациялық талдау" қараңыз.
Сандық есептеу геометриясы
Бұл сала геометриялық модельдеу және компьютерлік көмекпен геометриялық жобалау (ККГЖ) деп те аталады. Негізгі мәселелер – қисықтар мен беттерді модельдеу және бейнелеу. Мұндағы ең маңызды құралдар – Безиер қисықтары, сплайн қисықтары және беттері сияқты параметрлік қисықтар мен параметрлік беттер. Маңызды параметрлік емес тәсіл – деңгей жиыны әдісі. Есептеу геометриясының қолданылу салаларына кеме жасау, авиация және автомобиль өнеркәсібі жатады.