Computational geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms of geometry.
Geometri komputasi merupakan salah satu cabang ilmu komputer yang mempelajari algoritma yang dapat dinyatakan dalam istilah geometri.
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.
Beberapa masalah geometri murni muncul dari studi tentang algoritma geometri komputasi, dan masalah seperti itu juga dianggap sebagai bagian dari geometri komputasi.
While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.
Geometri komputasi merupakan salah satu bidang komputasi tertua dalam sejarah sejak zaman kuno, meskipun geometri komputasi modern yang saat ini masih dalam perkembangan.
For such sets, the difference between O(n2) and O(n log n) may be the difference between days and seconds of computation.
Untuk himpunan seperti itu, perbedaan antara O ( n 2 ) dan O ( n log n ) bisa saja diartikan sebagai perbedaan antara hari dan detik dalam komputasi.
The main branches of computational geometry are: Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discrete entities.
Cabang utama geometri komputasi adalah: Geometri komputasi kombinatorial , juga disebut geometri algoritmik , yang menangani objek geometris sebagai entitas diskrit .
Numerical computational geometry, also called machine geometry, computer-aided geometric design (CAGD), or geometric modeling, which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems.
Geometri komputasi numerik , juga disebut geometri mesin , desain geometris berbantuan komputer (CAGD), atau pemodelan geometris , yang terutama berhubungan dengan representasi objek dunia nyata dalam bentuk yang sesuai untuk komputasi komputer dalam sistem CAD / CAM.
This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics or CAD.
Cabang ini dapat dilihat sebagai pengembangan lebih lanjut dari geometri deskriptif dan sering dianggap sebagai cabang grafik komputer atau CAD.
The term "computational geometry" in this meaning has been in use since 1971.
Istilah "geometri komputasi" dalam arti ini telah digunakan sejak tahun 1971.
The primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc.
Tujuan utama penelitian dalam geometri komputasi kombinatorial adalah untuk mengembangkan algoritma dan struktur data yang efisien untuk memecahkan masalah yang dinyatakan dalam objek geometris dasar: titik, ruas garis, poligon , polihedra , dll.
Some of these problems seem so simple that they were not regarded as problems at all until the advent of computers.
Beberapa dari masalah ini tampak begitu sederhana sehingga mereka tidak dianggap sebagai masalah sama sekali sampai munculnya komputer .
Consider, for example, the closest pair problem: Given n points in the plane, find the two with the smallest distance from each other.
Pertimbangkan, misalnya, masalah pasangan terdekat : Diberikan n poin pada bidang, temukan dua dengan jarak terkecil satu sama lain.
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.
Seseorang dapat menghitung jarak antara semua pasangan titik, yang mana ada n (n-1) / 2 , lalu pilih pasangan dengan jarak terkecil.
This brute-force algorithm takes O(n2) time; i.e. its execution time is proportional to the square of the number of points.
Ini brute-force algoritma mengambil O ( n 2 ) waktu; yaitu waktu pelaksanaannya sebanding dengan kuadrat dari jumlah poin.
A classic result in computational geometry was the formulation of an algorithm that takes O(n log n).
Hasil klasik dalam geometri komputasi adalah perumusan algoritma yang mengambil 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.
Algoritma acak yang mengambil O ( n ) waktu yang diharapkan, serta algoritma deterministik yang membutuhkan waktu O ( n log log n ), juga telah ditemukan.
The core problems in computational geometry may be classified in different ways, according to various criteria.
Masalah utama dalam geometri komputasi dapat diklasifikasikan dengan cara yang berbeda, sesuai dengan kriterianya.
Convex hull: Given a set of points, find the smallest convex polyhedron/polygon containing all the points.
Beberapa masalah mendasar dari jenis ini adalah: Convex hull : Diketahui satu set titik, temukan polihedron / poligon cembung terkecil yang berisi semua titik.
Core problems are curve and surface modelling and representation.
Masalah inti adalah kurva dan pemodelan dan representasi permukaan.
The most important instruments here are parametric curves and parametric surfaces, such as Bézier curves, spline curves and surfaces.
Instrumen terpenting di sini adalah kurva parametrik dan permukaan parametrik , seperti kurva Bézier , kurva spline , dan permukaan.
An important non-parametric approach is the level-set method.
Pendekatan non-parametrik yang penting adalah metode set level .
Application areas of computational geometry include shipbuilding, aircraft, and automotive industries.
Bidang aplikasi geometri komputasi meliputi industri pembuatan kapal, pesawat terbang, dan otomotif.