Грубый расчет расстояния между 2 точками

Question

Я хочу вычислить приблизительное (приблизительное) расстояние между двумя точками, чтобы уменьшить накладные расходы на вычисления.

Я использую следующую формулу для расстояния между (x1, y1) & (x2, y2):

Dist = Mod (x1 - x2) + Mod (y1 - y2)

Где Mod - это оператор модуля, такой, что Mod (x) = | X |.

Кажется, это работает.

Я хочу знать, еслиЯ что-то упустил ...

Answer 1

Графическое представление трех обычных расстояний:

(Примечание: в этих трех метриках представлен круг радиуса 4).

Answer 2

Пока вы получаете абсолютное значение (как вы указали | X |) и не используете функцию модуля, это даст вам манхэттенское расстояние между двумя точками

Если это то, что выхотите, тогда вы ничего не пропустили

Если вы хотите расстояние по прямой, используйте теорему Пифагора.Это sqrt ((x1 - x2) ^ 2 + (y1 - y2) ^ 2)

Answer 3

Вы уверены, что у вас правильный оператор модуля?Похоже, что вы используете MOD как ABSOLUTE

http://en.wikipedia.org/wiki/Modulo_operation

в любом случае, как говорит Мердад, используя теорему Пифагора:

Dist = Sqrt( (x1-x2)^2 + (y1-y2)^2 )

Answer 4

Вы должны быть конкретны с точки зрения расстояния, которое вы хотите вычислить.

Формула расстояния: Учитывая две точки (x1, y1) и (x2, y2),расстояние между этими точками определяется по формуле:

Это стандартная формула, которую мы используем в геометрии Co-Ordinate для нахождения расстояния между точками, и это специализация MinKowski distance за одно измерение.

Answer 5

Если вы хотите сравнить расстояния и сэкономить время, используйте не само расстояние, а его квадрат: (x1-x2) ^ 2 + (y1-y2) ^ 2. Не принимайте sqrt. Таким образом, ваши расстояния будут работать точно так же, как нормальные, но быстро. Подсчет dx = x1-x2 и dx2 = dx * dx даже быстрее, чем принимать ABS (вы имели в виду, а не MOD), потому что последний - это функция, и вы должны за нее платить.

Расстояние АБС правильное - теоретически. Но какая от этого польза, если она груба для ваших целей?

Answer 6

Ваш показатель расстояния подходит для грубого расстояния. Но (x ₂ - x ₁ ) ² + (y ₂ - y ₁ ) ² даст вам квадрат фактического расстояния. Пока вы помните, что это квадрат расстояния, это будет более точным. И в зависимости от архитектуры, на которой вы это реализуете, это может быть быстрее - умножение может занять меньше времени, чем ветвь в модуле, либо для аппаратных реализаций вполне может потребоваться то же время. Вам нужно будет проверить, чтобы быть уверенным.

Answer 7

Я сделал этот алгоритм для вычисления расстояния по прямой линии между 2 точками:

var distance = function(x1, y1, x2, y2) {
            //Distance Horizantally
            var horizontalDistance = 0;
            /Distance Vertically
            var verticalDistance = 0;
            
            if(x1 > x2) {
                horizantalDistance = x1 - x2;
            }
            else {
                horizantalDistance = x2 - x1;
            }
            
            if(y1 > y2) {
                verticalDistance = y1 - y2;
            }
            else {
                verticalDistance = y2 - y1;
            }

            var answer = 0;
            
            if(verticalDistance !== 0 && horizantalDistance !== 0) {
                //Use the Pathagoreum Theorum
                answer = Math.sqrt(verticalDistance + horizantalDistance);
            }
            else if(horizantalDistance === 0) {
                //Use the Vertical Distance
                answer = verticalDistance;
            }
            else if (verticalDistance === 0) {
                //Use the Horizantal distance
                answer = horizantalDistance;
            }
            //Return the answer
            return answer;
        }