Geometri komputasi
Geometri komputasi ialah satu cabang sains komputer yang menumpukan kepada kajian algoritma yang boleh dinyatakan dari segi geometri. Beberapa masalah geometri semata-mata timbul daripada kajian algoritma geometri pengiraan, dan masalah sedemikian juga dianggap sebagai sebahagian daripada geometri komputasi. Walaupun geometri komputasi moden adalah perkembangan terkini, ia adalah salah satu bidang pengkomputeran tertua dengan sejarah yang terbentang kembali ke zaman dahulu.
Kerumitan pengiraan adalah penting kepada geometri komputasi, dengan kepentingan praktikal yang besar jika algoritma digunakan pada set data yang sangat besar yang mengandungi puluhan atau ratusan juta mata. Untuk set sedemikian, perbezaan antara O (n2) dan O(n log n) boleh jadi perbezaan antara hari dan saat pengiraan.
Dorongan utama untuk pembangunan geometri komputasi sebagai satu disiplin ialah kemajuan dalam grafik komputer dan reka bentuk dan pembuatan berbantukan komputer (CAD / CAM), tetapi banyak masalah dalam geometri komputasi adalah bersifat klasik, dan mungkin datang daripada pembayangan matematik.
Aplikasi penting geometri komputasi lain termasuk robotik (perancangan gerakan dan masalah keterlihatan), sistem maklumat geografi (GIS) (lokasi dan carian geometri, perancangan laluan), reka bentuk litar bersepadu (reka bentuk dan pengesahan geometri IC), kejuruteraan bantuan komputer (CAE) (penjanaan jaringan), dan penglihatan komputer (pembinaan semula 3D).
Cabang utama geometri komputasi ialah:
- Geometri komputasi kombinatorial, juga dipanggil geometri algoritma, yang memperkatakan objek geometri sebagai entiti diskret. Sebuah buku asas dalam subjek oleh Preparata dan Shamos memulakan penggunaan pertama istilah "geometri komputasi" dalam pengertian ini menjelang 1975.[1]
- Geometri pengiraan berangka, juga dipanggil geometri mesin, reka bentuk geometri bantuan komputer (CAGD), atau pemodelan geometri, yang berurusan terutamanya dengan mewakili objek dunia sebenar dalam bentuk yang sesuai untuk pengiraan komputer dalam sistem CAD/CAM. Cabang ini boleh dilihat sebagai perkembangan lanjut geometri deskriptif dan sering dianggap sebagai cabang grafik komputer atau CAD. Istilah "geometri pengiraan" dalam pengertian ini telah digunakan sejak 1971.[2]
Walaupun kebanyakan algoritma geometri komputasi telah dibangunkan (dan sedang dibangunkan) untuk komputer elektronik, beberapa algoritma telah dibangunkan untuk komputer bukan konvensional (cth komputer optik[3])
Rujukan
[sunting | sunting sumber]- ^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988.
- ^ A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187–195 (1971)
- ^ Yevgeny B. Karasik (2019). Optical Computational Geometry. ISBN 979-8511243344.