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).
algorithms
math
geometry
MarshalSHI
źródło
źródło
Odpowiedzi:
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:
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.
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:
Ponieważ AB = AD, sprawdź BD:
Dla pewności musisz sprawdzić inne strony: BC i CD.
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.
źródło
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.
źródło
sqrt
chyba że jest to niezbędne! Nie musisz obniżać obliczeń całkowitych do FP ... nie wspominając o pogorszeniu precyzji obliczeń FP.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
v2
wektor będziev
obrócony o 90 stopni:v2 := (-y, x)
Teraz inne punkty powinny być
center - v
,center + v2
icenter - v2
.Zaletą tego rozwiązania jest to, że nie musisz wcale używać pierwiastków kwadratowych.
źródło
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ęć.
źródło
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.
źródło
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.
źródło
Myślę, że możesz to zrobić za pomocą prostego dodawania i odejmowania oraz znajdowania min / max. Warunki (pasuje do diagramu innych osób):
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:
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.
źródło
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.
Po uzyskaniu średniej odległość między każdym punktem a średnią musiałaby być taka sama dla wszystkich czterech punktów.
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.
Zakłada się, że punkty A, B, C, D nie krzyżują się (jak w prawidłowej kolejności nawijania).
źródło
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
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.
źródło
Podstawowy pomysł (odpowiada to na pytanie, czy wnoszę coś nowego, o co pytał bot, kiedy kliknąłem, by podać odpowiedź):
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.
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”.
xy
odnosi się do rodzaju matrycy zaakceptowany przez grupę Rplot
,points
ilines
funkcji.Zastosowanie
as.data.frame
jest sztuczką, aby skłonić R do robienia rzeczy w kolumnie.optional=T
Klauzula eliminuje nazw, które nie są używane, w każdym razie.Jest to funkcja do obliczania kwadrancji między określonymi punktami, w których
i2
argument par określa para punktów .i2
Symbol 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ę).Przedstawiony
.which
jest jako argument jedynie po to, aby go wystawićformals
i spróbować przekazać, co się dzieje.Powiedziałem, że „prosty” nie zawiera funkcji multilinii. Musisz usprawiedliwić tę funkcję dwuwierszową.
Zauważ, że pierwsze cztery funkcje są użyteczne same w sobie, oprócz pytania o cztery punkty.
źródło
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:
Jeśli znamy kolejność punktów, można to oczywiście uprościć.
źródło
Rozwiązanie jest podobne do mediów myślących.
Pierwszy krok:
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ź
Tutaj AB oznacza iloczyn skalarny A i B.
źródło