Jak sprawdzić, czy 4 punkty tworzą kwadrat?

Załóżmy, że mam 4 punkty (są 2-wymiarowe), które różnią się od siebie i chcę wiedzieć, czy tworzą kwadrat. Jak to zrobić? (niech proces będzie tak prosty, jak to możliwe).

Zakładając, że Twój kwadrat może zostać obrócony w stosunku do dowolnego układu współrzędnych, który masz na miejscu, nie możesz polegać na powtarzaniu wartości X i Y w twoich czterech punktach.

Co możesz zrobić, to obliczyć odległości między każdym z czterech punktów. Jeśli uważasz, że są spełnione następujące warunki, masz kwadrat:

1. Istnieją dwa punkty, powiedzmy A i C, które są odległością x od siebie, i dwa inne punkty, powiedzmy B i D, które również są odległością x od siebie.

2. Każdy punkt {A, B, C, D} jest w równej odległości od dwóch punktów, które nie znajdują się w odległości x . tzn .: jeśli A jest x od C, to będzie z z dala od B i D.

Nawiasem mówiąc, odległość z będzie musiała wynosić SQRT (( x ^ 2) / 2), ale nie musisz tego potwierdzać. Jeśli warunki 1 i 2 są spełnione, masz kwadrat. UWAGA: Niektóre osoby są zaniepokojone nieefektywnością pierwiastka kwadratowego. Nie powiedziałem, że powinieneś wykonać te obliczenia, po prostu powiedziałem, że jeśli to zrobisz, uzyskasz przewidywalny wynik!

Absolutnym minimum pracy, jaką musisz wykonać, byłoby wybranie punktu, powiedzenie A i obliczenie odległości do każdego z pozostałych trzech punktów. Jeśli okaże się, że A wynosi x z jednego punktu az z dwóch innych punktów, wystarczy sprawdzić te dwa inne punkty względem siebie. Jeśli są również x względem siebie, masz kwadrat. to znaczy:

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

Ponieważ AB = AD, sprawdź BD:

• BD = x

Dla pewności musisz sprawdzić inne strony: BC i CD.

• BC = z
• CD = z

Ponieważ AC = BD, a AB: AD = BC = CD, jest to zatem kwadrat.

Po drodze, jeśli znajdziesz więcej niż dwie wyraźne odległości od krawędzi, postać nie może być kwadratem, więc możesz przestać patrzeć.

Implementacja przykładu roboczego

Stworzyłem działający przykład na jsfiddle (patrz tutaj ). Wyjaśniając algorytm, używam dowolnych punktów A, B, C i D. Te przypadkowe punkty są w określonej kolejności, aby przejść przez przykład. Algorytm działa nawet wtedy, gdy punkty są w innej kolejności, jednak przykładem niekoniecznie działa, jeśli te punkty są w innej kolejności.

Dzięki: meshuai, Blrfl, MSalters i Bart van Ingen Schenau za przydatne komentarze w celu poprawy tej odpowiedzi.

Wybierz trzy z czterech punktów.

Sprawdź, czy jest to prawy trójkąt równoramienny, sprawdzając, czy jeden z trzech wektorów między punktami jest równy drugiemu obróconemu o 90 stopni.

Jeśli tak, oblicz czwarty punkt przez dodanie wektora i porównaj go z danym czwartym punktem.

Zauważ, że nie wymaga to drogich pierwiastków kwadratowych, nawet mnożenia.

Myślę, że najłatwiejszym rozwiązaniem jest:

• Najpierw obliczyć środek 4 punktów: center = (A + B + C + D)/4

• Następnie obliczyć wektor A - center. Niech tak będziev := (x,y)

• Niech v2wektor będzie vobrócony o 90 stopni:v2 := (-y, x)

• Teraz inne punkty powinny być center - v, center + v2i center - v2.

Zaletą tego rozwiązania jest to, że nie musisz wcale używać pierwiastków kwadratowych.

Przykro mi, ale niektóre odpowiedzi nie mają zastosowania.

W przypadku, gdy mierzysz 3 krawędzie (powiedzmy AB, AC i AD), aby stwierdzić, że dwa mają ten sam rozmiar (powiedzmy AC i AD), a jeden jest większy (powiedzmy AB). Następnie zmierzyłbyś CD, aby zobaczyć, czy jest tego samego rozmiaru AB, i okazało się, że tak. Zamiast kwadratu możesz mieć poniższy obrazek, co sprawia, że ​​jest to złe rozwiązanie.

Następnie wypróbuj inne rozwiązanie: zmierz wszystkie odległości przynajmniej raz: AB, AC, AD, BC, BD, CD. Potem okazuje się, że 4 z nich są równe, a pozostałe 2 są równe między sobą. Ale możesz mieć zdjęcie takie jak poniżej:

Tak więc odpowiedzi te są niepoprawne, pomimo wysokich ocen pozytywnych.

Jedno możliwe rozwiązanie: jeśli dwie równe miary nie łączą tego samego punktu. Tak więc: jeśli AB i CD są tej samej długości, wszystkie inne kombinacje (AC, AD, BC, BD) są równe, masz kwadrat. Jeśli masz ten sam punkt, tworząc największą długość (AB i AC są największe, a wszystkie pozostałe są równe), masz jedno z powyższych zdjęć.

Niech cztery punkty mają wektory współrzędnych a, b, c, d.

Następnie nazwijmy ich różnice w = (reklama), x = (ba), y = (cb), z = (dc).

Wtedy w jest prostopadłe do a, jeśli możesz utworzyć w z obrotu o 90 stopni. Matematycznie macierz obrotu 90 stopni w przestrzeni 2 to ((0, -1), (1, 0)). Zatem warunek, czy w jest obrócony o 90 stopni a, daje wynik

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

Jeśli tak się stanie, musisz sprawdzić, czy w == -y i x == -z lub

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

Jeśli te trzy relacje się utrzymują, a, b, c, d tworzą kwadrat zorientowany.

Podobne do odpowiedzi starblue

Wybierz dowolne trzy z czterech punktów.

Poszukaj między nimi wierzchołka ustawionego pod kątem prostym : Sprawdzając, czy iloczyn iloczynu dowolnych dwóch z trzech wektorów jest równy zero. Jeśli nie znaleziono, nie kwadrat.

Sprawdź, czy wierzchołki sąsiadujące z tym kątem są również ustawione pod kątem prostym. Jeśli nie, nie kwadrat.

Sprawdź, czy przekątne są prostopadłe : Jeśli iloczyn punktowy wektorów między pierwszym i czwartym wierzchołkiem i pozostałymi dwoma wierzchołkami (przekątnymi) wynosi zero, to jest to kwadrat.

Myślę, że możesz to zrobić za pomocą prostego dodawania i odejmowania oraz znajdowania min / max. Warunki (pasuje do diagramu innych osób):

• Punkt o najwyższej wartości y => A
• najwyższa x => B
• najniższe y => C
• najniższy x => D

Jeśli 4 punkty dzielą tylko 2 x wartości i 2 y wartości, masz kwadrat poziomu.

W przeciwnym razie masz kwadrat, jeśli twoje punkty spełniają następujące warunki:

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

Objaśnienie: Segmenty linii AC i BD powinny się spotkać w punktach środkowych. Zatem (Ax + Cx) / 2 jest punktem środkowym AC, a (Bx + Dx) / 2 jest punktem środkowym BD. Pomnóż każdą stronę tego równania przez 2, aby otrzymać moje pierwsze równanie. Drugie równanie jest takie samo dla wartości Y. Diamentowe kształty (romboidy) spełnią te właściwości, więc musisz sprawdzić, czy masz równe boki - czy szerokość jest taka sama jak wysokość. To jest trzecie równanie.

Jest tu kilka dobrych odpowiedzi, ale pytanie dotyczy najprostszego podejścia. Zastanowiłem się nad tym i tak bym to zrobił.

Możesz stwierdzić, czy cztery punkty reprezentują kwadrat (nawet jeśli są obrócone), ale znajdując średnią z czterech punktów.

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

Po uzyskaniu średniej odległość między każdym punktem a średnią musiałaby być taka sama dla wszystkich czterech punktów.

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

EDYTOWAĆ:

Mój błąd. To by powiedziało tylko, gdyby punkty formy były na okręgu. Jeśli sprawdzisz także odległość między punktami, to musi to być kwadrat.

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"

Zakłada się, że punkty A, B, C, D nie krzyżują się (jak w prawidłowej kolejności nawijania).

zgodnie z ustalonymi standardami nie jest to odpowiedź, ale mam nadzieję, że to pomoże:

[Skopiowano z poniższego linku, więc nie trzeba go otwierać] Python 76 znaków

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

Funkcja S przyjmuje listę liczb zespolonych jako swoje dane wejściowe (A). Jeśli znamy zarówno środek, jak i jeden narożnik kwadratu, możemy go zrekonstruować, obracając narożnik o 90,180 i 270 stopni wokół punktu środkowego (c). Na płaszczyźnie złożonej obrót o 90 stopni wokół punktu początkowego odbywa się przez pomnożenie punktu przez i. Jeśli nasz pierwotny kształt i zrekonstruowany kwadrat mają te same punkty, to musiał to być kwadrat.

To zostało zaczerpnięte z: Ustal, czy 4 punkty tworzą kwadrat

Jeśli podoba ci się odpowiedź, mówię, poświęć chwilę, aby podziękować osobie lub głosuj jej odpowiedź na tej stronie.

Podstawowy pomysł (odpowiada to na pytanie, czy wnoszę coś nowego, o co pytał bot, kiedy kliknąłem, by podać odpowiedź):

• romb o równych przekątnych jest kwadratem.
• „prosty jak to możliwe” obejmuje:
  • bez podziału,
  • bez pierwiastków kwadratowych,
  • bez rozgałęzień,
  • bez wyszukiwania
  • bez sprawdzania lub ścigania kąta,
  • brak wektorów,
  • bez przekształceń,
  • brak liczb zespolonych,
  • brak funkcji multilinii oraz
  • bez importowania specjalnych pakietów (używaj tylko wbudowanych rzeczy).
  • (I żadnych imperialnych uwikłań!)

Moje rozwiązanie w R jest przedstawione poniżej. Zakładam, że są dokładnie cztery punkty i że zgodnie z opisem problemu ustalono już, że punkty są unikalne.

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

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

Zobacz prace Normana Wildbergera, zwłaszcza jego filmy z YouTube'a ( prawdziwe ryby, prawdziwe liczby, prawdziwe miejsca pracy i kolejne) oraz jego książkę Divine Proportions do dyskusji na temat „kwadrantu”.

xyodnosi się do rodzaju matrycy zaakceptowany przez grupę R plot, pointsi linesfunkcji.

Zastosowanie as.data.framejest sztuczką, aby skłonić R do robienia rzeczy w kolumnie.

optional=TKlauzula eliminuje nazw, które nie są używane, w każdym razie.

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

Jest to funkcja do obliczania kwadrancji między określonymi punktami, w których i2argument par określa para punktów . i2Symbol odnosi się do indeksu matrycy, która ma jedną kolumnę w każdym indeksie i 2 elementów na kolumnie (taki sam rodzaj matrycy zwracana przezcombn funkcję).

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

Przedstawiony .whichjest jako argument jedynie po to, aby go wystawićformals i spróbować przekazać, co się dzieje.

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
}

Powiedziałem, że „prosty” nie zawiera funkcji multilinii. Musisz usprawiedliwić tę funkcję dwuwierszową.

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

Zauważ, że pierwsze cztery funkcje są użyteczne same w sobie, oprócz pytania o cztery punkty.

Załóżmy, że cztery punkty A = (ax, ay), B = (bx, by), C = (cx, cy), D = (dx, dy) i tworzą punkty kwadratu w kolejności przeciwnej do ruchu wskazówek zegara. Przesuwamy punkty tak, aby A znajdowało się w (0, 0), odejmując ax od bx, cx i dx, i odejmując ay od przez, cy i dy, ustawiając ax = ay = 0.

Jeśli punkty są dokładnie w rogach kwadratu w kolejności przeciwnej do ruchu wskazówek zegara, to biorąc pod uwagę A i B, możemy obliczyć, gdzie są C i D: Powinniśmy mieć (cx, cy) = (bx - by, bx + by) i (dx, dy) = (-by, bx). Obliczamy zatem kwadrat do odległości od miejsca, w którym znajdują się C i D, do miejsca, w którym powinny być: errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2 i errD = (dx + by) ^ 2 + (dy - bx) ^ 2. Dodajemy je i dzielimy przez (bx ^ 2 + przez ^ 2), dając err = (errC + errD) / (bx ^ 2 + przez ^ 2).

Wynikowy błąd będzie wynosił 0, jeśli idealny kwadrat lub niewielka liczba, jeśli prawie kwadrat, a liczba pozostanie niezmieniona, z wyjątkiem błędów zaokrąglania, jeśli tłumaczymy, skalujemy lub obracamy punkty kwadratu. Możemy więc użyć err, aby zdecydować, jak dobry mamy kwadrat.

Ale nie znamy kolejności punktów. B i D powinny znajdować się w tej samej odległości od A; jeśli pomnożymy to przez pierwiastek kwadratowy z 2, powinna to być odległość od A do C. Używamy tego, aby dowiedzieć się, który punkt to C: Oblicz distB = bx ^ 2 + przez ^ 2, distD = dx ^ 2 + dy ^ 2. Jeśli distD ≥ 1,5 distB, zamieniamy C i D; jeśli distB ≥ 1,5 distD to zamieniamy C i B. Teraz C ma rację.

Możemy również dowiedzieć się, które punkty to B i D: Jeśli źle zgadliśmy, który to B, a który to D, wówczas nasze obliczenia umieszczają D w całkowicie niewłaściwym miejscu, dokładnie odwrotnie niż tam, gdzie jest. Więc jeśli errD ≥ (bx ^ 2 + o ^ 2), wówczas zamieniamy B i D.

Spowoduje to prawidłowe ustawienie B, C i D, jeśli rzeczywiście mamy kwadrat lub przynajmniej z grubsza kwadrat. Ale jeśli nie mamy nawet z grubsza kwadratu, wiemy, że obliczenie błędu na końcu to pokaże.

Podsumowanie:

1. Odejmij ax od bx, cx, dx. Odejmij, od, cy, dy.
2. Niech distB = bx ^ 2 + przez ^ 2, distD = dx ^ 2 + dy ^ 2.
3. Jeśli distD ≥ 1,5 * distB, zamień C i D i ponownie oblicz distD.
4. W przeciwnym razie, jeśli distB ≥ 1,5 * distD, zamień B i C i ponownie oblicz distB.
5. Niech errD = (dx + by) ^ 2 + (dy - bx) ^ 2.
6. Jeśli errD ≥ distB, to zamień B i D, zamień distB i distD, oblicz ponownie errD.
7. Niech errC = (cx - bx + by) ^ 2 + (cy - bx - by) ^ 2.
8. Niech err = (errC + errD) / distB.
9. Zdecyduj, czy mamy kwadrat, czy prawie kwadrat, w zależności od wartości err.

Jeśli znamy kolejność punktów, można to oczywiście uprościć.

Rozwiązanie jest podobne do mediów myślących.

Pierwszy krok:

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

Po tej właściwości następuje kwadrat, ponieważ jest ona cykliczna. teraz okrąg, aby śledzić tę właściwość. więc teraz po prostu sprawdź

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

if (f==1)
  square
else 
  not square

Tutaj AB oznacza iloczyn skalarny A i B.