Bagaimana cara memeriksa apakah 4 poin membentuk bujur sangkar?

Asumsikan saya memiliki 4 poin (mereka adalah 2 dimensi), yang berbeda satu sama lain, dan saya ingin tahu apakah mereka membentuk bujur sangkar. Bagaimana cara melakukannya? (biarkan prosesnya sesederhana mungkin.)

Dengan asumsi bahwa kuadrat Anda mungkin diputar terhadap sistem koordinat apa pun yang Anda miliki, Anda tidak bisa mengandalkan adanya pengulangan nilai X dan Y dalam empat poin Anda.

Yang bisa Anda lakukan adalah menghitung jarak antara masing-masing dari empat titik. Jika Anda menemukan yang berikut ini benar, Anda memiliki kotak:

1. Ada dua titik, katakanlah A dan C yang merupakan jarak x dari satu sama lain, dan dua titik lainnya, misalnya B dan D yang juga merupakan jarak x dari satu sama lain.

2. Setiap titik {A, B, C, D} adalah jarak yang sama dari dua titik yang tidak x jauhnya. yaitu: Jika A adalah x jauh dari C, maka itu akan menjadi z menjauh dari B dan D.

Secara kebetulan, jarak z harus SQRT (( x ^ 2) / 2), tetapi Anda tidak perlu mengkonfirmasi ini. Jika kondisi 1 dan 2 benar maka Anda memiliki kotak. CATATAN: Beberapa orang khawatir tentang inefisiensi akar kuadrat. Saya tidak mengatakan bahwa Anda harus melakukan perhitungan ini, saya hanya mengatakan bahwa jika Anda melakukannya, Anda akan mendapatkan hasil yang dapat diprediksi!

Pekerjaan minimum yang harus Anda lakukan adalah memilih satu titik, katakan A dan menghitung jarak ke masing-masing dari tiga titik lainnya. Jika Anda dapat menemukan bahwa A adalah x dari satu titik dan z dari dua titik lainnya, maka Anda hanya perlu memeriksa dua titik itu satu sama lain. Jika mereka juga x dari satu sama lain maka Anda memiliki kotak. yaitu:

• AB = z
• AC = x
• AD = z

Karena AB = AD, centang BD:

• BD = x

Hanya untuk memastikan, Anda perlu memeriksa sisi lain: BC dan CD.

• BC = z
• CD = z

Karena AC = BD dan karena AB = AD = BC = CD, maka ini adalah bujur sangkar.

Sepanjang jalan, jika Anda menemukan lebih dari dua jarak tepi yang berbeda maka angka tersebut tidak bisa menjadi persegi, sehingga Anda dapat berhenti mencari.

Implementasi Contoh Kerja

Saya telah membuat contoh kerja di jsfiddle (lihat di sini ). Dalam penjelasan saya tentang algoritma, saya menggunakan titik arbitrer A, B, C, dan D. Titik-titik arbitrer itu berada dalam urutan tertentu demi berjalan melalui contoh. The algoritma bekerja bahkan jika poin berada di urutan yang berbeda, namun, misalnya tidak selalu bekerja jika titik-titik tersebut dalam urutan yang berbeda.

Terima kasih kepada: meshuai, Blrfl, MSalters, dan Bart van Ingen Schenau atas komentar yang bermanfaat untuk meningkatkan jawaban ini.

Pilih tiga dari empat poin.

Cari tahu apakah itu segitiga sama kaki kanan dengan memeriksa apakah salah satu dari tiga vektor antara titik sama dengan yang lain diputar oleh 90 derajat.

Jika demikian, hitung titik keempat dengan penambahan vektor dan bandingkan dengan titik keempat yang diberikan.

Perhatikan bahwa ini tidak membutuhkan akar kuadrat yang mahal, bahkan tidak multiplikasi.

Saya pikir solusi termudah adalah sebagai berikut:

• Pertama, hitung pusat dari 4 poin: center = (A + B + C + D)/4

• Kemudian hitung vektornya A - center. Biarkan ini terjadiv := (x,y)

• Membiarkan v2menjadi vektor yang vdiputar 90 derajat:v2 := (-y, x)

• Sekarang poin lainnya seharusnya center - v, center + v2dan center - v2.

Keuntungan dari solusi ini adalah Anda tidak harus menggunakan akar kuadrat sama sekali.

Maaf, beberapa jawaban tidak berlaku.

Untuk kasus Anda mengukur 3 tepi (katakanlah AB, AC dan AD) untuk menemukan bahwa dua memiliki ukuran yang sama (katakanlah AC dan AD) dan satu lebih besar (katakanlah AB). Kemudian Anda akan mengukur CD untuk melihat apakah ukuran AB-nya sama, dan ternyata itu adalah ukurannya. Alih-alih persegi, Anda bisa memiliki gambar di bawah ini, dan itu membuatnya menjadi solusi yang salah.

Kemudian Anda mencoba beberapa solusi lain: mengukur semua jarak setidaknya sekali: AB, AC, AD, BC, BD, CD. Kemudian Anda menemukan bahwa 4 dari itu sama, dan 2 lainnya juga sama di antara mereka. Tapi Anda bisa memiliki gambar seperti di bawah ini:

Jadi, jawaban-jawaban itu tidak benar, meskipun mereka menerima banyak pujian.

Satu solusi yang mungkin: jika kedua ukuran yang sama tidak menghubungkan titik yang sama. Jadi: jika AB dan CD sama panjang, semua kombinasi lainnya (AC, AD, BC, BD) juga sama, Anda memiliki kotak. Jika Anda memiliki titik yang sama membuat panjang terbesar (AB dan AC adalah yang terbesar, dan yang lainnya sama), Anda memiliki salah satu gambar di atas.

Biarkan keempat titik memiliki koordinat vektor a, b, c, d.

Kemudian mari kita sebut perbedaan mereka w = (iklan), x = (ba), y = (cb), z = (dc).

Maka w adalah ortogonal ke a jika Anda dapat membuat w dari dengan rotasi 90 derajat. Secara matematis 90-derajat-rotasi-matriks dalam 2-ruang adalah ((0, -1), (1, 0)). Jadi, kondisi apakah w diputar 90 derajat menghasilkan

(w_1 == -x_2 dan w_2 == x_1)

Jika ini berlaku, maka Anda perlu memeriksa bahwa w == -y dan x == -z, atau

((w_1 == -y_1 dan w_2 == -y_2) dan (x_1 == -z_1 dan x_2 == -z_2))

Jika ketiga relasi tersebut berlaku, a, b, c, d membuat sebuah persegi yang berorientasi.

Mirip dengan jawaban oleh starblue

Pilih tiga dari empat poin.

Cari titik sudut siku-siku di antara mereka : Dengan memeriksa apakah produk titik dari dua dari tiga vektor adalah nol. Jika tidak ditemukan, bukan kotak.

Periksa apakah simpul-simpul yang berdekatan dengan sudut ini juga memiliki sudut yang benar. Jika tidak, bukan kotak.

Periksa apakah diagonal tegak lurus : Jika produk titik vektor antara simpul pertama dan keempat dan dua simpul lainnya (diagonal) adalah nol, maka kuadratnya.

Saya pikir Anda bisa melakukan ini dengan penambahan dan pengurangan sederhana dan menemukan min / maks. Ketentuan (cocok dengan diagram orang lain):

• Poin dengan nilai y tertinggi => A
• tertinggi x => B
• terendah y => C
• terendah x => D

Jika 4 poin hanya berbagi nilai 2 x dan nilai 2 y Anda memiliki kuadrat tingkat.

Jika tidak, Anda memiliki kotak jika poin Anda memenuhi yang berikut:

• Ax + Cx = Bx + Dx
• Ay + Cy = Dengan + Dy
• Ay - Cy = Bx - Dx

Penjelasan: Segmen garis AC dan BD harus bertemu di titik tengahnya. Jadi (Ax + Cx) / 2 adalah titik tengah AC dan (Bx + Dx) / 2 adalah titik tengah BD. Lipat gandakan setiap sisi persamaan ini dengan 2 untuk mendapatkan persamaan pertama saya. Persamaan kedua adalah hal yang sama untuk nilai-Y. Berlian-bentuk (rhomboids) akan memenuhi sifat-sifat ini, jadi Anda perlu memeriksa bahwa Anda memiliki sisi yang sama - bahwa lebarnya sama dengan tinggi. Itu persamaan ketiga.

Ada beberapa jawaban bagus di sini, tetapi pertanyaannya menanyakan pendekatan paling sederhana. Saya memberikan beberapa pemikiran cepat dan ini adalah bagaimana saya akan melakukannya.

Anda dapat mengetahui apakah empat poin mewakili kotak (meskipun diputar), tetapi temukan rata-rata dari empat poin tersebut.

R = (A+B+C+D)/4

Setelah Anda memiliki rata-rata, jarak antara setiap titik dan rata-rata harus sama untuk keempat titik.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) then
   print "Is Square"
else
   print "Is Not Square"

EDIT:

Kesalahanku. Itu hanya akan memberi tahu Anda jika titik formulir berada di lingkaran. Jika Anda juga memeriksa jarak antara titik, maka itu harus kuadrat.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) AND
  (dist(A,B) == dist(B,C) == dist(C,D) == dist(A,D) then
   print "Is Square"
else
   print "Is Not Square"

Ini mengasumsikan bahwa titik A, B, C, D tidak melewati (seperti memiliki urutan belitan yang valid).

ini bukan jawaban sesuai dengan standar yang ditetapkan, tapi saya harap ini membantu:

[Disalin dari tautan di bawah sehingga Anda tidak perlu membuka tautan] Python 76 karakter

def S(A):c=sum(A)/4.0;return set(A)==set((A[0]-c)*1j**i+c for i in range(4))

Fungsi S mengambil daftar bilangan kompleks sebagai inputnya (A). Jika kita tahu pusat dan salah satu sudut kotak, kita dapat merekonstruksi kotak dengan memutar sudut 90.180 dan 270 derajat di sekitar titik pusat (c). Pada rotasi bidang yang rumit sebesar 90 derajat tentang titik asal dilakukan dengan mengalikan titik dengan i. Jika bentuk asli kita dan alun-alun yang direkonstruksi memiliki titik yang sama maka itu pasti persegi.

Ini diambil dari: Tentukan apakah 4 poin membentuk kuadrat

Jika Anda suka jawabannya, saya katakan, luangkan waktu sejenak untuk mengucapkan terima kasih kepada orang tersebut, atau pilih suara jawabannya di halaman itu.

Ide dasar (ini menjawab pertanyaan apakah saya berkontribusi sesuatu yang baru, yang ditanyakan oleh bot ketika saya mengklik untuk memberikan jawaban):

• belah ketupat dengan diagonal yang sama adalah bujur sangkar.
• "sesederhana mungkin" meliputi:
  • tidak ada pembagian,
  • tidak ada akar kuadrat,
  • tidak bercabang,
  • tidak mencari,
  • tidak ada pengecekan sudut atau -chasing,
  • tidak ada vektor,
  • tidak ada transformasi,
  • tidak ada bilangan kompleks,
  • tidak ada fungsi multiline, dan
  • tidak mengimpor paket khusus (hanya menggunakan barang bawaan).
  • (Dan tidak ada kepemilikan Imperial!)

Solusi saya dalam R disajikan di bawah ini. Saya mengasumsikan bahwa ada tepat empat poin dan bahwa, per pernyataan masalah, telah ditentukan bahwa poin tersebut unik.

sumsq <- function(x) sum(x^2)

quadrances.xy <- function(xy) vapply(
    as.data.frame(t(diff(xy)), optional=T), sumsq, 1)

Lihat karya-karya Norman Wildberger, terutama video YouTube-nya ( ikan asli, angka nyata, pekerjaan nyata, dan seq.) Dan bukunya Divine Proportions untuk diskusi tentang "quadrance."

xymengacu pada jenis matriks diterima oleh R plot, pointsdan linesfungsi.

Penerapan as.data.frameadalah trik untuk membuat R melakukan hal-hal yang bijaksana.

The optional=Tklausul menghilangkan nama, yang tidak digunakan, anyway.

quadrances.xy..i2. <- function(xy, i2) vapply(
    as.data.frame(i2, optional=T),
    function(k) quadrances.xy(m[k,]),
    1)

Ini adalah fungsi untuk menghitung kuadran antara titik yang ditentukan, di mana pasangan titik ditentukan oleh i2argumen. The i2simbol mengacu pada matriks indeks yang memiliki satu kolom per indeks, dan 2 elemen per kolom (jenis yang sama dari matriks dikembalikan oleh combnfungsi).

quadrance.every.xy <- function(xy, .which=combn(nrow(xy), 2))
        quadrances.xy..i2.(xy, .which)

Ini .whichdisajikan sebagai argumen semata-mata untuk memaparkannya formalsdan berusaha mengkomunikasikan apa yang sedang terjadi.

is.square.xy <- function(xy) {
    qq <- sort(quadrance.every.xy(xy))
    all(qq[2:4] == qq[1]) && # ALL SIDES (SHORT QUADRANCES) EQUAL
    qq[5] == qq[6] # ALL DIAGONALS (LONG QUADRANCES) EQUAL
}

Saya mengatakan "sederhana" tidak termasuk fungsi multiline. Anda harus memaafkan fungsi dua baris ini.

xy <- t(matrix(c(3,0,  7,3,  4,7,  0,4), ncol=4))
xy
#      [,1] [,2]
# [1,]    3    0
# [2,]    7    3
# [3,]    4    7
# [4,]    0    4
is.square.xy(xy)
# [1] TRUE

Perhatikan bahwa empat fungsi pertama berguna dalam hak mereka sendiri, terlepas dari pertanyaan tentang empat poin.

Asumsikan empat titik A = (kapak, ay), B = (bx, oleh), C = (cx, cy), D = (dx, dy), dan mereka membentuk titik-titik persegi dalam urutan anti-searah jarum jam. Kami memindahkan titik sehingga A berada pada (0, 0) dengan mengurangi kapak dari bx, cx, dan dx, dan mengurangi ay dari oleh, cy, dan dy, mengatur kapak = ay = 0.

Jika titik-titiknya persis sudut-sudut bujur sangkar dalam urutan anti-searah jarum jam, maka diberi A dan B, kita dapat menghitung di mana C dan D adalah: Kita harus memiliki (cx, cy) = (bx - oleh, bx + dengan) dan (dx, dy) = (-dengan, bx). Jadi kita menghitung jarak kuadrat dari tempat C dan D, ke tempat seharusnya: errC = (cx - bx + by) ^ 2 + (cy - bx - oleh) ^ 2, dan errD = (dx + oleh) ^ 2 + (dy - bx) ^ 2. Kami menambahkan ini, dan membaginya dengan (bx ^ 2 + dengan ^ 2), memberikan err = (errC + errD) / (bx ^ 2 + oleh ^ 2).

Hasil err akan menjadi 0 jika kuadrat sempurna, atau angka kecil jika hampir kuadrat, dan angka itu akan tetap tidak berubah kecuali untuk kesalahan pembulatan jika kita menerjemahkan, skala, atau memutar titik-titik kuadrat. Jadi kita dapat menggunakan err untuk memutuskan seberapa baik persegi yang kita miliki.

Tapi kita tidak tahu urutan poinnya. B dan D harus berada pada jarak yang sama dari A; jika kita kalikan ini dengan akar kuadrat dari 2, itu seharusnya jarak dari A ke C. Kita menggunakan ini untuk mencari tahu titik mana yang C: Hitung distB = bx ^ 2 + oleh ^ 2, distD = dx ^ 2 + dy ^ 2. Jika distD ≥ 1,5 distB, maka kita menukar C dan D; jika distB ≥ 1,5 distD maka kita menukar C dan B. Sekarang C benar.

Kita juga bisa mengetahui titik mana yang B dan D: Jika kita menebak yang mana yang B dan mana yang D, maka perhitungan kita menempatkan D ke tempat yang sepenuhnya salah, persis berlawanan dari tempat itu. Jadi jika salah ≥ (bx ^ 2 + oleh ^ 2), maka kita menukar B dan D.

Ini akan mengatur B, C dan D dengan benar jika kita memang memiliki kotak atau paling tidak kira-kira kotak. Tetapi jika kita bahkan tidak memiliki persegi, kita tahu perhitungan kesalahan pada akhirnya akan menunjukkan ini.

Ringkasan:

1. Kurangi kapak dari bx, cx, dx. Kurangi ay dari by, cy, dy.
2. Biarkan distB = bx ^ 2 + x ^ 2, distD = dx ^ 2 + dy ^ 2.
3. Jika distD ≥ 1,5 * distB, tukar C dan D dan hitung distD lagi.
4. Sebaliknya, jika distB ≥ 1,5 * distD, tukar B dan C dan hitung distB lagi.
5. Biarkan errD = (dx + oleh) ^ 2 + (dy-bx) ^ 2.
6. Jika errD ≥ distB maka swap B dan D, swap distB dan distD, hitung errD lagi.
7. Biarkan errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2.
8. Biarkan err = (errC + errD) / distB.
9. Putuskan apakah kita memiliki kuadrat atau hampir kuadrat tergantung pada nilai err.

Jika kita mengetahui urutan poinnya, ini jelas dapat disederhanakan.

Solusi serupa dengan media berpikir.

Langkah pertama:

x = (A+B+C+D)/4
f=0
if(dist(x,A) == dist(x,B) == dist(x,C) == dist(x,D) 
   f=1
else
   f=0

Properti ini diikuti oleh bujur sangkar karena bersifat siklik. sekarang lingkaran untuk mengikuti properti ini. jadi, sekarang periksa saja

if(A.B==B.C==C.D==D.A==0)
  f=1
else 
  f=0

if (f==1)
  square
else 
  not square

Di sini AB berarti titik produk A dan B