31 December 2010

SINGLE LINKED LIST


Link list merupakan list yang setiap anggotanya mempunyai kait ke data berikutnya. Cara ini menyebabkan anggota list tidak harus menempati tempat yang saling berdekatan.
Untuk memudahkan dalam pemahaman single link list, berikut ini contoh kasus dan penyelesaian single link list.

Contoh Kasus
Suatu perusahaan mebel “PT SINAR AGUNG“ merupakan perusahaan yang baru saja diresmikan ingin mendata seluruh karyawannya. Tiap karyawan memilki data berikut :
-   Nama karyawan
-   Alamat rumah
-   Telepon
Pendataan karyawan tersebut dilakukan dengan penyisipan depan, tengah dan belakang, serta akan  dilakukan penghapusan jika nama karyawan tersebut salah dengan cara penghapusan didepan, ditengah dan dibelakang.

Untuk penyelesaian dari kasus di atas, silakan Download di sini. 


Berikut ini tampilan dari aplikasi yang dibuat :


MINIMUM SORT SECARA ASCENDING

Langkah-langkah MINIMUM SORT secara Ascending

Tahap–tahap penyusunan algoritma seringkali dimulai dari langkah yang global lebih dahulu. Langkah global ini diperhalus sampai langkah yang lebih rinci. Pendekatan desain algoritma seperti ini dinamakan penghalusan langkah atau perancangan puncak turun (top-down design). Cara pendekatan ini sangat bermanfaat dalam membuat algoritma untuk masalah yang cukup rumit atau kompleks. Gagasan penghalusan langkah adalah memecahkan proses menjadi beberapa langkah. Tiap langkah diuraikan lagi menjadi beberapa langkah yang lebih sederhana. Penghalusan langkah terus berlanjut sampai tiap langkah sudah sampai rinci dan tepat untuk dilaksanakan pemroses.
Penghalusan langkah yang akan dibahas yaitu pengurutan minimum menaik (minimum sort secara ascending). Sebagai contoh penghalusan langkah, tinjau masalah pengurutan data sebagai berikut:
Diberikan N buah data bilangan bulat yang tersusun secara acak. Kita diminta menyusun suatu algoritma untuk mengurutkan sekumpulan data tersebut sehingga tersusun terurut dari nilai data yang terkecil sampai nilai data yang terbesar.
Algoritma pengurutan yang cukup sederhana adalah dengan mencari elemen yang terkecil didalam kumpulan mulai dari data ke-1 sampai data ke-N, lalu menempatkannya pada posisi data pertama (dengan cara mempertukarannya dengan data pertama). Karena data yang pertama sudah menempati tempat yang sudah benar, selanjutnya dicari lagi elemen elemen terkecil di dalam kumpulan mulai data ke-2 sampai data ke-N, lalu menempatkannya pada data kedua. Karena data pertama dan kedua sudah terurut, selanjutnya dicari lagi elemen yang terkecil dari data ke-3 sampai data ke-N, lalu menempatkannya pada posisi data ketiga, begitu seterusnya samapi tersisa satu data yang belum terurut. Karena data yang terakhir tinggal satu-satunya maka sudah data tersebut sudah pada posisi yang benar. Jadi, algoritma pengurutan ini sebenarnya ada dua langkah yaitu :
1. Mencari elemen terkecil
2. Pertukaran

Kedua langkah ini diulang sebanyak N-1 kali (satu data terakhir yang tersisa tidak perlu diurutkan lagi karena sudah pada posisi yang benar). Setiap pengulangan langkah ini disebut pass atau lelaran (iteration). Pada setiap pass ke-k, kita cari data terkecil (min) mulai dari data ke-k sampai data ke-N, lalu pertukaran min dengan elemen ke-k.

Dari keterangan di atas dapat disimpulkan bahwa :
Untuk setiap pass ke-I = 1,2,3, … , N-1 lakukan :
1. Cari elemen terkecil (min) mulai dari elemen ke-I sampai dengan elemen ke-N
2. Pertukaran min dengan elemen ke-I.
Rincian setiap pass adalah sebagai berikut :
Pass 1 : Cari elemen terkecil di dalam L[1..N]
Pertukaran elemen terkecil dengan elemen L[1]
Pass 2 : Cari elemen terkecil di dalam L[2..N]
Pertukaran elemen terkecil dengan elemen L[2]
Pass 3 : Cari elemen terkecil di dalam L[3..N]
Pertukaran elemen terkecil dengan elemen L[3]

Pass N-1: Cari elemen terkecil di dalam L[1..N]
Pertukaran elemen terkecil dengan elemen L[1]

(elemen yang tersisa adalah L[N], tidak perlu diurut karena hanya satu-satunya)

Untuk langkah-langkah dan algoritma minimum sort, silakan Download di sini.

MERGE SORT

DEFINISI MERGE SORT

Pengurutan algoritma Merge Sort membuat pengurutan dengan membagi 2 dan menggabungkannya. Metoda ini cukup efisien untuk diterapkan. Sama dengan Quick Sort, algoritma Merge Sort adalah dasar pembagian dan penyelesaiannya. Pertama urutan atau elemen data awal diurutkan dengan membaginya menjadi 2 bagian (Devide). Setengahnya diurutkan dengan bebas (Conquer). Kemudian 2 bagian itu digabungkan dengan cara diurut sesuai dengan urutan (Combine).
Untuk lebih jelas perhatikan gambar dibawah ini.



Perhatikan contoh procedure pengurutan merge sort dari index lo ke index hi.


Pertama, index m yang berada di tengah diantara lo dan hi adalah faktor. Kemudian urutan pertama( dari lo ke m ) dan bagian kedua ( dari m+1 ke hi ) diurutkan berulang yang disebut mergesort. Kemudian dua bagian yang sudah diurutkan digabungkan oleh procedure merge. Perulangan berakhir ketika lo = hi, dan ketika yang berikutnya hanya memiliki satu elemen.

- Download contoh algoritma Mergesort

- Download contoh program C Mergesort

30 December 2010

QUICK SORT

Soal :
Bila terdapat data acak sebagai berikut :
16 12 23 50 19 49 31
Bila akan diurutkan secara descending dengan menggunakan metode quick sort maka hasil yang menjadi pivot pada tahap pertama adalah…..
Sebelum menyelesaikan soal di atas, terlebih dahulu dicari pengertian pivot. Kami telah mendapatkan 5 referensi buku untuk mendapatkan pengertian dan cara pengambilan pivot.

a. Buku Referensi 1
Algoritma dan Pemograman
Oleh : Antony Pranata
Penerbit : Graha Ilmu


Cara pengambilan pivot didapat dari L = 1 (data 1) dijumlahkan dengan R = N(jumlah data), kemudian dibagi 2. Tujuan dari pemilihan pivot adalah mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Misal pivot dilambangkan dengan x. Pivot harus diletakkan pada posisi ke-j sedemikian hingga data antara 1 sampai dengan (j-1) lebih kecil daripada x; sedangkan data pada posisi ke (j+1) sampai dengan N lebih besar daripada x. Cara pengaturannya adalah menukarkan data diantara posisi (j+1) sampai dengan N yang lebih besar daripada x dengan data diantara posisi (j+1) sampai dengan N yang lebih kecil daripada x. Dan untuk cara descending kebalikannya.
Jadi, untuk soal di atas dengan metode yang ada pada buku ini maka yang menjadi pivot pada tahap pertama yaitu :
data :
1 2 3 4 5 6 7
16 12 23 50 19 49 31


x ← data[(L + R) div 2]
x ← data[(1 + 7) div 2]
x ← data[8 div 2]
x ← data[4]
Jadi, pivot pada tahap pertama adalah data ke-4 yaitu 50.

b. Buku Referensi 2
Algoritma dan Struktur Data dengan C++
Oleh : Indra Yatini B
Erliansyah Nasution
Penerbit : Graha Ilmu


Pada buku ini dijelaskan bahwa pivot merupakan suatu elemen pembanding yang membandingkan elemen disebelah kirinya dan sebelah kanannya. Untuk memilih pivot, kita tidak harus memilih item pertama dalam daftar. Kita bisa memilih setiap item yang kita inginkan dan menukarkannya dengan item pertama sebelum memulai loop yang memisahkan daftar. Sebenarnya, item pertama dalam daftar sering merupakan pilihan buruk untuk dijadikan pivot, karena jika datar telah terurut, maka tidak ada kunci yang kurang darinya sehingga satu subdaftar akan kosong. Lebih baik memilih pivot dekat dengan tengah daftar, dengan harapan pilihan kita akan memisahkan kunci masing-masing separuh bagian.
Jadi, dalam buku ini pemilihan pivot dapat diambil didata manapun, tetapi diusahakan dekat dengan tengah.

c.Buku Referensi 3
Struktur Data dengan C++
Oleh : Andri Kristanto
Penerbit : Graha Ilmu


Pada buku ini, pemilihan pivot tidak terlalu berbeda dengan buku referensi pertama. Pengambilan pivotnya yaitu dengan menjumlahkan data 1 dengan banyaknya data kemudian dibagi 2, sehingga nilai pivotnya berada ditengah yaitu pada data ke-4, yaitu 50. Tapi hanya ada sedikit perbedaan dalam pengerjaannya yaitu dalam buku referensi 1, penyelesaian dilakukan disebelah kiri dulu kemudian data disebelah kanan dan pivot pertama menjadi j. Sedangkan dalam buku ini, nilai j ada pada data terakhir sampai (j-1).

d.Buku Referensi 4
Berpetualang dengan Struktur Data di Planet Pascal
Oleh : Dwi Sanjaya
Penerbit : J & J Learning Yogyakarta


Pivot adalah elemen yang membandingkan elemen dengan elemen lain dan menyusunnya sedemikian rupa. Cara pengambilan pivotnya pun sama dengan buku referensi 1 dan buku referensi 3, yaitu dengan rumus :
x ← data[(L + R) div 2]
Sehingga pivot pertamanya akan berada ditengah. Jika dari soal di atas, pivot pada tahap pertama adalah data ke-4 yaitu 50.

e.Buku Referensi 5
Algoritma Teknik Penyelesaian dan Permasalahan untuk Komputasi
Oleh : Edi Sutanto
Penerbit : Graha Ilmu


Pivot adalah suatu pembanding elemen data dengan elemen data lainnya yang diurutkan secara urut naik maupun urut turun. Cara pengambilan pivotnya mempunyai kesamaan dengan buku referensi 2, yaitu pengambilan pivotnya bisa diambil didata manapun tapi diusahakan mendekati tengah dan membagi array menjadi 2 bagian.


Penyelesaian :
Soal di atas akan dicoba untuk diselesaikan dengan cara descending dan dikerjakan sesuai dengan metode yang ada dibuku referensi 4 yaitu Berpetualang dengan Struktur Data di Planet Pascal.

Diketahui : Bila terdapat data acak sebagai berikut :

16 12 23 50 19 49 31
Data tersebut akan diselesaikan dengan metode quicksort secara descending.

Langkah 1 :
Tentukan pivot pada array. Misalkan pivot adalah x.
x ← data[(L+R) div 2]
x ← data[(1 + 7) div 2]
x ← data[8 div 2]
x ← data[4]
i ← L
j ← R

data 1 2 3 4 5 6 7
16 12 23 (50) 19 49 31

i → ← j
i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang <= pivot. j bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang >= pivot.

i berhenti pada data ke-1 karena langsung menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-4 karena tidak menemukan nilai yang lebih besar daripada pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 12 23 16 19 49 31


Langkah 2 :
data 1 2 3 4 5 6 7
50 12 23 (16) 19 49 31

i → ← j
i berhenti pada data ke-2 karena menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-7 karena langsung menemukan nilai yang lebih besar dari pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 31 23 16 19 49 12


Langkah 3 :
Data 1 2 3 4 5 6 7
50 31 23 (16) 19 49 12

i → ← j
i berhenti pada data ke-4 karena tidak menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-6 karena menemukan nilai yang lebih besar dari pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 31 23 49 19 16 12


Langkah 4 :
Data 1 2 3 4 5 6 7
50 31 23 (49) 19 16 12

i → ← j
i berhenti pada data ke-2 karena menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-4 karena tidak menemukan nilai yang lebih besar dari pivot.
Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 49 23 (31) 19 16 12


Langkah 5 :
Data 1 2 3 4 5 6 7
50 49 23 (31) 19 16 12

i → ← j
i berhenti pada data ke-3 karena menemukan nilai yang lebih kecil dari pivot.
j berhenti pada data ke-4 karena tidak menemukan nilai yang lebih besar dari pivot.

Karena i < j maka data yang ditunjuk oleh i ditukar dengan data yang ditunjuk oleh j sehingga menjadi:

50 49 31 23 19 16 12

Proses pengurutan berhenti karena i tidak menemukan data yang lebih kecil dari x dan j tidak menemukan data yang lebih besar dari x.


Algoritma Pengurutan
procedure quicksort_secara_descending ( i/o data : larik, input L, R : char)
{ I.S : elemen data array sudah terdefinisi }
{ F.S: menghasilkan elemen data array yang sudah terurut secara descending }

Deklarasi :
i, j, x, temp: char
Deskripsi :
x ← data[(L + R) div 2]
i ← L
j ← R

while i ≠ j do
while data[i] > x do
i = i + 1
endwhile
while
data[j] < x do
j = j – 1
endwhile
if
i ≠ j then
temp ← data[i]
data[i] ← data[j]
data[j] ← temp
i ← L
j ← R
endif
endwhile
endprocedure

29 December 2010

Aplikasi Transformasi 2 Dimensi

Transformasi 2 Dimensi

Ini program yang saya buat sendiri ketika masih di bangku kuliah buat tugas besar komputer grafik. Iseng-iseng saya posting di blog. Mudah-mudahan bisa bermanfaat.
Berikut ini contoh pengujian aplikasi transformasi 2 dimensi.

1.Translasi
Untuk menggambarkan translasi suatu objek berupa segitiga dengan koordinat A (1,1 ), B ( 3, 0), dan C (1,3) dengan tx,ty(1,2).tentukan koordinat yang barunya?
Jawab
A : x‘=1+1=2
y‘=1+2=3
A‘=(2,3)

B : x‘=3+1=4
y‘=1+2=3
B‘=(4,3)

C : x‘=1+1=2
y‘=3+2=5
C‘=(2,5)

Gambar Penginputan Data


Gambar Hasil Perhitungan Translasi


2. Penskalaan
Untuk menggambarkan skala suatu objek berupa segitiga dengan koordinat A (1,1) B(3,1) dan C(1,3) dengan (sx,sy) (3,2),tentukan koordinat yang barunya ?
Jawab

A : x‘=1*3=3
y‘=1*2=2
A‘=(3,2)

B : x‘=3*3=9
y‘=1*2=2
B‘=(9,2)

C: x‘=1*3=3
y‘=3*2=6
C‘=(3,6)

Gambar Penginputan Data


Gambar Hasil Perhitungan Skala


3. Perputaran ( Rotasi)
Untuk menggambarkan rotasi suatu objek berupa segitiga dengan koordinat A(1,1),B(3,1) dan C (1,3) dengan sudut rotasi 300 terhadap titik pusat cartesian (1,1), dilakukan dengan menghitung koordinat hasil rotasi tiap titik satu demi satu.
Jawab
Titik A
x′ = xr + ( x - xr ) cos θ - ( y - yr ) sin θ
= 1 + (1-1)* 0,9 - (1-1) * 0,5= 1
y′ = yr + ( x - xr ) sin θ + ( y - yr ) cos θ
= 1 + (1-1) * 0,5 + (1-1) * 0,9= 1
Titik A’(1,1)

Titik B
x′ = xr + ( x - xr ) cos θ - ( y - yr ) sin θ
= 1+ (3-1)* 0,9 - (1-1)*0,5=2,8
y′ = yr + ( x - xr ) sin θ + ( y - yr ) cos θ
= 1 + (3-1)* 0,5+ (1-1) * 0,9 = 2
Titik B’(2,8 , 2)

Titik C
x′ = xr + ( x - xr ) cos θ - ( y - yr ) sin θ
= 1+ (1-1) * 0,9 - (3-1) *0,5 = 0
y′ = yr + ( x - xr ) sin θ + ( y - yr ) cos θ
= 1 + (1-1) * 0,5 + (3-1) * 0,9 = 2,8
Titik C’(0, 2,8)

Gambar Penginputan Data


Gambar Hasil Perhitungan Rotasi


4. Refleksi
Untuk menggambarkan refleksi suatu objek berupa segitiga dengan koordinat A (1,1) B(3,1) dan C(1,3) terhadap sumbu x, sumbu y,sumbu x => y, dan sumbu x=y,tentukan koordinat yang barunya ?
Jawab

Terhadap sumbu x
A’(1,-1)
B‘ (3,-1)
C‘(1,-3)
Terhadap sumbu y
A’(-1,-1)
B‘ (-3,-1)
C‘(-1,-3)

Terhadap sumbu x=> y
A’(1,1)
B‘ (3,1)
C‘(1,3)
Terhadap sumbu x = y
A’(1,1)
B‘ (1,3)
C‘(3,1)

Gambar Penginputan Data


Gambar Hasil Perhitungan Refleksi terhadap sumbu x


Gambar Hasil Perhitungan Refleksi terhadap sumbu y


Gambar Hasil Perhitungan Refleksi terhadap sumbu x=> y


Gambar Hasil Perhitungan Refleksi terhadap sumbu x=y


4. Shear
Transformasi shear dengan nilai shx=2 dengan koordinat A (1,1) B (3,1) C (3,3) dan D (1,3).
Jawab
Terhadap sumbu x
Titik A ( 1,1 )
x′ = 1 + 2 . 1=3
y′ = 1
A‘= ( 3,1 )
Titik B ( 3,1 )
x′ = 3 + 2 . 1=5
y′ = 1
B‘= ( 5,1 )
Titik C ( 3,3)
x′ = 3 + 2 . 3=9
y′ = 3
C‘= ( 9,3 )
Titik D ( 1,3 )
x′ = 1 + 2 . 3=7
y′ = 3
D‘= ( 7,3 )

Gambar Penginputan Data


Gambar Hasil Perhitungan Shear terhadap sumbu x


Terhadap sumbu y
Titik A ( 1,1 )
x′ = 1
y′ = 2.1+1=3
A‘= ( 1,3 )
Titik B ( 3,1 )
x′ = 3
y′ = 2.3+1=7
B‘= ( 3,7 )
Titik C ( 3,3)
x′ = 3
y′ =2.3+3=9
C‘= ( 3,9 )
Titik D ( 1,3 )
x′ = 1
y′ = 2.1+3=5
D‘= ( 1,5 )

Gambar Hasil Perhitungan Shear terhadap sumbu y

Catatan: Bila Anda penasaran dengan aplikasi transformasi 2 dimensi ini, silakan Download di sini.

Rumus Transformasi 2 Dimensi

Rumus Transformasi

Rumus perhitungan untuk setiap transformasi, yaitu :
a. Translasi
Rumus yang digunakan, yaitu :
x′ = x + tx
y′ = y + ty

Keterangan :
x′ : koordinat x yang dibentuk setelah translasi
x : koordinat x awal
tx : besarnya translasi (perpindahan) x
y′ : koordinat y yang dibentuk setelah translasi
y : koordinat y awal
ty : besarnya translasi (perpindahan) y

b. Skala
Jenis perhitungan skala berdasarkan faktor skala, dan fixed point.
1)Rumus yang digunakan berdasarkan faktor skala, yaitu :
x′ = x . sx
y′ = y . sy

Keterangan :
x′ : koordinat x yang dibentuk setelah penskalaan
x : koordinat x awal
sx : besarnya penskalaan x
y′ : koordinat y yang dibentuk setelah penskalaan
y : koordinat y awal
sy : besarnya penskalaan y

2)Rumus yang digunakan berdasarkan fixed point, yaitu :
x′ = x . sx + xf (1 - sx )
y′ = y . sy+ yf (1 - sy )

Keterangan :
x′ : koordinat x yang dibentuk setelah penskalaa
x : koordinat x awal
sx : besarnya penskalaan x
xf : besar fixed point x
y′ : koordinat y yang dibentuk setelah penskalaan
y : koordinat y awal
sy : besarnya penskalaan y
yf : besar fixed point y

c.Rotasi
Jenis perhitungan rotasi berdasarkan sudut putaran, dan pivot point.
1)Rumus yang digunakan berdasarkan sudut putaran, yaitu :
x′ = x cos θ - y sin θ
y′ = x sin θ + y cos θ

Keterangan :
x′ : koordinat x yang dibentuk setelah penskalaan
x : koordinat x awal
θ : besar sudut
y′ : koordinat y yang dibentuk setelah penskalaan
y : koordinat y awal

2)Rumus yang digunakan berdasarkan pivot point, yaitu :
x′ = xr + ( x - xr ) cos θ - ( y - yr ) sin θ
y′ = yr + ( x - xr ) sin θ + ( y - yr ) cos θ

Keterangan :
x′ : koordinat x yang dibentuk setelah rotasi
x : koordinat x awal
xr : titik putar x
θ : besar sudut
y′ : koordinat y yang dibentuk setelah penskalaan
y : koordinat y awal
yr : titik putar y

d.Refleksi
Rumus yang digunakan untuk pencerminan objek ini, yaitu :
1)Terhadap sumbu x
x′ = x
y′ = -y

Keterangan :
x : koordinat x awal
y : koordinat y awal
x′ : koordinat x yang dibentuk setelah pencerminan
y′ : koordinat y yang dibentuk setelah pencerminan

2)Terhadap sumbu y
x′ = -x
y′ = y

Keterangan :
x : koordinat x awal
y : koordinat y awal
x′ : koordinat x yang dibentuk setelah pencerminan
y′ : koordinat y yang dibentuk setelah pencerminan

3)Terhadap sumbu x → y
x′ = -x
y′ = -y

Keterangan :
x : koordinat x awal
y : koordinat y awal
x′ : koordinat x yang dibentuk setelah pencerminan
y′ : koordinat y yang dibentuk setelah pencerminan

4)Terhadap sumbu x = y
x′ = y
y′ = x

Keterangan :
x : koordinat x awal
y : koordinat y awal
x′ : koordinat x yang dibentuk setelah pencerminan
y′ : koordinat y yang dibentuk setelah pencerminan

e.Shear
Rumus yang digunakan untuk mengubah sisi objek (distorsi), yaitu :
1)Terhadap sumbu x
x′ = x + shx . y
y′ = y

Keterangan :
x : koordinat x awal
y : koordinat y awal
x′ : koordinat x yang dibentuk setelah pencerminan
y′ : koordinat y yang dibentuk setelah pencerminan
shx : shear x
shy : shear y

2)Terhadap sumbu y
y′ = shy . x + y
x′ = x

Keterangan :
x : koordinat x awal
y : koordinat y awal
x′ : koordinat x yang dibentuk setelah pencerminan
y′ : koordinat y yang dibentuk setelah pencerminan
shx : shear x
shy : shear y

Grapika Komputer dan Transformasi

Grapika Komputer

Grafik komputer adalah salah satu cabang disiplin ilmu informatika yang mempelajari pembuatan gambar dengan menggunakan komputer. Perbedaan antara grafik komputer dengan pengolahan citra adalah dalam pengolahan citra, gambar input kedalam proses pengolahan citra sudah tersedia, sedangkan pada grafik komputer dilakukan proses untuk menciptakan gambar dari awal.
Grafik 2 Dimensi merupakan teknik penggambaran pada layar (monitor) dengan berpatokan pada titik koordinat sumbu x (datar) dan sumbu y (tegak). Pada monitor komputer, koordinat tersebut dihitung mulai dari sudut kiri atas layar. Semakin ke kanan, nilai koordinat x semakin bertambah. Semakin ke bawah, nilai koordinat y semakin bertambah. Besarnya nilai koordinat ini dihitung dalam satuan pixel.
Salah satu bagian dari grafika komputer adalah pemodelan objek (objek modelling). Dalam pemodelan objek dua dimensi (2D), didapati berbagai objek dapat dimodelkan. Menurut kondisi tertentu, objek yang dimodelkan itu perlu dimodifikasi. Pemodifikasian objek ini dapat dilakukan dengan melakukan berbagai operasi fungsi atau operasi transformasi geometri.


Transformasi

Transformasi ini dapat berupa trasformasi dasar ataupun gabungan dari berbagai transformasi geometri. Contoh trasformasi geometri adalah translasi, penskalaan, putaran (rotasi), balikan, shearing dan gabungan. Transformasi ini dikenal dengan transformasi affine. Pada dasarnya, transformasi ini adalah memindahkan objek tanpa merusak bentuk. Satu contoh transformasi adalah transformasi dari jendela (window) ke viewport. Disini kita telah melihat citra dalam jendela dunia diskala dan dipindahkan ke jendela viewport. Dalam bagian ini akan dibahas transformasi objek 2D dan 3D yang terdiri dari translasi, skala, putar(rotasi) dan shearing.
Transformasi dapat dilakukan dengan dua operasi, yaitu operasi matrik, dan operasi vektor.

1.Operasi matrik
a.Penambahan dan pengurangan
b.Perkalian
c.Determinan
d.Transpos
e.Kebaikan (inverse)

2.Operasi vector
a.Penambahan dan pengurangan
b.Pekalian titik (dot product)
c.Perkalian silang (cross product)


Tujuan Transformasi

Adapun tujuan dari transformasi, yaitu :
1.Merubah atau menyesuaikan komposisi pemandangan.
2.Memudahkan membuat objek yang simetris.
3.Melihat objek dari sudut pandang yang berbeda.
4.Memindahkan satu atau beberapa objek dari satu tempat ke tempat lain, ini biasa dipakai untuk animasi komputer.



Jenis Transformasi Dasar

1. Translasi
Translasi dilakukan dengan penambahan translasi pada suatu titik koordinat dengan translation vector atau shift vector, yaitu (tx, ty). Koordinat baru titik yang ditranslasi dapat diperoleh dengan menggunakan rumus :
x’ = x + tx
y’ = y + ty
Translasi adalah transfomasi dengan bentuk yang tetap memindahkan objek apa adanya.Titik yang akan ditranslasi akan dipindahkan ke lokasi lain menurut garis lurus.

2.Penskalaan
Transformasi skala adalah perubahan ukuran suatu objek. Koordianat baru diperoleh dengan melakukan perkalian koordinat dengan ascling faktor,yaitu (sx,sy) dimana sx adalah scaling factor untuk sumbu sx dan sy adalah scaling faktor untuk sumbu y. Koordinat baru titik yang diskala dapat diperoleh dengan
x’ = x.sx
y’ = y.sy
Scaling factor sx dan sy dapat diberikan sembarangan nilai positif. Nilai lebih dari 1 menandakan bahwa sebuah objek diperbesar sedang nilai nilai kurang dari 1 menunjukan bahwa objek diperkecil

3.Rotasi
Rotasi dua dimensi memindahkan sebuah objek menurut garis melingkar. Untuk melakukan rotasi diperlukan sudut rotasi a’ dan pivot point(xp,yp). Nilai positif dari sudut rotasi menentukan arah rotasi berlawanan dengan arah jarum jam. Sedangkan sudut rotasi negative memutar objek searah dengan jarum jam.
Rumus transformasi untuk rotasi suatu titik(x,y) dengan sudut rotasi a sebagai
berikut:
x’= x cos a - y sin a
y’= y sin a + y cos a

4.Refleksi
Refleksi adalah transfomasi membuat mirror dari suatu objek. Objek hasil refleksi dibuat relatif terhadap sumbu dari refleksi dengan memutar 180' terhadap sumbu refleksi. Sumbu refleksi dapat dipilih pada bidang xy. Jenis -
jenis refleksi ada berbagai macam tetapi algoritma yang digunakan semua sama tinggal mengubah matriks transfomasinya saja.

5.Shear
Shear yaitu transformasi yang mengubah sisi objek.