Kali ini saya akan coba menjelaskan sedikit tentang
Geometric Problems.
Geometric problem adalah suatu masalah algoritma yang membahas tentang geometry, yang mana geometry itu tidak terlepas dari titik, poligon dan garis.
Geometric problem adalah suatu masalah algoritma yang membahas tentang geometry, yang mana geometry itu tidak terlepas dari titik, poligon dan garis.
Geometric Problems
Kali ini saya akan coba menjelaskan sedikit tentang
Geometric Problems.
Geometric problem adalah suatu masalah algoritma yang membahas tentang geometry, yang mana geometry itu tidak terlepas dari titik, poligon dan garis.
Contoh Beberapa Geometric Problems
1. Segment Intersection > Ada persimpangan diberikan dua segmen, apakah mereka berpotongan?
Geometric problem adalah suatu masalah algoritma yang membahas tentang geometry, yang mana geometry itu tidak terlepas dari titik, poligon dan garis.
Contoh Beberapa Geometric Problems
1. Segment Intersection > Ada persimpangan diberikan dua segmen, apakah mereka berpotongan?
2. Simple Closed Path > mengingat satu set poin dan menemukan poligon bebas berpotong dengan simpul pada titik.
3. Inclusion in Poligon > Ini apakah titiknya berada didalam poligon tersebut atau tidak.
Titik Biru (Point ) itu adalah point yang mana biasa
dilambangkan dengan koordinat (x,y)
Warna Hijau ( Segment ) adalah bagian dari garis lurus antar dua titik.
Warna Merah ( Polygon ) adalah edaran urutan poin ( Vertex ) dan segmen ( Tepi )
Warna Hijau ( Segment ) adalah bagian dari garis lurus antar dua titik.
Warna Merah ( Polygon ) adalah edaran urutan poin ( Vertex ) dan segmen ( Tepi )
Contoh Dasar Problem Sederhana Dari
Segment Intersection
Kita bisa memulai dengan menulis persamaan garis melalui segmen, kemudian menguji apakah garisnya berpotongan. Atau kita juga bisa menggunakan cara pendekatan alternatif didasarkan pada gagasan tentang orientasi triplet memerintahkan poin dalam pesawat.
Orientasi Dalam Pesawat
Orientasi triplet
memerintahkan poin dalam pesawat ada tiga bentuk :
1. Counterclockwise ( belok ke kiri )
2. Clockwise ( belok ke arah kanan )
3. Collinear ( tidak ada pergerakan atau
perpindahan atau lurus)
Contoh
Bentuknya :
Counter clockwise clockwise
collinear
Intersection dan Orientasi
1.
Dua Segmen (p1, q1) dan (p2, q2) berpotongan
jika dan hanya jika salah satu kondisi dua diverifikasi.
2.
Kasus Umum : (p1,q1,p2) dan (p1,q1,q2)
memiliki orientasi berbeda dan (p2,q2,p1) dan (p2,q2,q1) memiliki orientasi
berbeda juga.
Contoh Kasus Umum :
Bagaimana
Cara Menghitung Orientasinya
·
Lereng Segmennya (p1,q2): s =
(y2 – y1 ) / (x2 – x1)
·
Percobaan Orientasi :
counterclockwise ( arah kiri ): s < t
clockwise ( arah kiri ): s > t
collinear ( searah ): s = t
counterclockwise ( arah kiri ): s < t
clockwise ( arah kiri ): s > t
collinear ( searah ): s = t
·
Orientasi itu sendiri bergantung pada suatu
ekspresi itu sendiri
(y2-y1) (x3-x2)- (y3-y2) (x2-x1) apakah itu positiv negatif atau sama dengan.
(y2-y1) (x3-x2)- (y3-y2) (x2-x1) apakah itu positiv negatif atau sama dengan.
Tidak ada komentar:
Posting Komentar