Tentukan apakah suatu titik terletak pada lambung cembung dalam waktu O(log n) [duplikat]

Saya telah meneliti beberapa algoritme untuk menentukan apakah suatu titik terletak pada lambung cembung, namun sepertinya saya tidak dapat menemukan algoritme apa pun yang dapat melakukan trik tersebut dalam waktu O(logn), dan saya juga tidak dapat membuatnya sendiri. Biarkan a [] menjadi larik yang berisi simpul dari lambung cembung, dapatkah saya memproses terlebih dahulu larik ini, untuk memungkinkan memeriksa apakah ada titik baru yang terletak di dalam lambung cembung dalam waktu O(logn).


performance algorithm point computational-geometry convex-hull
person Andrew Brick    schedule 02.03.2015    source sumber
comment
Anda mungkin juga ingin menanyakan pertanyaan ini di situs Matematika. Sepertinya Anda lebih tertarik pada algoritme itu sendiri daripada penerapannya.   -  person Tim Biegeleisen    schedule 02.03.2015

Jawaban (1)


arrow_upward
1
arrow_downward

Sepertinya kamu bisa.

  1. Urutkan simpul di a[] berdasarkan sudut kutub relatif terhadap salah satu simpul (sebut saja A). O(N log N), seperti perhitungan lambung cembung.
  2. Baca titiknya, tentukan sudut kutubnya. HAI(1)
  3. Temukan dua simpul yang bertetangga, salah satunya harus memiliki sudut kutub yang lebih kecil dari titik pada langkah 2, dan yang lainnya harus memiliki sudut yang lebih besar (B dan C). O(log N), pencarian biner
  4. Kemudian geometri sederhana: gambarlah segitiga antara titik-titik dari A, B, C dan periksa apakah titik dari langkah 2 terletak di dalamnya. HAI(1)
person Everv0id    schedule 02.03.2015
comment
apa itu pt. 1, 2 dan 3 dalam hal ini adalah pt. 1 titik yang diuji, dan pt. 2 dan 3 apakah titik-titik tetangganya memenuhi kondisi pada langkah 3? - person Andrew Brick; 02.03.2015
comment
Bisakah Anda juga menjelaskan bagaimana langkah 3 dilakukan dalam waktu O(logn). - person Andrew Brick; 02.03.2015
comment
tidak, maaf untuk singkatan saya :) pt.1 adalah item 1 (sortir), pt.2 adalah item 2 (read point), dll. - person Everv0id; 02.03.2015
comment
oh begitu, tapi masih mungkin suatu titik tidak terletak pada garis yang menghubungkan titik-titik tetangganya dan masih berada di lambung cembung - person Andrew Brick; 02.03.2015
comment
Sepertinya saya salah memahami masalah Anda. Apakah maksud Anda titik tersebut terletak di dalam lambung cembung? - person Everv0id; 02.03.2015
comment
ya, saya sedang memeriksa apakah itu terletak di dalam lambung cembung, bukan hanya di tepi lambung cembung - person Andrew Brick; 02.03.2015
comment
pada langkah 4, apakah Anda memeriksa apakah segitiga tersebut termasuk dalam himpunan cembung, tapi menurut saya ini tidak dapat dilakukan dalam waktu O(1), apakah ada cara untuk melakukannya dalam waktu O(logn) - person Andrew Brick; 02.03.2015
comment
Tidak. Pada langkah keempat kita sudah mempunyai titik A, B, C. Jika titik yang kita periksa terletak di luar segitiga ABC, berarti terletak di luar seluruh lambung cembung. - person Everv0id; 02.03.2015
comment
maaf tentang tumpukan pertanyaan yang banyak, tapi saya hanya punya satu hal lagi untuk ditanyakan. Sudut kutub suatu titik adalah sudut yang dibuat vektor dari titik asal ke titik tersebut dengan sumbu x, tetapi saya belum pernah melihat sudut kutub suatu titik relatif terhadap titik lain (titik A dalam kasus kami). Apakah ini sudut antara vektor dari titik asal ke titik dan vektor dari titik asal ke titik A. - person Andrew Brick; 02.03.2015
comment
Secara formal, titik (x1, y1) lebih kecil dari titik (x2, y2) jika dan hanya jika kemiringan (y1 − y0) / (x1 − x0) lebih kecil dari kemiringan (y2 − y0) / (x2 − x0). dari sana: coursera.cs.princeton.edu/algs4/assignments/collinear.html - person Everv0id; 02.03.2015
comment
Anda dapat dengan mudah melakukannya di Log(h) dengan menggunakan algoritma saya menggunakan hasil kuadran perantara. Lihat: codeproject.com/Articles/ 775753/ dan/atau (lebih baru): codeproject.com/Articles/1210225/ - person Eric Ouellet; 22.11.2017