Page 207 - EMODUL - PENGOLAHAN CITRA DIGITAL
P. 207

konveks jika di seluruh pasangan dua  titik yang terkandung di dalamnya dibentuk


                        oleh garis yang seluruhnya berada dalam S. Dengan demikian, Gambar 11.4(b)

                        bukanlah bentuk konveks karena garis contoh menghasilkan titik di luar objek.


                                    (a) Himpunan konveks   (b) Bukan Himpunan konveks














                                             Gambar 11. 4 Konveks dan bukan konveks



                                            Tabel 11. 2 Berbagai algoritma convex hull
                                    Algoritma              Kinerja                Penemu
                                                                    3
                                                          4
                             Brute Force               O(n ) dan O(n )    Tidak diketahui
                             Graham Scan               O(n log n)         Graham, 1972
                             Gift Wrapping             O(nh)              Jarvis, 1973
                             QuickHull                 O(nh)              Eddy, 1977
                             Divide-and-Conquer        O(n log n)         Preparata & Hong, 1977
                             Monotone Chain            O(n log n)         Andrew, 1979
                             Incremental               O(n log n)         Kallay, 1984
                             Marriage-                 O(n log h)         Kirkpatrick & Seidel,
                             beforeConquest                               1986

                               Dasar untuk memperoleh convex hull pada algoritma Graham Scan dibagi

                        menjadi tiga tahap.


                           1.  Perolehan titik p0 di dalam himpunan P yang berisi kumpulan titik. Titik p0
                               ini biasa disebut sebagai titik jangkar atau pivot. Caranya adalah dengan

                               mencari titik yang mempunyai nilai ordinat Y terkecil. seandainya terdapat
                               beberapa nilai Y yang memenuhi hal itu, dicari nilai X yang paling kecil.

                           2.  Penghitungan  sudut  semua  titik  di  dalam  P,  selain  p0  terhadap  p0.

                               Kemudian,  semua  titik  di  dalam  P  selain  p0  diurutkan  secara  radial
                               berlawanan dengan arah jarum jam.


                                                                                                   207
   202   203   204   205   206   207   208   209   210   211   212