Geometry Problem

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 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?

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.

Note :

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 )

Contoh Dasar Problem Sederhana Dari Segment Intersection

1.       Cobalah, apakah segmen (a,b) dan (c,d) saling berpotongan? Bagaimana kita mengetahuinya?


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)

·         Lereng Segmennya (p2,p3): t = (y3 – y2) / (x3 – x2)

·         Percobaan Orientasi :
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.

sumber : http://www.cse.iitd.ernet.in/~amitk/cs201/Geometry.ppt