Kandangin Kambing pake Convex Hull (2)

Oke, setelah pada postingan kemarin sempat php (pemberi harapan palsu), kali ini akan saya kupas algoritma penyelesaian problem convex hull dengan pendekatan metode brute-force, berguna banget nih supaya kambing-kambing agan tidak lepas, monggo dinikmati...

Gagasan Awal

Ingat dengan apa yang dikatakan dosen saya pada postingan sebelumnya, bahwa

"dua titik yang membentuk garis dan menjadikan semua titik sisa berada di salah satu sisi garis, adalah titik-titik kandidat convex hull"

 adalah ide awal kita disini. Berikut ini ilustrasi tentang hal itu

titik (2,6) dan (8,7) adalah titik himpunan convex hull, karena semua titik sisa berada pada salah satu sisi dari garis tersebut. Begitu juga dengan titik (2,6) dan (1,3) adalah titik himpunan convex hull karena semua titik sisa terletak di salah satu sisi dari garis yang mereka bentuk. Lha terus gimana bos caranya kita tau kalo semua titik nimbrung di salah satu sisi garis? Kita flashback ke zaman SMA, persamaan garis berguna banget tuh untuk nylesein masalah ini.

Kanan atau Kiri yah?

Maksudnya gimana bos? Gini, let's say titik A adalah (2,6), titik B adalah (8,7) dan titik C adalah (7,4). Ke arah mana supaya garis AB mendekat ke garis AC? Kanan atau kiri? Begitu. Eh, ternyata si garis AB ke milih jalur kanan, yaudah kanan. Kalau memang garis titik A dan B adalah himpunan convex hull, garis AB harus ke arah kanan terus dong untuk mendekati semua garis yang dibentuk titik A dengan titik sisa? Mudeng?

Gambar ini mungkin bisa membantu teman-teman dalam mendapatkan arah yang harus dituju suatu garis,

Apa saya bilang, pelajaran SMA kembali membantu kita kan? Kita main-main dengan gradien di sini. Gradien yang lebih besar otomatis membentuk sudut yang lebih besar dengan titik acuan. Pada gambar di atas, gradien (baca: kemiringan) garis AB terhadap garis x = 7 lebih besar daripada kemiringan garis AC. Oleh karena itu titik C ada di sebelah kanan (baca dari bawah ke atas) dari garis AB. Berikut ini source code untuk menentukan posisi titik,

int side (dot a, dot b, dot c)
{
    int dx1 = b.x - a.x;
    int dx2 = c.x - a.x;
    int dy1 = b.y - a.y;
    int dy2 = c.y - a.y;
    if (dx1 * dy2 > dy1 * dx2)
        return -1;
    if (dx1 * dy2 < dy1 * dx2)
        return 1;
    return 0;
}

Finally...

Kita akan mengulangi langkah yang telah kita lakukan sebelumnya untuk semua titik, sehingga bisa didapatkan, running time dari algoritma ini adalah O(n³), karena untuk setiap titik yang membentuk kurva harus berhubungan dengan 2 titik lainnya dan sekalinya sudah terbentuk garis dugaan sementara, harus diperiksa, apakah semua titik yang tersisa terletak pada sisi yang sama atau tidak, berikut ini adalah hasil implementasi penyelesaian dalam bentuk code,

#include "stdio.h"
#include "math.h"
#include "string.h"

int n = 6;
typedef struct a
{
    int x, y;
} dot;

int side (dot a, dot b, dot c)
{
    int dx1 = b.x - a.x;
    int dx2 = c.x - a.x;
    int dy1 = b.y - a.y;
    int dy2 = c.y - a.y;
    if (dx1 * dy2 > dy1 * dx2)
        return -1;
    if (dx1 * dy2 < dy1 * dx2)
        return 1;
    return 0;
}

int main()
{
    dot a[n];
    for (int i = 0; i < n; i++)
        scanf ("%d %d", &a[i].x, &a[i].y);
    bool flag[n];
    memset (flag, false, n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int sisa = 0;
            if (i != j)
            {
                for (int k = 0; k < n; k++)
                    if (side (a[i], a[j], a[k]) == 1)
                        sisa++;
                if (sisa == 0 || sisa == n - 2)
                    flag[i] = flag[j] = true;
            }
        }
    }
    printf ("ans :\n");
    for (int i = 0; i < n; i++)
        if (flag[i])
            printf ("%d %d\n", a[i].x, a[i].y);
}

Silahkan dipelajari, masih ada kekurangan di bagian outputnya. Output belum tercetak secara teratur, seharusnya output ditulis dalam urutan searah jarum jam atau berlawanan arah jarum jam. Dari segi optimasi code, masih ada beberapa yang temen-temen bisa perbaiki. Baik, sekarang tiba di penghujung posting, semoga apa yang saya tulis bermanfaat. Terima kasih sudah mau mampir di blog ane, semoga kambing-kambing kita tidak lepas ya bro, sayonara...