Persimpangan Lingkaran dengan Algoritma Sapu Garis

Sayangnya saya masih belum begitu kuat dalam memahami Algoritma Sweep Line . Semua makalah dan buku pelajaran tentang topik sudah dibaca, namun pemahaman masih jauh. Untuk membuatnya lebih jelas, saya mencoba menyelesaikan sebanyak mungkin latihan. Tapi, tugas yang sangat menarik dan penting masih menjadi tantangan bagi saya.

Latihan berikut ini saya temukan dalam catatan kuliah tentang Line Segment Intersection oleh Mahakuasa Jeff Erickson.

Latihan 2. Jelaskan dan analisis algoritma sweepline untuk menentukan, diberikan lingkaran di pesawat, apakah ada dua berpotongan, dalam waktu . Setiap lingkaran ditentukan oleh pusat dan jari-jarinya, sehingga input terdiri dari tiga array , dan . Berhati-hatilah untuk menerapkan primitif tingkat rendah dengan benar. $n$ $O(n \log n)$ $X[1.. n], Y [1.. n]$ $R[1.. n]$

Mari kita coba untuk membuat hal yang kompleks menjadi lebih mudah. Apa yang kita ketahui tentang persimpangan lingkaran? Apa yang analog dapat ditemukan dengan persimpangan garis. Dua garis mungkin berpotongan jika berbatasan, properti mana yang harus dimiliki oleh dua lingkaran untuk berpotongan? Misalkan menjadi jarak antara pusat lingkaran, dan pusat lingkaran. Pertimbangkan beberapa kasus: $d$ $r_{0}$ $r_{1}$

Kasus 1: Jika maka tidak ada solusi, lingkarannya terpisah. $d > r_{0} + r_{1}$
Kasus 2: Jika maka tidak ada solusi karena satu lingkaran terkandung di dalam yang lain. $d < |r_{0} - r_{1}|$
Kasus 3: Jika dan maka lingkarannya bertepatan dan ada banyak solusi. $d = 0$ $r_{0} = r_{1}$

Jadi, sepertinya kondisi simpang sudah siap, tentu saja kondisinya mungkin salah. Harap perbaiki jika benar.

Algoritma. Sekarang kita perlu menemukan kesamaan antara dua lingkaran yang berpotongan. Dengan persimpangan analog ke garis, kita harus memiliki kondisi penyisipan dan menghapus kondisi ke antrian acara. Katakanlah titik kejadian adalah koordinat x dari titik pertama dan terakhir yang disentuh garis vertikal. Pada titik pertama kita memasukkan lingkaran ke status dan memeriksa persimpangan (3 kasus untuk pemeriksaan disebutkan di atas) dengan lingkaran terdekat, pada titik terakhir kita menghapus lingkaran dari status .

Sepertinya cukup untuk algoritma garis sapu. Jika ada sesuatu yang salah, atau mungkin ada sesuatu yang harus dilakukan berbeda, jangan ragu untuk membagikan pemikiran Anda dengan kami.

Adendum :

Saya memasukkan lingkaran ketika garis sapuan vertikal menyentuh lingkaran untuk pertama kalinya, dan menghapus lingkaran dari status ketika garis sapuan menyentuhnya untuk yang terakhir kalinya. Pemeriksaan untuk persimpangan harus dilakukan untuk lingkaran terdekat sebelumnya. Jika kami menambahkan lingkaran ke status dan sudah ada lingkaran lain yang kami tambahkan sebelumnya dan itu masih ada, maka lingkaran yang dulunya tidak "ditutup", jadi mungkin ada persimpangan.

algorithms computational-geometry com
sumber

Mahakuasa [rujukan?]

JeffE

@ co, apa yang Anda maksud dengan "lingkaran sebelumnya terdekat"?

Joe

Saya berasumsi bahwa statusmempertahankan lingkaran yang saat ini memotong garis sapuan? Misalkan saat ini Anda memiliki 100 lingkaran status, dan Anda memproses acara penyisipan dan memasukkan lingkaran ke-101. Berapa banyak lingkaran yang Anda bandingkan untuk memeriksa persimpangan? Bagaimana Anda memilih lingkaran mana yang akan dibandingkan?

Joe

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

Jawaban:

Anda pasti berada di jalur yang benar. Pertanyaan besarnya adalah: ketika Anda memasukkan lingkaran, lingkaran mana yang Anda periksa untuk persimpangan? Bagaimana Anda melakukan pemeriksaan ini?

Dalam kasus persimpangan ruas garis, ruas garis pada koordinat x mana pun diberikan secara total. (Anda dapat mencantumkannya dari koordinat Y terendah ke tertinggi). Dengan demikian, Anda dapat mempertahankan segmen garis di pohon pencarian biner, dan ketika Anda menambahkan segmen baru, Anda hanya perlu mencari tahu di mana tempatnya di pohon pencarian biner, dan memeriksa tetangganya untuk acara persimpangan.

Dalam kasus lingkaran, ini tidak segera menghapus lingkaran mana yang akan diperiksa. Jika jawaban Anda adalah "semuanya" maka algoritme Anda perlu beberapa pekerjaan.

Bisakah Anda mencari cara untuk mewakili lingkaran sehingga mereka benar-benar dipesan, seperti segmen garisnya?

Cobalah mewakili lingkaran sebagai dua setengah lingkaran. Setiap acara memasukkan sebenarnya dua peristiwa: masukkan bagian atas, dan masukkan bagian bawah.

Joe
sumber

Sayangnya saya tidak mendapatkan ide setengah lingkaran, mungkin Anda menganggap setengah lingkaran sebagai unit minimal lingkaran yang dapat berpotongan (3 kasus persimpangan: persimpangan adalah di setengah lingkaran atas, atau di bawah, atau pada keduanya). Pada mengemis semua lingkaran diperintahkan oleh x koordinat batas kiri dan kanan mereka. Jadi kita tidak boleh mempertimbangkan x terkoordinasi dalam status , karena semua lingkaran sudah masuk dalam urutan koordinat x. Karena itu, tampaknya lebih logis untuk mempertimbangkan koordinat pusat (setengah lingkaran), atau kombinasi y dan jari-jari. Pendapat Anda?

com

@ co Anda memerlukan titik pusat dan jari-jari untuk menentukan apakah dua lingkaran berpotongan, seperti yang telah Anda lakukan pada pemeriksaan persimpangan Anda sendiri. Hanya koordinat y dan jari-jari saja tidak sepenuhnya menentukan batas lingkaran. Tampaknya ada sesuatu yang mendasar tentang algoritma garis sapu yang tidak Anda mengerti, tetapi sulit bagi saya untuk mengatakan apa itu.

Joe

Saya bisa memikirkan pendekatan ini analog dengan sapuan Bentley Ottmann yang berjalan dalam waktu O ((n + k) logn).

Saya bisa mengurangi masalah persimpangan lingkaran ke persimpangan segmen garis. Saya akan mempertimbangkan diameter vertikal sejajar dengan sumbu-Y untuk masing-masing lingkaran. Algoritma harus menggunakan garis horizontal yang menyapu pesawat dari bawah ke atas.

Sekarang kita memiliki titik ujung atas, titik ujung bawah untuk masing-masing lingkaran. Juga, kita perlu memodifikasi predikat titik-temu untuk mengatakan bahwa dua segmen berpotongan jika dan hanya jika garis sapuan memotong kedua lingkaran pada satu titik.

Karena masalah persimpangan garis dapat diselesaikan dalam waktu O ((n + k) logn), batas yang sama juga mengikuti untuk persimpangan lingkaran.

Saya cukup yakin bahwa ini akan berhasil tetapi jika kalian bisa menunjukkan kasus apa pun yang tidak akan ditangani secara umum, beri tahu saya.

TheGT
sumber