გამოთვლითი გეომეტრია
გამოთვლითი გეომეტრია (ინგლ. Computational geometry) — კომპიუტერული მეცნიერების დარგი, რომელიც შეისწავლის ალგორითმებს. ზოგიერთი წმინდა გეომეტრიული პრობლემა წარმოიქმნება გამოთვლითი გეომეტრიული ალგორითმების შესწავლის საფუძველზე და ასეთი პრობლემები ასევე ითვლება გამოთვლითი გეომეტრიის ნაწილად. მიუხედავად იმისა, რომ თანამედროვე გამოთვლითი გეომეტრია არის ბოლოდროინდელი მეცნიერული განვითარების შედეგი, თუმცა იგი ანტიკური პერიოდის გამოთვლების ერთ-ერთი უძველესი მიმართულებაა.
| გამოთვლითი გეომეტრია | |
|---|---|
| კომბინატორული გამოთვლითი გეომეტრია | |
| რიცხვითი გამოთვლითი გეომეტრია | |
 | |
| მეცნიერების დარგი | კომპიუტერული მეცნიერება |
| ძირითადი დარგები |
|
| პრობლემის კლასიფიცირება |
|
გამოთვლითი გეომეტრიის, როგორც დისციპლინის განვითარების მთავარი იმპულსი იყო კომპიუტერული გრაფიკის პროგრესი, მაგრამ გამოთვლითი გეომეტრიის ბევრი პრობლემა კლასიკური ხასიათისაა და შეიძლება მათემატიკური ვიზუალიზაციიდან გამომდინარეობდეს.
გამოთვლითი გეომეტრიის სხვა მნიშვნელოვანი პროგრამებია: რობოტიკა (მოძრაობის დაგეგმვა და ხილვადობის
პრობლემები), გეოგრაფიული ინფორმაციის სისტემები (GIS) (გეომეტრიული მდებარეობა და ძებნა, მარშრუტის დაგეგმვა), ინტეგრირებული სქემის დიზაინი (IC გეომეტრიული დიზაინი და შემოწმება), კომპიუტერული ინჟინერია (CAE) (ბადის წარმოება) და კომპიუტერული ხედვა (3D რეკონსტრუქცია).
გამოთვლითი გეომეტრიის ძირითადი დარგებია:
- კომბინატორული გამოთვლითი გეომეტრია, რომელსაც ასევე უწოდებენ ალგორითმულ გეომეტრიას, რომელიც სწავლობს გეომეტრიულ საგნებს, როგორც დისკრეტულ ერთეულებს. ტერმინი "გამოთვლითი გეომეტრია" ამ მნიშვნელობით პრეპარატასა და შამოსის წიგნშია ნახსენები და თარიღდება 1975 წლით.
- რიცხვითი გამოთვლითი გეომეტრია, რომელსაც ასევე უწოდებენ მანქანურ გეომეტრიას, კომპიუტერულ გეომეტრიულ დიზაინს (CAGD), ან გეომეტრიულ მოდელირებას, ეხება რეალურ სამყაროში არსებული ობიექტების კომპიუტერულ გამოთვლებისათვის შესაფერისი ფორმების წარმოდგენას CAD/CAM სისტემებში. ეს დარგი შეიძლება ჩაითვალოს აღწერითი გეომეტრიის შემდგომ განვითარებად და ხშირად განიხილება კომპიუტერული გრაფიკის ან CAD-ის მიმდინარეობად. ტერმინი "გამოთვლითი გეომეტრია" ამ მნიშვნელობით გამოიყენება 1971 წლიდან.[1]
მიუხედავად იმისა, რომ გამოთვლითი გეომეტრიის უმეტესი ალგორითმი განვითარდა (და ვითარდება) ელექტრონული კომპიუტერებისთვის, ზოგიერთი ალგორითმი შემუშავებულია არატრადიციული კომპიუტერებისთვის (მაგ. ოპტიკური კომპიუტერები).
კომბინატორული გამოთვლითი გეომეტრია
რედაქტირებაკომბინატორულ გამოთვლით გეომეტრიაში კვლევის უპირველესი მიზანია შექმნას ეფექტური ალგორითმები და მონაცემთა სტრუქტურები ძირითადი გეომეტრიული ობიექტების თვალსაზრისით წარმოქმნილი პრობლემების გადასაჭრელად: წერტილები, ხაზების სეგმენტები, პოლიგონები, პოლიედრონები და ა.შ.
ზოგიერთი ეს პრობლემა იმდენად მარტივია, რომ ისინი კომპიუტერების გამოჩენამდე საერთოდ არ განიხილებოდა, როგორც პრობლემა. მაგალითად, განვიხილოთ უახლოესი წყვილის პრობლემა:
სიბრტყეში მოცემულია n რაოდენობის წერტილები, იპოვეთ ორი ერთმანეთთან ყველაზე ახლოს მყოფი წერტილი.
შეიძლება გამოითვალოს მანძილი წერტილების ყველა წყვილს შორის, რომელთაგან არის n (n-1)/2, შემდეგ კი აირჩეს წყვილი ყველაზე მცირე მანძილით. ამ ალგორითმს მიაქვს O (n²) დროს; ანუ მისი შესრულების დრო პროპორციულია წერტილების რაოდენობის კვადრატისა. კლასიკური შედეგი გამოთვლილ გეომეტრიაში იქნებოდა ალგორითმის ფორმულირება, რომელიც იღებს შემდეგ სახეს O (n log n). ასევე აღმოჩენილია რანდომიზებული ალგორითმები, რომლითაც ვიღებთ O (n) მოსალოდნელ დროს[2], ასევე დეტერმინისტული ალგორითმი, რომლითაც მიიღება O (n log log n) დროს[3].
პრობლემის კლასიფიცირება
რედაქტირებაგამოთვლითი გეომეტრიის ძირითადი პრობლემები შეიძლება კლასიფიცირდეს სხვადასხვა გზით, სხვადასხვა კრიტერიუმების გათვალისწინებით. შეგვიძლია გამოვყოთ შემდეგი ზოგადი კლასები:
სტატიკური პრობლემები
რედაქტირება- ამოზნექილი კორპუსი: წერტილების ნაკრების გათვალისწინებით, იპოვნეთ ყველაზე პატარა ამოზნექილი პოლიგონი/პოლიედრონი, რომელიც შეიცავს ყველა წერტილს.
- ხაზის სეგმენტის გადაკვეთა: იპოვეთ კვეთა ხაზების სეგმენტების მოცემულ ნაკრებებს შორის.
- Delaunay triangulation
- Voronoi diagram: მოცემულია წერტილების ერთობლიობა, გაყავით სივრცე იმის მიხედვით თუ რომელი წერტილებია ყველაზე ახლოს მოცემულ წერტილებთან.
- ხაზოვანი პროგრამირება
- წერტილების უახლოესი წყვილი: წერტილების ნაკრების გათვალისწინებით, იპოვეთ ორი ერთმანეთისგან ყველაზე მცირე მანძილით დაშორებული წერტილები.
- წერტილების ყველაზე შორი წყვილი
- ყველაზე დიდი ცარიელი წრე: წერტილების ერთობლიობის გათვალისწინებით, იპოვნეთ უდიდესი წრე მისი ცენტრით, ამოზნექილი გარსის შიგნით ისე, რომ არცერთი მათგანი არ ეხებოდეს.
- ევკლიდური უმოკლესი გზა: შეაერთეთ ორი წერტილი ევკლიდურ სივრცეში უმოკლესი გზით.
- პოლიგონის დაყოფა სამკუთხედებად: მოცემულია მრავალკუთხედი, დაყავით ის სამკუთხედებად
- ბადისებრი თაობა
- ლოგიკური ოპერაციები პოლიგონებზე
ამ კლასის პრობლემების გამოთვლის სირთულე შეფასებულია იმ დროისა და სივრცის მიხედვით (კომპიუტერის მეხსიერება), რომელიც საჭიროა მოცემული პრობლემის გადასაჭრელად.
გეომეტრიული კითხვის პრობლემები
რედაქტირებაგეომეტრიული კითხვის პრობლემებში, რომელიც ცნობილია როგორც გეომეტრიული ძებნის პრობლემები, შეყვანა შედგება ორი ნაწილისგან: საძიებო სივრცის ნაწილი და შეკითხვის ნაწილი, რომლებიც განსხვავებულია სხვადასხვა პრობლემის გათვალისწინებით. საძიებო სივრცეს, როგორც წესი, სჭირდება წინასწარი დამუშავება ისე, რომ მრავალ შეკითხვაზე შეეძლოს ეფექტური პასუხის გაცემა.
ზოგიერთი ფუნდამენტური გეომეტრიული შეკითხვის პრობლემაა:
- დიაპაზონის ძებნა: წერტილების ერთობლიობის წინასწარი დამუშავება, რათა ეფექტურად დაითვალოს წერტილების რაოდენობა შეკითხვის რეგიონში.
- წერტილის მდებარეობა: იმის გათვალისწინებით, რომ სივრცე იყოფა უჯრედებად, შექმენით მონაცემთა სტრუქტურა, რომელიც ეფექტურად გეტყვით რომელ უჯრედში მდებარეობს შეკითხვის წერტილი.
- უახლოესი მეზობელი: წინასწარ დაამუშავეთ წერტილების ერთობლიობა, რათა ეფექტურად იპოვოთ რომელია ყველაზე ახლოს შეკითხვასთან.
- სხივების კვალი: სივრცეში არსებული ობიექტების ერთობლიობის გათვალისწინებით, შექმენით მონაცემთა სტრუქტურა, რომელიც ეფექტურად გვეტყვის, რომელი ობიექტი გადაკვეთს სხივს პირველად.
თუ საძიებო სივრცე დაფიქსირებულია, ამ კლასის პრობლემების გამოთვლის სირთულე ჩვეულებრივ შეფასებულია
- იმ დროით და სივრცით, რომელიც საჭიროა მონაცემების სტრუქტურის შესაქმნელად.
- იმ დროით (და ზოგჯერ დამატებით ადგილით), რომელიც საჭიროა კითხვებზე პასუხის გასაცემად.
დინამიური პრობლემები
რედაქტირებამისი მიზანია ეფექტური ალგორითმის პოვნა გამოსავლის საპოვნელად არაერთხელ შემავალი მონაცემების ყოველი დამატებითი მოდიფიკაციის შემდეგ (ეომეტრიული ელემენტების შეყვანა, დამატება ან წაშლა). ამ ტიპის პრობლემების ალგორითმები, როგორც წესი, მოიცავს მონაცემთა დინამიურ სტრუქტურას. ნებისმიერი გამოთვლითი გეომეტრიული პრობლემა შეიძლება გარდაიქმნას დინამიურად, დამუშავების გაზრდილი დროის ფასად. მაგალითად, დიაპაზონის ძებნის პრობლემა შეიძლება გარდაიქმნას დინამიური დიაპაზონის ძიების პრობლემად წერტილების დამატებისა და/ან წაშლის შედეგად. დინამიური ამოზნექილი კორპუსის პრობლემა არის ამოზნექილი კორპუსის თვალყურის დევნება, მაგ., წერტილების დინამიურად ცვალებადი ნაკრებისთვის, ანუ შეყვანის წერტილების ჩასმის ან წაშლისას.
ამ ტიპის პრობლემების გამოთვლის სირთულე შეფასებულია:
- იმ დროით და სივრცით, რომელიც საჭიროა მონაცემების სტრუქტურის შესაქმნელად.
- იმ დროით და სივრცით, რომელიც საჭიროა ძებნილი მონაცემების სტრუქტურის შესაცვლელად საძიებო სივრცეში დამატებითი ცვლილების შემდეგ
- იმ დროით (და ზოგჯერ დამატებით ადგილით), რომელიც საჭიროა კითხვაზე პასუხის გასაცემად.
ვარიაციები
რედაქტირებაკონტექსტიდან გამომდინარე, ზოგიერთი პრობლემა შეიძლება განიხილებოდეს როგორც რომელიმე კატეგორიის კუთვნილება. მაგალითად, განვიხილოთ შემდეგი პრობლემა.
წერტილი მრავალკუთხედში: გადაწყვიტეთ წერტილი არის მოცემული მრავალკუთხედის შიგნით თუ გარეთ.
ბევრ პროგრამაში ეს პრობლემა განიხილება როგორც ერთჯერადი, ანუ პირველი კლასის კუთვნილება. მაგალითად, კომპიუტერული გრაფიკის ბევრ პროგრამაში საერთო პრობლემაა ეკრანის რომელ უბანზე დააწკაპუნებს მაჩვენებელი. თუმცა, ზოგიერთ პროგრამაში, პოლიგონი არის უცვლელი, ხოლო წერტილი წარმოადგენს შეკითხვას. მაგალითად, შეყვანის პოლიგონი შეიძლება წარმოადგენდეს ქვეყნის საზღვარს და წერტილი არის თვითმფრინავის პოზიცია, ხოლო პრობლემა არის იმის დადგენა, დაარღვია თუ არა თვითმფრინავმა საზღვარი. და ბოლოს, კომპიუტერული გრაფიკის ადრე ხსენებულ მაგალითში, CAD პროგრამებში შეცვლილი შეყვანის მონაცემები ხშირად ინახება დინამიურ მონაცემთა სტრუქტურებში, რაც შეიძლება გამოყენებულ იქნას პოლიგონური წერტილების მოთხოვნის დასაჩქარებლად.
რიცხვითი გამოთვლითი გეომეტრია
რედაქტირებაეს მიმდინარეობა ასევე ცნობილია როგორც გეომეტრიული მოდელირება და კომპიუტერული გეომეტრიული დიზაინი (CAGD).
ძირითადი პრობლემა გულისხმობს მრუდისა და ზედაპირის მოდელირებას და წარმოდგენას.
აქ ყველაზე მნიშვნელოვანი ინსტრუმენტებია პარამეტრული მოსახვევები და პარამეტრული ზედაპირები, როგორიცაა ბეზიეს მრუდი, სპლინის მრუდი და სხვა ზედაპირები. მნიშვნელოვანი არაპარამეტრული მიდგომა არის დონის დადგენის მეთოდი.
გამოთვლითი გეომეტრიის გამოყენების სფეროებია გემთმშენებლობა, თვითმფრინავები და საავტომობილო ინდუსტრიები.
ლიტერატურა
რედაქტირება- (1985) Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
- (1998) Algorithmic Geometry. Cambridge University Press. Translation of a 1995 French edition. ISBN 0-521-56529-4.
- Joseph O'Rourke (1998). Computational Geometry in C, 2nd, Cambridge University Press. ISBN 0-521-64976-5.
- (2011) Discrete and Computational Geometry. Princeton University Press. ISBN 978-0-691-14553-2.
- Jim Arlow (2014). Interactive Computational Geometry - A taxonomic approach. Mountain Way Limited. 1st edition: ISBN 978-0-9572928-2-6.
რესურსები ინტერნეტში
რედაქტირებასქოლიო
რედაქტირება- ↑ A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)
- ↑ S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem Inf. Comput., 118(1):34—37,1995 (PDF)
- ↑ S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979