Czy są jakieś wady korzystania z czeków na odległość do kwadratu zamiast odległości?

Korzystam z kwadratowych kontroli odległości w zasadzie do sprawdzania wszystkich odległości (długość wektora3), ze względu na wzrost wydajności wynikający z braku naliczania pierwiastka kwadratowego (jak w przypadku kontroli zwykłej długości).

Wygląda na to, że kwadratowe kontrole odległości działają dobrze w każdej sytuacji:

if x^2 < y^2, then x < y, even when 0 < (x or y) < 1

Nie rozważam sytuacji, w których x lub y jest mniejsze niż 0, ponieważ odległość i kwadrat do odległości zawsze będą dodatnie.

Ponieważ to działa, wygląda na to, że kontrole odległości nigdy nie są potrzebne, ale mam dokuczliwe wrażenie, że czegoś mi brakuje. Czy nadal będzie to miało miejsce w sytuacjach krytycznych dla dokładności?

Nie ma żadnej wady, o której wiem, gdy używam kwadratowej długości do porównywania odległości. Pomyśl o tym w ten sposób: po prostu pomijasz to, sqrtco nie daje żadnej dodatkowej dokładności. Jeśli nie potrzebujesz rzeczywistej odległości euklidesowej, możesz bezpiecznie pominąć sqrt.

Oczywiście kwadratowa długość skaluje się zupełnie inaczej niż odległość euklidesowa i dlatego jest złym kandydatem do takich rzeczy, jak heurystyka poszukiwania ścieżki .

Jak wskazał bummzack z analogią Odnajdywanie Ścieżek, POTRZEBUJESZ używać „normalnej” długości za każdym razem, gdy sumujesz odległości i chcesz porównać ich sumę. (Tylko dlatego, że sumy kwadratów długości różnią się od kwadratów sum długości).

x ^ 2 + y ^ 2! = (x + y) ^ 2

Jedyną wadą, o której mogę pomyśleć, jest zajmowanie się dużymi liczbami, które przepełnią się po podniesieniu kwadratu.

Na przykład w Javie:

int x = Integer.MAX_VALUE / 1000000; //2147
int y = Integer.MAX_VALUE / 5000; //429496
System.out.println("x < y: " + (x < y)); //true
System.out.println("x*x: " + (x * x)); //4609609
System.out.println("y*y: " + (y * y)); //-216779712 - overflows!
System.out.println("x*x < y*y: " + (x * x < y * y)); //false - incorrect result due to overflow!

Warto również zauważyć, że tak się dzieje, gdy używasz Math.pow () z dokładnie tymi samymi liczbami i rzutujesz z powrotem na int z podwójnego zwrotu z Math.pow():

System.out.println("x^2: " + (int) (Math.pow(x, 2))); //4609609
System.out.println("y^2: " + (int) (Math.pow(y, 2))); //2147483647 - double to int conversion clamps to Integer.MAX_VALUE
System.out.println("x^2 < y^2: " + ((int) (Math.pow(x, 2)) < (int) (Math.pow(y, 2)))); //true - but for the wrong reason!

Czy to działa? Nie , podała tylko poprawną odpowiedź, ponieważ y*yjest ograniczona do Integer.MAX_VALUEi x*xjest mniejsza niż Integer.MAX_VALUE. Gdyby x*xrównież był zaciśnięty Integer.MAX_VALUE, otrzymałeś niepoprawną odpowiedź.

Podobne zasady obowiązują również w przypadku liczb zmiennoprzecinkowych i podwójnych (z tym wyjątkiem, że oczywiście mają większy zasięg przed przepełnieniem) oraz w każdym innym języku, który cicho dopuszcza przepełnienia.

Pewnego razu pracowałem na odległościach kwadratowych i popełniłem błąd, kumulując odległości kwadratowe dla licznika przebiegu.

Oczywiście nie możesz tego zrobić, ponieważ matematycznie

(a^2+b^2+c^2+d^2)!=(a+b+c+d)^2

Skończyło się na tym, że otrzymałem niepoprawny wynik. Ups!

Możesz napotkać kłopoty, jeśli piszesz algorytm, który wymaga obliczenia zoptymalizowanej pozycji. Załóżmy na przykład, że masz zestaw obiektów i próbujesz obliczyć pozycję przy najmniejszej całkowitej odległości od wszystkich obiektów. Dla konkretnego przykładu, powiedzmy, że próbujemy zasilić trzy budynki i chcemy dowiedzieć się, gdzie powinna iść elektrownia, abyśmy mogli połączyć ją ze wszystkimi budynkami za pomocą najmniejszej całkowitej długości drutu. Używając metryki odległości do kwadratu, skończyłbyś z współrzędną x elektrowni, która jest średnią współrzędnych x wszystkich budynków (i analogicznie dla współrzędnej y). Używając zwykłej miary odległości, rozwiązanie byłoby inne i często bardzo dalekie od rozwiązania kwadratu odległości.

Korzystanie z kwadratu odległości jest prawie zawsze w porządku i dobre dla wydajności. Ważne są następujące uwagi:

Jeśli chcesz pomyśleć o sumie kilku odległości, odległość do kwadratu będzie niedokładna. Na przykład mam dwie odległości i chcę się upewnić, że ich suma jest mniejsza niż 10. Poniższy kod jest niepoprawny:

a = get_distance_squared(c,d);
b = get_distance_squared(e,f);
assert(a+b < 10^2);

Nie można stwierdzić w następującym nieprawidłowym przypadku: a=36i b=49. W tym przypadku pierwsza długość wynosi 6, a druga 7; ich suma jest większa niż 10, ale suma kwadratów nie jest równa 100 lub większa.

Kolejna uwaga: dla odległości o wartościach rzeczywistych odległość do kwadratu zawsze będzie dodatnia. Jeśli na przykład mierzysz przemieszczenie, być może będziesz musiał poradzić sobie z wartościami ujemnymi, a kwadratowanie ich nie da rady.