Geometry Poblem

Geometry problem adalah permasalahan yang berhubungan dengan titik , garis dan bidang geometri lainnya yang akan diterjemahkan dalam bentuk komputasi.

Ada 2 masalah klasik dalam geometry problem yaitu:

1. Convex hull : pencarian poligon cembung terkecil, melibatkan semua titik yang ditentukan       

   

Adalah permasalahan yang digambarkan dalam ruang bidang, dari kumpulan titik dibuat kedalam bentuk poligon yang konveks. poligon dikatakan konveks jika garis itu berhubungan antar titik maka tidak ada garis yang memotong garis yang menjadi batas luar poligon. 



Dalam pembuatan poligon terdapat dua bagian yang memisahkan bidang yaitu derah kanan dan daerah kiri yang dilihat dari garis orientasinya dalam bentuk sumbu kooordinat.

Contoh

 

Lihat sumbu vertikal yang miring, seluruh titik di sebelah kanan garis memiliki kemiringan lebih miring dari kiri maka disebut nilai horizontalnya (X) positif sedangkan seluruh titik di sebelah kiri garis kemiringannya lebih rendah maka nilai komponen koordinat horizontal negatif.
 
Maka poligon diatas bisa digunakan untuk menentukan aksi awal yaitu titik yang berada paling luar pertama. Mencari titik pertama yaitu memilih titik yang memiliki nilai komponen koordinat (horizontal atau vertikal) atau kemiringan yang tinggi (minimum atau maksimum). maka penentuan titik convex hull lainnya ditentukan berdasarkan darititik pertama.

Berikut adalah langkah singkatnya :

• memilih titik pertama

•  memilih titik berikutnya, berdasarkan yang pertama.

• jika dibuat garis dengan titik sebelumnya maka seluruh titik lainnya tidak ada yang berada di sebelah kiri.

• jika titik tersebut sesuai maka masukkan kedalam daftar titik luar. 

Algoritma yang digunakan adalah menggunakan pendekatan exhaustive (brute-force).terdiri dari tiga bagian yaitu pengurutan titik, penyusunan batas bagian atas, dan penyusunan batas bagian bawah.
 
2. Problem closest pair : pemberian titik di suatu bidang, dan cari pasangan  terdekatnya

Cara untuk memecahkan masalah ini adalah membandingkan semua titik-titiknya untuk dicari jaraknya. Untuk menentukan jarak antar titik digunakan persamaan berikut.

x dan y merupakan koordinat titik yang diperbandingkan. Algoritma bisa menggunakan brute force, dengan cara kerja terus mencoba semua titik sampai mendapatkan nilai d yang terkecil.

Sumber : http://analisis-algoritma12.blogspot.co.id/2016/09/geometry-problem.html

              https://icomit.wordpress.com/2010/12/24/cara-implementasi-algoritma-closest-pair-point-di-java/