Jak sprawdzić, czy 4 punkty tworzą kwadrat?

35

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).

MarshalSHI
źródło
3
Rozumiem, że musisz uwzględnić obrócone kwadraty?
Martijn Pieters
Czy w ogóle masz informacje na temat kolejności punktów? Czy możesz powiedzieć, czy dwa punkty sąsiadują ze sobą, czy tworzą przekątną? (te informacje można wykorzystać, aby uprościć proces)
Daniel B
1
@DanielB Brak innych informacji. Tak jak mam biały papier i losuję na nim 4 punkty losowo. Potem chcę wiedzieć, czy tworzą kwadrat.
MarshalSHI
5
W szczególności, jeśli punkty są reprezentowane jako liczby zmiennoprzecinkowe, przydatne jest uwzględnienie poczucia „tolerancji” w każdym z porównań sugerowanych poniżej. Dokładne kontrole równości mogą się nie powieść dla wyników operacji zmiennoprzecinkowych, nawet jeśli my ludzie uznalibyśmy je za „wystarczająco blisko”.
Stephan A. Terre
To pachnie jak zadanie domowe. Nie chodzi o to, że coś jest nie tak. : / whathaveyoutried.com
Jim G.

Odpowiedzi:

65

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!

Ilustracja kwadratowych zasad

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.

Joel Brown
źródło
19
Możesz zewrzeć ten proces i nie martwić się o porządek punktów, mierząc odległość między nimi i śledząc liczbę znalezionych unikalnych odległości. Po przekroczeniu dwóch ( x i Z Joela ) liczba nie jest kwadratem.
Blrfl,
3
Inną optymalizacją byłoby porównanie kwadratowych odległości zamiast odległości.
vaughandroid
4
@Blrfl: Twój test nie działa. Niech ABCD będzie diamentem z AB = BC = CD = DA = 1, AC = 1 też (krótka przekątna), a następnie AD ~ 1.7 (długa przekątna) / Masz tylko dwie długości xiz, ale figura nie jest kwadratem .
MSalters
2
@JelBrown: Możliwe jest utworzenie kształtu trapezu z przekątnymi AC = BD = x, bokami AB = BC = AD = z, a ostatnim bokiem CD = y! = Z.
Bart van Ingen Schenau
2
W porządku, zauważ jednak, że OP powiedział wyraźnie 2 wymiary.
Joel Brown,
24

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.

starblue
źródło
Jedna z dwóch dobrych odpowiedzi. Nie używaj, sqrtchyba że jest to niezbędne! Nie musisz obniżać obliczeń całkowitych do FP ... nie wspominając o pogorszeniu precyzji obliczeń FP.
K.Steff,
dzięki. dobry.
MarshalSHI
To jest właściwy sposób, aby to zrobić. Mnożenie rzeczywiście nie jest tutaj potrzebne.
PRZYJEDŹ Z
Jak znaleźć, czy 2 wektory są prostopadłe do siebie bez iloczynu iloczynu, który wymaga zwielokrotnienia?
Pavan Manjunath,
1
(x, y) obrócony o kąt prosty to (-y, x) lub (y, -x), w zależności od tego, czy obracasz odpowiednio w kierunku dodatnim czy ujemnym.
starblue
17

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.

Elian Ebbing
źródło
2
Tak. Jest to również najbardziej zrozumiały i prawdopodobnie najłatwiejszy do wdrożenia.
Eric G
Wydaje się, że wektorowa równość segmentów. Czy ktoś może opracować lub udowodnić, dlaczego to działa?
vCillusion
Nie udaje się to szczególnie w przypadku (0,0), (2,1), (3, -1), (1, -2) - kwadrat nie jest wyrównany do osi
v Cillusion
1
Działa w tym przypadku. Punkt środkowy to (1,5; -0,5), pierwszy punkt to (0, 0), a trzy inne punkty to (1,5; -0,5) + (1,5; -0,5) = (3; -1); (1,5, -0,5) + (0,5, 1,5) = (2, 1) i (1,5, -0,5) - (0,5, 1,5) = (1, -2), co oznacza, że ​​jest kwadratem. Dowodem jest ... symetria?
aragaer
1
„Rozwiązanie odległości” wymaga pierwiastków kwadratowych, ale istnieje „rozwiązanie odległości kwadratu”, które nie wymaga żadnego. Twoja może być jeszcze bardziej wydajna ...
maaartinus,
5

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.

To nie jest kwadrat ...

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:

I to też nie jest kwadrat ...

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ęć.

woliveirajr
źródło
nie, jego algorytm powiedział, że 2 krawędzie odległości x nie dzielą punktu. ale po prostu dzielisz C. Załóżmy, że AC to x, a BD powinno być kolejnym x zamiast BC.
MarshalSHI
3

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.

Mark Salzer
źródło
1
Myślę, że prostokąt również spełnia twoje warunki.
MarshalSHI
Nie, pierwszy warunek nie jest spełniony przez wektory ortogonalne, ale nie w równym stopniu wydłużone.
Mark Salzer
1
tak, po prostu tęsknię za pierwszym. Ale 4 punkty nie są uporządkowane. Myślę, że potrzebujemy więcej kroków, aby potwierdzić.
MarshalSHI
Tak ... jeśli nie pojawi się mądrzejszy pomysł, należałoby zapętlić. Myślę, że potrzebna jest zewnętrzna pętla do obliczenia w, x, y, z z każdego możliwego uporządkowania a, b, c, d i jednej wewnętrznej pętli dla każdego możliwego uporządkowania krotki w, x, y, z.
Mark Salzer,
2

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.

Max
źródło
Dobry pomysł, ale wciąż musisz sprawdzić, czy 4. wierzchołek znajduje się w odpowiedniej odległości od innych punktów. Sprawdzasz tylko, czy jest na przekątnej.
starblue
@starblue Racja! W przeciwnym razie może utworzyć latawiec. Zaktualizowano
Maks.
2

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.

GlenPeterson
źródło
2

wprowadź opis zdjęcia tutaj

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).

Reactgular
źródło
1

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.

bad_keypoints
źródło
1
Tutaj możesz podsumować algorytm. Linkujesz do innej strony SE, co jest nieco lepsze niż wskazanie innej strony, ale chcemy, aby odpowiedź była na tej stronie, na której zadawane jest pytanie. Teraz ludzie muszą kliknąć ponownie, aby dowiedzieć się, jaka może być odpowiedź.
Martijn Pieters
0

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.

Ana Nimbus
źródło
0

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ć.

gnasher729
źródło
-3

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.

singh13
źródło