Czy mogę uprościć nierówność „odległość (p1, p2) <odległość (p1, p3)?”

Pracuję nad pewną logiką wektorową, więc pytam: czy mogę zaoszczędzić czas procesora, upraszczając tę ​​nierówność:

distance(vector1, vector2) < distance(vector1, vector3)

Widzę, że vector1powtarza się to w obu przypadkach.

tak , możesz to uprościć. Po pierwsze, przestań nazywać je wektorami. Są punktami. Nazwijmy je A, Bi C.

Chcesz tego:

dist(A, B) < dist(A, C)

Wymienić odległości z odległościami do kwadratu, a następnie iloczyn skalarny (z definicji długości euklidesowej . Wymień ACzAB + BC (obecnie są to rzeczywiste wektory) Rozwiń, uproszczenia, czynnik.:

dist(A, B)² < dist(A, C)²
dot(AB, AB) < dot(AC, AC)
dot(AB, AB) < dot(AB + BC, AB + BC)
dot(AB, AB) < dot(AB, AB) + dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC, BC) + 2 dot(AB, BC)
0 < dot(BC + 2 AB, BC)

Tutaj jesteś:

dot(AB + AC, BC) > 0

Za pomocą notacji wektorowej:

dot(v2 - v1 + v3 - v1, v3 - v2) > 0

To kilka dodatków i jeden produkt kropkowy zamiast poprzednich dwóch produktów kropkowych.

Tak.Zakładając, że distancefunkcja używa pierwiastka kwadratowego, możesz to uprościć, usuwając pierwiastek kwadratowy.

Próbując znaleźć większą (lub mniejszą) odległość, x^2 > y^2 nadal obowiązuje x > y.

Jednak dalsze próby matematycznego uproszczenia równania są prawdopodobnie bezcelowe. Odległość między vector1i vector2nie jest taka sama jak odległość między vector1i vector3. Chociaż równanie można uprościć matematycznie, jak pokazuje odpowiedź Sama , forma, w jakiej się obecnie znajduje, jest prawdopodobnie tak prosta, jak to możliwe z perspektywy użycia procesora.

Niektóre matematyki mogą pomóc.

To, co próbujesz zrobić, to:

<v1, v2> < <v1, v3> =>
sqrt((y2-y1)^2+(x2-x1)^2) < sqrt((y3-y1)^2+(x3-x1)^2) =>
y2^2 - 2*y2y1 + y1^2 + x2^2 - 2*x2x1 + x1^2 < y3^2 - 2*y3y1 + y1^2 + x3^2 - 2*x3x1 + x1^2

Z tego, co możesz usunąć powtarzające się zmienne i pogrupować kilka innych. Operacja, którą musisz sprawdzić, to:

y3^2 - y2^2 - 2*y1(y3-y2) + x3^2 - x2^2 - 2*x1(x3-x2) > 0

Mam nadzieję, że to pomoże.

Prawdziwe pytanie wydaje się być to, jak ograniczyć obliczenia do określania najbliższego obiektu?

Optymalizacja jest często przeprowadzana w grach, chociaż przy wszystkich optymalizacjach powinna być prowadzona przez profil i często nie upraszcza rzeczy.

Sposobem uniknięcia niepotrzebnych obliczeń odległości w celu ustalenia najbliższej rzeczy - lub wszystkich rzeczy w określonym zakresie - jest użycie indeksu przestrzennego, np. Oktetu . .

Opłaca się to tylko w przypadku dużej liczby obiektów. W przypadku zaledwie trzech przedmiotów jest mało prawdopodobne, aby się spłaciło i na pewno nie upraszcza kodu.

zależy to od tego, jaka jest wydajność odległości (v1, v2)

jeśli jest to liczba dziesiętna (liczba zmiennoprzecinkowa lub podwójna) nad wektorem, prawdopodobne jest, że pokonane odległości byłyby znacznie szybsze