Bagaimana saya bisa mengukur kelurusan garis yang ditarik?

37

Saya sedang mengerjakan permainan yang mengharuskan pemain untuk menggambar garis dari titik A (x1, y1) ke titik B lainnya (x2, y2) di layar perangkat Android.

Saya ingin menemukan seberapa baik gambar itu cocok untuk garis lurus. Sebagai contoh, hasil dari 90% akan berarti gambar hampir cocok dengan garis. Jika pemain menggambar garis melengkung dari A ke B, itu harus mendapatkan skor rendah.

Poin akhir tidak diketahui sebelumnya. Bagaimana saya bisa melakukan ini?

pengguna3637362
sumber
1
Apakah Anda tahu sebelumnya apa dua poin akhir Anda? Atau ditentukan pada saat pengguna berhenti menyentuh layar?
Vaillancourt
Maaf jika uraian saya tidak jelas untuk Anda. Nah, titik awal A (x, y) adalah sentuhan pertama dan titik akhir B (x, y) adalah ketika kita dilepaskan dari layar sentuh seperti yang Anda katakan.
user3637362
Kami memiliki pertanyaan terkait tentang pencocokan huruf yang ditarik pemain .
Anko
3
Tolong jangan posting gambar untuk kode sumber di masa depan.
Josh
1
@ user3637362 Saya mengerti bahwa Anda mulai j=1sehingga Anda dapat membandingkan touchList[j]dengan touchList[j-1], tetapi ketika touch.phase == TouchPhase.Beganatau touch.phase == TouchPhase.Endedposisi tidak ditambahkan ke touchListdan kemudian tidak termasuk dalam sumLength. Bug ini akan hadir dalam semua kasus tetapi akan lebih jelas ketika garis memiliki beberapa segmen.
Kelly Thomas

Jawaban:

52

Garis lurus sempurna juga akan menjadi garis terpendek yang mungkin dengan panjang total sqrt((x1-x2)² + (y1-y2)²). Jalur yang lebih scribbly akan menjadi koneksi yang kurang ideal dan karenanya akan lebih lama.

Saat Anda mengambil semua titik individual dari jalur yang digambar pengguna dan menjumlahkan jarak di antara mereka, Anda dapat membandingkan total panjang dengan panjang ideal. Semakin kecil total panjang dibagi dengan panjang ideal, semakin baik garis.

Ini visualisasi. Ketika titik-titik hitam adalah titik-akhir dari gerakan dan titik-titik biru adalah titik-titik yang Anda ukur selama gerakan, Anda akan menghitung dan menjumlahkan panjang garis-garis hijau dan membaginya dengan panjang garis merah:

masukkan deskripsi gambar di sini

Skor atau indeks sinuositas 1 akan sempurna, apa pun yang lebih tinggi akan kurang sempurna, apa pun di bawah 1 akan menjadi bug. Ketika Anda memilih untuk mendapatkan skor dalam persen, bagilah 100% dengan jumlah itu.

Philipp
sumber
34
Ada masalah kecil dengan pendekatan ini di mana polyline dengan panjang yang sama tidak sama 'lurus'. Sebuah garis yang bergetar dengan deviasi rendah (tetapi berkali-kali) tentang garis lurus adalah 'lebih lurus' daripada garis dengan panjang yang sama yang menyimpang ke satu titik dan kemudian kembali.
Dancrumb
Saya tidak bisa memberi komentar +1 @ Dancrumbs dengan cukup - itu adalah batasan kunci yang cukup dengan metode ini seolah-olah pengguna menggambar garis lurus mereka akan sedikit goyah sehingga ini terasa seperti kasus penggunaan umum.
T. Kiley
@ Dancrumb hanya faktor dalam jarak rata-rata dari garis, atau faktor dalam "jarak maks" setiap titik dari garis. Kemudian Anda dapat menimbang algoritme tersebut ke garis yang lebih goyah dengan amplitudo deviasi yang lebih kecil, dan menjauh dari garis yang menyimpang jauh dari jalur yang diharapkan.
Superdoggy
2
@Dancrumb Kedengarannya bagi saya seperti ini mungkin berakhir dengan manfaat untuk kasus penggunaan OP. Garis yang digambar tangan, tentu saja, memiliki penyimpangan kecil. Pendekatan ini mungkin benar-benar bekerja untuk mengurangi efek dari perbedaan yang diharapkan ini.
2
@ user3637362 Anda memiliki bug di kode Anda. Penjelasan yang mungkin adalah bahwa Anda lupa memperhitungkan jarak antara titik awal dan titik pertama atau titik akhir dan titik terakhir, tetapi tanpa melihat kode Anda, tidak mungkin untuk menentukan kesalahan Anda.
Philipp
31

Ini mungkin bukan cara terbaik untuk mengimplementasikan ini, tetapi saya menyarankan RMSD (root mean square deviation) bisa lebih baik, daripada hanya metode jarak, dalam kasus yang disebutkan oleh Dancrumb (lihat dua baris pertama di bawah).

RMSD = sqrt(mean(deviation^2))

catatan:

  • Jumlah dari penyimpangan absolut (seperti integral) mungkin lebih baik, karena tidak rata-rata kesalahan positif dengan yang negatif. ( =sum(abs(deviation)))
  • Anda mungkin harus mencari jarak terpendek ke garis linier jika ada cara yang menciptakan jarak lebih pendek daripada menjatuhkan tegak lurus.

gambar

(Maafkan kualitas gambar saya yang rendah)

Seperti yang Anda lihat, Anda harus melakukannya

  1. temukan vektor ortogonal ke baris Anda ( titik-produk sama dengan 0 ).
    Jika garis Anda mengarah ke yang (1, 3) Anda inginkan (3, -1)(masing-masing melalui titik asal)
  2. Ukur jarak h dari garis ideal ke garis pengguna, sejajar dengan vektor itu.
  3. Hitung RMSD atau jumlah perbedaan absolut.
gr4nt3d
sumber
Jawaban Joel Bosveld menunjukkan kasus yang menarik: garis lurus yang hampir sempurna dengan sudut di awal dan akhir. Jika garis harus ditarik secara bebas oleh pengguna, ini memang masalah. Meskipun demikian saya pikir metode ini dapat mencakup skenario itu. Seseorang dapat benar-benar melakukan kecocokan dengan RMSD atau Integral absolut sebagai nilai teratas yang diminimalkan. Nilai awal dapat menjadi titik awal dan akhir. Karena panjangnya tidak masalah, juga tidak relevan jika optimasi menggerakkan titik-titik sehingga garis ideal mencapai lebih jauh atau lebih pendek (ketinggian harus dihitung ke niveau itu).
gr4nt3d
1
Kasus lain yang sepertinya tidak dibahas: Katakanlah setiap titik yang diukur berada pada sumbu x, tetapi garis membalikkan arah beberapa kali. Ini akan mengembalikan kesalahan 0.
dave mankoff
23

Jawaban yang ada tidak memperhitungkan bahwa titik akhir arbitrer (daripada diberikan). Jadi, ketika mengukur kelurusan kurva, tidak masuk akal untuk menggunakan titik akhir (misalnya, untuk menghitung panjang, sudut, posisi yang diharapkan). Contoh sederhana akan menjadi garis lurus dengan kedua ujungnya kincked. Jika kita mengukur dengan menggunakan jarak dari kurva dan garis lurus antara titik-titik akhir ini akan cukup besar, karena garis lurus yang kita gambar diimbangi dari garis lurus antara titik-titik akhir.

Bagaimana kita tahu seberapa lurus kurva itu? Dengan asumsi kurva cukup halus, kami ingin tahu berapa banyak, rata-rata, garis singgung kurva berubah. Untuk garis, ini akan menjadi nol (karena garis singgung adalah konstan).

Jika kita membiarkan posisi pada waktu t menjadi (x (t), y (t)), maka garis singgung adalah (Dx (t), Dy (t)), di mana Dx (t) adalah turunan dari x pada waktu t (situs ini tampaknya tidak memiliki dukungan TeX). Jika kurva tidak diparameterisasi oleh panjang busur, kita dinormalisasi dengan membaginya dengan || (Dx (t), Dy (t)) ||. Jadi kita memiliki vektor satuan (atau sudut) dari garis singgung ke kurva pada waktu t. Jadi, sudutnya adalah a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||

Kami kemudian tertarik pada || Da (t) || ^ 2 yang terintegrasi di sepanjang kurva.

Mengingat bahwa kemungkinan besar kita memiliki titik data diskrit daripada kurva, kita harus menggunakan perbedaan hingga untuk memperkirakan turunannya. Jadi, Da (t) menjadi (a(t+h)-a(t))/h. Dan, a (t) menjadi ((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||. Kemudian kita mendapatkan S dengan menjumlahkan h||Da(t)||^2semua titik data dan mungkin menormalkan dengan panjang kurva. Kemungkinan besar, kami menggunakan h=1, tetapi itu benar-benar hanya faktor skala yang sewenang-wenang.

Untuk mengulangi, S akan menjadi nol untuk suatu garis dan semakin besar semakin menyimpang dari suatu garis. Untuk mengonversi ke format yang diperlukan, gunakan 1/(1+S). Mengingat bahwa skala agak arbitrer, dimungkinkan untuk mengalikan S dengan beberapa angka positif (atau mengubahnya dengan cara lain, misalnya menggunakan bS ^ c bukan S) untuk menyesuaikan seberapa lurus kurva tertentu.

Joel Bosveld
sumber
2
Ini adalah definisi kelurusan yang paling masuk akal.
Marcks Thomas
1
Sejauh ini, inilah jawaban yang paling masuk akal dan saya yakin yang lain akan menjadi sangat frustasi. Sayangnya, bentuk dari solusi yang disajikan sedikit lebih kabur daripada yang lain, tetapi saya akan merekomendasikan OP tetap ada.
Dan Sheppard
Secara umum saya juga berpikir jawaban ini memang yang terbaik. Meskipun ada masalah yang mengganggu saya: Apa yang terjadi jika saluran tidak "cukup mulus"? Misalnya, jika Anda memiliki dua segmen garis lurus sempurna dengan sudut, katakanlah, 90 °. Apakah saya salah atau akankah ini menghasilkan hasil yang cukup rendah dibandingkan dengan garis linier yang sangat halus? (Saya pikir kasus pengguna Dancrumb dengan garis goyah adalah masalah yang sama) ... Secara lokal ini adalah cara terbaik.
gr4nt3d
3

Ini adalah sistem berbasis grid, kan? Temukan poin Anda sendiri untuk garis dan hitung kemiringan garis. Sekarang, dengan menggunakan perhitungan itu, tentukan poin-poin valid yang akan dilewati garis, dengan memberikan margin kesalahan dari nilai yang tepat.

Melalui pengujian coba-coba dalam jumlah singkat, tentukan jumlah pencocokan baik dan buruk apa yang akan ada dan atur permainan Anda menggunakan skala untuk hasil yang sama dari pengujian Anda.

yaitu, sebuah garis pendek dengan kemiringan hampir horizontal mungkin memiliki 7 poin yang dapat Anda tarik. Jika Anda dapat secara konsisten mencocokkan 6 atau lebih dari 7 yang ditentukan sebagai bagian dari garis lurus, maka itu akan menjadi skor tertinggi. Grading untuk panjang dan akurasi harus menjadi bagian dari penilaian.

Pemanah
sumber
3

Ukuran yang sangat mudah dan intuitif adalah area antara garis lurus pas terbaik dan kurva aktual. Menentukan ini cukup mudah:

  1. Gunakan kuadrat-terkecil yang cocok untuk semua poin (ini mencegah masalah end-kink yang disebutkan oleh Joel Bosveld).
  2. Untuk semua titik pada kurva, tentukan jarak ke garis. Ini juga masalah standar. (Aljabar linier, transformasi basis.)
  3. Jumlah semua jarak.
MSalters
sumber
Bisakah Anda keberatan jika saya meminta kode teks (JS, C #) atau kode semu, karena sebagian besar jawaban di atas dijelaskan dalam teori, saya tidak tahu bagaimana memulainya?
user3637362
1
@ user3637362: StackOverflow memiliki jawaban praktis: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/…
MSalters
2

Idenya adalah untuk menjaga semua titik yang disentuh pengguna, lalu mengevaluasi dan menjumlahkan jarak antara masing-masing titik ke garis yang terbentuk saat pengguna melepaskan layar.

Ini adalah sesuatu untuk Anda mulai dengan pseudo-code:

bool mIsRecording = false;
point[] mTouchedPoints = new point[];

function onTouch
  mIsRecording = true

functon update
  if mIsRecording
    mTouchedPoints.append(currentlyTouchedLocation)

function onRelease
  mIsRecording = false

  cumulativeDistance = 0

  line = makeLine( mTouchedPoints.first, mTouchedPoints.last )

  for each point in mTouchedPoints:
    cumulativeDistance = distanceOfPointToLine(point, line)

  mTouchedPoints = new point[]

Apa yang cumulativeDistancebisa memberi Anda ide tentang pemasangan. Jarak 0 berarti pengguna berada di garis lurus sepanjang waktu. Sekarang Anda harus melakukan beberapa tes untuk melihat bagaimana berperilaku dalam konteks Anda. Dan Anda mungkin ingin memperbesar nilai yang dikembalikan distanceOfPointToLinedengan mengkuadratkannya untuk menghukum lebih jauh jarak yang jauh dari garis.

Saya tidak akrab dengan persatuan, tetapi kode di updatesini mungkin memiliki onDragfungsi.

Dan Anda mungkin ingin menambahkan suatu tempat di sana beberapa kode untuk mencegah mendaftarkan suatu titik jika itu sama dengan yang terakhir terdaftar. Anda tidak ingin mendaftarkan barang ketika pengguna tidak bergerak.

Vaillancourt
sumber
5
Ketika Anda menambahkan jarak antara garis ideal dan titik untuk setiap titik yang diukur, Anda harus memperhitungkan jumlah tindakan yang Anda ambil, jika tidak, ketika pengguna menggambar lebih lambat atau menggunakan perangkat dengan kecepatan pindai yang lebih cepat mereka akan mendaftar lebih banyak poin yang berarti mereka akan mendapatkan skor lebih buruk.
Philipp
@ Pilip Ya Anda tahu! Saya harus mengakui bahwa cara Anda melakukannya tampaknya lebih baik daripada saya: P
Vaillancourt
Saya pikir pendekatan ini ditingkatkan dengan mengambil jarak rata - rata , daripada Kumulatif Jarak.
Dancrumb
@ Dancrumb Sungguh, itu tergantung pada kebutuhan, tapi ya, itu akan menjadi cara untuk melakukannya.
Vaillancourt
2

Salah satu metode yang dapat Anda gunakan adalah dengan membagi garis menjadi segmen dan melakukan produk titik vektor antara masing-masing vektor yang mewakili segmen dan vektor yang mewakili garis lurus antara titik pertama dan terakhir. Ini memiliki manfaat membiarkan Anda menemukan segmen yang sangat "runcing" dengan mudah.

Edit:

Juga, saya akan mempertimbangkan untuk menggunakan panjang segmen selain produk titik. Vektor yang sangat pendek tetapi ortogonal harus menghitung kurang dari yang panjang yang memiliki sedikit penyimpangan.

Kik
sumber
1

Cara termudah dan tercepat mungkin hanya untuk mengetahui seberapa tebal garis harus mencakup semua poin dari garis yang dibuat pengguna.

Semakin tebal garis harus, semakin buruk pengguna dalam menggambar garis mereka.

Adam Davis
sumber
0

Entah bagaimana mengacu pada Jawaban MSalters, berikut adalah beberapa informasi yang lebih spesifik.

Gunakan metode kuadrat terkecil agar sesuai dengan garis untuk poin Anda. Anda pada dasarnya mencari fungsi y = f (x) yang paling cocok. Setelah memilikinya, Anda dapat menggunakan nilai y aktual untuk menjumlahkan kuadrat perbedaan:

s = jumlah over ((yf (x)) ^ 2)

Semakin kecil jumlahnya, semakin lurus garisnya.

Cara mendapatkan perkiraan terbaik, dijelaskan di sini: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Cukup baca dari "Pas garis lurus". Perhatikan bahwa t digunakan sebagai ganti x dan b bukan y. C dan D ditentukan sebagai perkiraan, maka Anda memiliki f (x) = C + Dx

Catatan Tambahan: Jelas, Anda juga harus mempertimbangkan panjang garis. Setiap baris yang terdiri dari 2 Poin akan sempurna. Saya tidak tahu konteks pastinya, tapi saya rasa saya akan menggunakan jumlah kuadrat dibagi dengan jumlah poin sebagai peringkat. Saya juga akan menambahkan persyaratan panjang minimal, jumlah minimal poin. (Mungkin sekitar 75% dari panjang maksimal)

philipp
sumber