Bagaimana cara mendeteksi klik pada tepi multigraf?

Saya telah menulis aplikasi GUI berbasis api win32 yang menggunakan fitur GDI+ seperti DrawCurve() dan DrawLine().

Aplikasi ini menggambar garis dan kurva yang mewakili multigraf.

Struktur data untuk edge hanyalah sebuah struct yang terdiri dari lima int. (x1, y1, x2, y2, dan id)

Jika hanya ada satu sisi di antara dua simpul, maka segmen garis lurus digambar menggunakan DrawLine(). Jika ada lebih dari satu sisi, kurva digambar menggunakan DrawCurve() -- Di sini, saya menyebarkan tepi garis lurus di sekitar titik tengah dua simpul, sehingga menjadikannya kurva. Suatu titik yang terpisah beberapa satuan piksel dihitung menggunakan persamaan garis normal. Jika lebih banyak sisi yang ditambahkan, maka dipilih satu piksel yang berjarak dua satuan piksel dari titik tengahnya, lalu berikutnya 3 satuan piksel, dan seterusnya.

Sekarang saya punya dua pertanyaan tentang mendeteksi klik di tepinya.

  1. Dalam menemukan tepi garis lurus, untuk meminimalkan waktu pencarian, apa yang harus saya lakukan?
    Cukup mudah untuk memeriksa apakah piksel yang diklik berada pada segmen garis, namun membandingkan semua tepi akan menjadi tidak efisien jika jumlah tepinya banyak. Tampaknya mungkin untuk melakukannya di O(log n), di mana n adalah jumlah tepi.
    EDIT: pada titik ini tepi (kelas Edge) disimpan di std::map yang memetakan id tepi (int)' s ke objek Edge dan saya sedang mempertimbangkan untuk mendeklarasikan container lain yang memetakan piksel ke id Edge.
    Saya sedang mempertimbangkan untuk menggunakan pohon pencarian biner tetapi apa kuncinya? Atau haruskah saya menggunakan array piksel 2D saja?

  2. Bisakah saya mendapatkan array poin yang digunakan oleh DrawCurve()? Jika ini tidak mungkin, maka saya harus menghitung ulang spline utama, mendapatkan rangkaian titik, dan memeriksa apakah titik yang diklik oleh pengguna cocok dengan titik mana pun dalam larik tersebut.


graph winapi edge-detection gdi+
person Jeffrey Goines    schedule 06.11.2012    source sumber
comment
Apakah tujuannya hanya untuk mendeteksi jika suatu tepi diklik, atau apakah Anda perlu mengambil nilai berdasarkan di mana tepi tersebut diklik?   -  person    schedule 06.11.2012
comment
Hanya mendeteksi tepi mana yang diklik sudah cukup. Kemudian id edge akan diambil dan std::map‹id, ​​Edge*› akan dicari.   -  person Jeffrey Goines    schedule 06.11.2012

Jawaban (1)


arrow_upward
0
arrow_downward

Jika Anda memiliki garis berbentuk rumit, Anda dapat melakukan hal berikut:

  • Buat bitmap internal seukuran grafik Anda dan isi dengan warna hitam.
  • Saat Anda merender grafik, Anda juga merender ke bitmap ini tepi yang ingin Anda klik, namun merendernya dengan warna berbeda. Simpan nilai warna ini dalam tabel bersama dengan ID yang sesuai. Yang penting warnanya berbeda-beda (unik).
  • Saat grafik diklik, transfer koordinat X dan Y ke bitmap internal Anda dan baca pikselnya. Jika bukan hitam, cari nilai warna di tabel Anda dan dapatkan ID terkait.

Dengan cara ini tidak perlu mengkhawatirkan bentuknya sama sekali, tidak perlu menggunakan algoritma kurva sendiri dan lain sebagainya. Biayanya adalah memori ekstra, ini akan menjadi pertimbangan, tetapi kecuali grafiknya sangat besar (dalam hal ini Anda dapat menyangga gambarnya) dalam banyak kasus hal ini tidak menjadi masalah. Anda dapat merender bitmap internal dalam hitungan detik agar grafik utama muncul lebih cepat (seperti biasa).

Semoga ini membantu!

(tip: Anda dapat merender garis "internal" dengan Pena yang lebih lebar sehingga menjadi lebih sensitif).

person Community    schedule 06.11.2012
comment
Pada resolusi 1920 x 1080 dengan 32 bpp (jadi jumlah maksimum tepi yang dapat digambar sekaligus adalah 2^32), diperlukan ruang sekitar 8 MB untuk mendeteksi klik tepi untuk setiap tampilan grafik (di sini, saya berasumsi kanvas ukurannya tetap karena seringnya realokasi buffer bitmap akan sangat mengurangi kinerja). Saya pikir ini adalah cara termudah dan tercepat (O(1)) untuk diterapkan tetapi pada awalnya sepertinya membuang terlalu banyak ruang (O(xy)~=O(n^2)). Namun, saya dapat menurunkan bpp dan mengurangi ukuran buffer bitmap karena praktis kurva yang jumlahnya lebih dari beberapa ribu bahkan tidak terlihat saat digambar bersama. - person Jeffrey Goines; 06.11.2012
comment
Tentu, jika tidak terlihat = tidak dapat diklik, sehingga Anda dapat menghilangkan kejadian yang tumpang tindih. Dan seperti yang Anda katakan, dapat juga mengkuantifikasi titik klik dengan membagi separuh bitmap serta koordinat x/y, atau bahkan mengurangi bitmap menjadi 1/4 dengan setiap titik yang dapat diklik pada wilayah piksel 4x4, tetapi jika Anda memiliki banyak sisi yang hadir pada saat yang sama yang mungkin tidak begitu nyaman. Saya hanya akan menggunakan 24 bpp (2^24 atau 16,8 juta warna berbeda - atau bahkan bitmap 16 bit) karena dalam ruang 1920x1080 Anda tidak akan pernah bisa menggunakan semua warna itu karena hanya ada sekitar 2 juta. piksel tersedia di layar. - person ; 06.11.2012