Tipe Problem : Geometric Problem (Beragam Masalah)
- Berkaitan dengan objek geometrik : titik, garis,poligon dan lain-lain
- Yunani Kuno : membangun geometrik sederhana ,contohnya segitiga, lingkaran dan lain-lain
- Masa kini : aplikasi komputer • grafik, robot
- Problem closest pair : diberikan titik pada suatu bidang, dan temukan pasangan terdekatnya
- Convex hull : temukan poligon cembung terkecil yang melibatkan smeua titik yang telah
ditentukan
poligon
Sebuah poligon hanya kumpulan segmen garis, membentuk suatu siklus, dan tidak melintasi satu sama lain. Kami dapat mewakilinya sebagai urutan poin, yang masing-masing hanya sepasang koordinat. Misalnya poin (0,0), (0,1), (1,1), (1,0)
membentuk persegi.
Segmen garis poligon menghubungkan titik yang berdekatan dalam daftar, bersama-sama dengan satu segmen tambahan menghubungkan titik pertama dan terakhir.
Tidak semua urutan poin membentuk poligon; misalnya poin (0, -1), (0,1), (1,0), (0, -1) akan menghasilkan dua segmen yang saling silang.
Kadang-kadang kita menggunakan frase poligon sederhana untuk menekankan persyaratan bahwa tidak ada dua segmen menyeberang.
Rincian dari rutinitas point-in-poligon
Biasanya ketika kita melakukan geometri komputasi, kami baru saja berhenti di sini. Semua sisanya adalah rincian untuk diisi hanya jika Anda benar-benar menulis sebuah program. Tapi itu berguna untuk melihat, setidaknya sekali, apa yang semacam ini detail terlihat seperti.
Seperti yang akan kita lihat, kita juga perlu sedikit lebih berhati-hati: penyeberangan juga dapat terjadi pada simpul dari poligon, dan kami belum memeriksa apakah (x, y) duduk persis di perbatasan. Pertama mari kita lihat bagaimana menerapkan langkah-langkah ini pseudo-code.
Bagaimana kita tahu apakah sinar turun dari (x, y) melintasi segmen antara dua titik (x1, y1) dan (x2, y2)? Semua poin dari ray memiliki sama pertama koordinat x. Jika ini adalah untuk menjadi antara (x1, y1) dan (x2, y2) maka x harus antara x1 dan x2; baik (x1 <x dan x <x2) atau (x1> x dan x> x2). Kita bisa menulis ini lebih ringkas sebagai (x1-x) (x2-x) <0 tapi ini mungkin benar-benar lambat karena melibatkan perkalian presisi tinggi.
Sekarang anggaplah x adalah antara x1 dan x2. Dimana titik persimpangan? Apakah ia memiliki berkoordinasi lebih kecil kedua dari y? Salah satu definisi dari garis ditentukan oleh poin (x1, y1) dan (x2, y2) adalah bahwa hal itu terdiri dari semua titik dalam bentuk
(T x1 + (1-t) x2, t y1 + (1-t) y2)
di mana nilai-nilai yang berbeda dari t memberikan poin yang berbeda pada baris. Untuk menemukan mengkoordinasikan kedua persimpangan, mari kita gunakan diketahui nilai koordinat pertama untuk memecahkan t:
x = t x1 + (1-t) x2
t = (x - x2) / (x1 - x2)
persimpangan = (x, t y1 + (1-t) y2)
Perhatikan bahwa kita juga bisa mengetahui apakah (x, y) adalah tepat pada segmen garis dengan menguji apakah y = crossing. Berikut sedikit masalah: rumus ini mungkin melibatkan pembagian dengan nol. Tapi dalam kasus x1 = x2 sehingga x tidak bisa antara keduanya. Selama kita hanya menghitung t ketika x adalah antara x1 dan x2, kita aman. Mari kita pasang formula ini menjadi pseudo-kode kita. Kami akan membiarkan n menunjukkan jumlah titik dalam poligon, dan P (i) .v dan P (i) .v menunjukkan koordinat titik (i mod n).
int penyeberangan = 0
for (int i = 0; i <n; i ++)
if ((P (i) .v <x && x <P (i + 1) .v) || (P (i) .v> x && x> P (i + 1) .v))
{
t = (x - P (i + 1) .v) / (P (i) .v - P (i + 1 .x))
cy = t * P (i) .v + (1-t) * P (i + 1) .v
jika (y == cy) kembali (pada batas)
lain jika (y> cy) penyeberangan ++;
}
jika (penyeberangan ganjil)
kembali (dalam);
lain kembali (luar);
Akhirnya, apa yang terjadi jika sinar dari (x, y) melewati persis melalui titik P? Kadang-kadang ini harus dihitung sebagai persimpangan, tapi kadang-kadang ray hanya "merumput" P dan seharusnya tidak dihitung sebagai persimpangan. Ada banyak kasus untuk mempertimbangkan, jadi ini mungkin membingungkan. Sebuah cara standar untuk memotong melalui semacam ini komplikasi adalah untuk mengacaukan masalah: memindahkan titik sedikit jadi ini kasus khusus tidak terjadi. Misalnya, kita bisa memindahkan titik (x, y) hanya sejumlah kecil ke kanan; ini tidak akan berubah apakah itu di dalam atau di luar poligon tetapi akan mengubah apakah ray melintasi melalui simpul. Bahkan, kita dapat melakukan gangguan ini hanya dalam pikiran kita, dan biarkan membimbing kita dalam berpikir tentang pemecahan masalah, tanpa benar-benar bergerak poin. Misalkan ray akan menyeberang simpul sebelum terganggu. Setelah gangguan, yang ujung-ujungnya akan itu menyeberang? Hanya orang-orang yang pergi ke kanan titik tersebut. Kita dapat menguji dua sinar dari titik dan melihat mana dari mereka pergi ke sebelah kanan, dan menyesuaikan jumlah yang sesuai. Sekali lagi, kami juga perlu berhati-hati tentang pengujian apakah intinya adalah tepat pada batas poligon; kasus yang paling rumit adalah ketika hal ini terjadi pada segmen garis vertikal.
int penyeberangan = 0
for (int i = 0; i <n; i ++)
{
if ((P (i) .v <x && x <P (i + 1) .v) || (P (i) .v> x && x> P (i + 1) .v))
{
t = (x - P (i + 1) .v) / (P (i) .v - P (i + 1 .x))
cy = t * P (i) .v + (1-t) * P (i + 1) .v
jika (y == cy) kembali (pada batas)
lain jika (y> cy) penyeberangan ++;
}
if ((P (i) .v == x && P (i) .v <= y) {
jika (P (i) .v == y) kembali (dari batas);
jika (P (i + 1) .v == x)
{
if ((P (i) .v <= y && y <= P (i + 1) .v) || (P (i) .v> = y && y> = P (i + 1) .v) )
kembali (pada batas);
} Else if (P (i + 1) .v> x) penyeberangan ++;
jika (P (i-1) .v> x) penyeberangan ++;
}
}
jika (penyeberangan ganjil)
kembali (dalam);
lain kembali (luar);
Ini hampir sepenuhnya diperluas untuk kode compilable, dan itu tidak terlalu lama, tetapi tidak mudah untuk dibaca. Untuk memahami ide di balik algoritma, aku akan tetap dengan pseudo-kode saya mulai dengan di bagian sebelumnya.
Poin di poligon cembung
Sebuah poligon cembung adalah salah satu tanpa lekukan. Hal ini juga dapat didefinisikan secara formal sebagai memiliki properti bahwa setiap dua titik dalam poligon dapat dihubungkan oleh segmen garis yang tidak menyeberangi poligon.
poligon cembung biasanya lebih mudah untuk menangani daripada yang non-cembung. Sebagai contoh, mari kita lihat bagaimana untuk menyederhanakan tes point-in-poligon.
Mari P (i) menjadi titik paling kiri dari poligon, dan P (j) menjadi titik paling kanan. Kedua poin membagi poligon menjadi dua bagian, rantai atas dan rantai yang lebih rendah. Setiap baris atau sinar melintasi poligon paling dua kali, dan setiap garis vertikal atau sinar melintasi masing-masing rantai paling banyak sekali.
Jadi banyak pekerjaan algoritma titik-in-poligon sebelumnya terbuang - kita pergi melalui setiap segmen memeriksa apakah itu memberikan crossing, tapi jawabannya akan ya di paling banyak dua kasus.
Bagaimana kita dapat menemukan dua kasus ini lebih cepat? pencarian biner. Hanya mencari x dalam koordinat pertama poin dalam dua rantai. Jika dalam rantai, Anda telah menemukan persimpangan melalui simpul (dan Anda tidak perlu menjadi seperti hati untuk mengatakan apa jenis persimpangan, baik). Jika x bukan koordinat dari titik dalam rantai, dua nilai terdekat untuk itu memberitahu Anda yang segmen ray dari (x, y) mungkin menyeberang. Jadi kita bisa menguji apakah suatu titik dalam poligon cembung dalam waktu O (log n).
Ternyata ada struktur data yang dapat menguji apakah suatu titik dalam poligon sewenang-wenang (atau yang dari beberapa poligon itu di) di O yang sama (log n) waktu terikat. Tapi mereka lebih rumit, jadi saya tidak punya waktu untuk menjelaskan di sini; Saya akan berbicara tentang mereka di beberapa titik di ICS 164.
lambung cembung
Sejak poligon cembung jauh lebih bagus untuk menangani dari jenis lain dari poligon, bagaimana kita bisa membuat cembung masukan? Terkecil poligon cembung berisi koleksi poin dikenal sebagai convex hull; ini juga dapat didefinisikan sebagai persimpangan (jauh lebih banyak) halfspaces (bagian dari pesawat di salah satu sisi garis) yang berisi semua poin.
Saya akan menjelaskan suatu algoritma untuk menemukan lambung cembung dikenal sebagai scan Graham. Idenya adalah sesuatu yang umum dalam geometri komputasi, dikenal sebagai algoritma tambahan: menambahkan item satu per satu untuk beberapa struktur, mempertahankan seperti yang Anda lakukan solusi parsial untuk item ditambahkan sejauh ini. Urutan item ditambahkan sering penting; scan Graham menambahkan poin untuk disortir dari kiri ke kanan (dengan nilai-nilai koordinat pertama mereka). Jadi O (n log n) waktu yang dibutuhkan untuk tahap penyortiran awal, atau kurang waktu jika Anda ingin menganggap mis bahwa koordinat titik-titik 'adalah bilangan bulat kecil.
Algoritma ini lebih mudah untuk menggambarkan dalam hal rantai atas dan bawah yang ditetapkan sebelumnya. Saya akan menjelaskan bagaimana untuk menghitung rantai atas; rantai yang lebih rendah benar-benar simetris. Karena urutan di mana kita menambah poin, poin pertama selalu akhir kiri rantai atas, dan titik terakhir selalu ujung kanan. Satu-satunya pertanyaan adalah, apa yang terjadi di tengah?
Gambar di bawah menunjukkan apa yang terjadi ketika kita menambahkan satu titik baru untuk rantai atas. Kita tahu itu harus di ujung kanan, jadi mari kita coba tambahkan setelah titik paling kanan sebelumnya. Namun, ini mungkin membuat lekukan pada titik sebelumnya; jika demikian kita menghapus lekukan dari rantai, sehingga memiliki satu tepi kurang. Kami terus menghapus lekukan satu per satu sampai tidak ada satu pun yang tersisa, di mana titik kita memiliki rantai baru.
Ini paling mudah untuk menerapkan jika kita mempertahankan rantai menggunakan struktur data stack. Setiap titik baru dalam rantai sesuai dengan dorongan dalam stack, dan menghapus lekukan sesuai dengan pop. Berikut adalah beberapa pseudocode:
tumpukan S = kosong
untuk setiap titik (x, y) dalam rangka diurutkan oleh x
{
jika (x, y) dan atas dua titik pada S yang menjorok
pop S
dorong (x, y) ke S
}
Satu-satunya pertanyaan adalah bagaimana kita menguji apakah tiga poin (x0, y0), (x1, y1), dan (x2, y2) membentuk lekukan. Karena kita tahu dalam hal ini urutan dari x-koordinat tiga poin, semua yang perlu kita lakukan adalah menguji apakah titik tengah atas atau di bawah segmen garis yang dibentuk oleh dua lainnya. Ini pada dasarnya adalah sama dengan matematika saya pergi melalui untuk mendeteksi penyeberangan untuk uji titik-in-poligon.
algoritma melewati O (n) iterasi dari loop luar. Ada juga loop bersarang dalam, tapi setiap iterasi dari loop batin menghapus poin dari stack, dan setiap titik hanya dapat dihapus setelah, jadi ini terjadi O (n) kali jumlah. Oleh karena itu total waktu untuk algoritma convex hull, setelah tahap penyortiran awal, adalah O (n). Algoritma keseluruhan membutuhkan waktu O (n log n) karena langkah penyortiran.
Sebuah proses serupa shortcutting lekukan juga bekerja untuk menemukan lambung cembung poligon sederhana. Tentu saja Anda bisa menyortir simpul dari poligon dan menerapkan Graham memindai, tapi Anda malah dapat melakukan proses shortcutting pada poligon itu sendiri. Hal ini dimungkinkan untuk jalan pintas untuk menambahkan persimpangan antara dua tepi, tetapi ini akan selalu menjadi diuraikan oleh tahap selanjutnya dari sudut. Dengan cara ini, orang dapat menemukan lambung cembung poligon sederhana dalam waktu linier, tanpa mengambil waktu untuk tahap penyortiran.
Sumber :
https://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf
No comments:
Post a Comment