Так что, по-видимому, вычисление квадратных корней не очень эффективно, что оставляет мне интересно, что лучший способ узнать расстояние (которое я назвал диапазоном ниже) между двумя кругами?
Как обычно, я бы выработал:
a^2 + b^2 = c^2
dy^2 + dx^2 = h^2
dy^2 + dx^2 = (r1 + r2 + range)^2
(dy^2 + dx^2)^0.5 = r1 + r2 + range
range = (dy^2 + dx^2)^0.5 - r1 - r2
Попытка избежать квадратного корня отлично работает, когда вы просто ищете ситуацию, когда "диапазон" равен 0 для коллизий:
if ( (r1 + r2 + 0 )^2 > (dy^2 + dx^2) )
Но если я пытаюсь разобраться в дальности дальности, я получаю какое-то громоздкое уравнение вроде:
range(range + 2r1 + 2r2) = dy^2 + dx^2 - (r1^2 + r2^2 + 2r1r2)
который никуда не денется. По крайней мере, я не знаю, как его решить для диапазона отсюда...
Очевидным ответом тогда является тригнометрия и сначала найдите theta:
Tan(theta) = dy/dx
theta = dy/dx * Tan^-1
Затем найдем гипотезу Грех (тета) = dy/h h = dy/Sin (theta)
Наконец, определите диапазон диапазон + r1 + r2 = dy/Sin (theta) range = dy/Sin (theta) - r1 - r2
Итак, что я сделал и получил метод, который выглядит так:
private int findRangeToTarget(ShipEntity ship, CircularEntity target){
//get the relevant locations
double shipX = ship.getX();
double shipY = ship.getY();
double targetX = target.getX();
double targetY = target.getY();
int shipRadius = ship.getRadius();
int targetRadius = target.getRadius();
//get the difference in locations:
double dX = shipX - targetX;
double dY = shipY - targetY;
// find angle
double theta = Math.atan( ( dY / dX ) );
// find length of line ship centre - target centre
double hypotemuse = dY / Math.sin(theta);
// finally range between ship/target is:
int range = (int) (hypotemuse - shipRadius - targetRadius);
return range;
}
Итак, мой вопрос заключается в том, что использование tan и sin более эффективно, чем поиск квадратного корня?
Возможно, я смогу реорганизовать часть моего кода, чтобы получить значение theta из другого метода (где я должен его обработать), что стоит делать?
Или существует другой способ?
Пожалуйста, извините меня, если я прошу очевидного или совершу какие-либо элементарные ошибки, это было давно, так как я использовал математику средней школы, чтобы что-то сделать...
Любые советы или рекомендации приветствуются!
**** **** EDIT
В частности, я пытаюсь создать устройство "сканер" в игре, которая обнаруживает, когда враги/препятствия приближаются/уходят и т.д. Сканер будет передавать эту информацию через звуковой тон или графическую панель или что-то в этом роде. Поэтому, хотя мне не нужны точные цифры, в идеале я хотел бы знать:
Я надеюсь, что возможна какая-то умная оптимизация/аппроксимация (dx + dy + (дольше dx, dy?), но со всеми этими требованиями, возможно, не...
Math.hypot предназначен для получения более быстрых и точных расчетов формы sqrt(x^2 + y^2). Так что это должно быть просто
return Math.hypot(x1 - x2, y1 - y2) - r1 - r2;
Я не могу представить какой-либо код, который был бы проще этого и не быстрее.
Если вам действительно нужно точное расстояние, вы не можете избежать квадратного корня. Тригонометрические функции по меньшей мере так же плохи, как вычисления с квадратным корнем, если не хуже.
Но если вам нужны только приблизительные расстояния или вам нужны только относительные расстояния для различных комбинаций кругов, то, безусловно, вы можете сделать что-то. Например, если вам нужны только относительные расстояния, обратите внимание, что квадрат чисел имеет те же отношения, что и их отношения, как и их квадратные корни. Если вы только сравниваете разные пары, пропустите шаг квадратного корня, и вы получите тот же ответ.
Если вам нужны только приблизительные расстояния, вы можете подумать, что h примерно равно более длинной смежной стороне. Это приближение никогда не отключается более чем в два раза. Или вы можете использовать таблицы поиска для тригонометрических функций, которые более практичны, чем таблицы поиска для произвольных квадратных корней.
Я устал прорабатывать, во-первых, ответы, когда мы используем tan, синус такой же, как при использовании функций sqrt.
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
double shipX = 5;
double shipY = 5;
double targetX = 1;
double targetY = 1;
int shipRadius = 2;
int targetRadius = 1;
//get the difference in locations:
double dX = shipX - targetX;
double dY = shipY - targetY;
// find angle
double theta = Math.toDegrees(Math.atan( ( dY / dX ) ));
// find length of line ship centre - target centre
double hypotemuse = dY / Math.sin(theta);
System.out.println(hypotemuse);
// finally range between ship/target is:
float range = (float) (hypotemuse - shipRadius - targetRadius);
System.out.println(range);
hypotemuse = Math.sqrt(Math.pow(dX,2) + Math.pow(dY,2));
System.out.println(hypotemuse);
range = (float) (hypotemuse - shipRadius - targetRadius);
System.out.println(range);
}
Ответ, который я получил, был: 4,700885452542996
1.7008854
5,656854249492381
2.6568542
Теперь кажется, что разница между значениями с точками sqrt более правильна.
i вычислил время выполнения, которое выражается как:
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
long lStartTime = new Date().getTime(); //start time
double shipX = 555;
double shipY = 555;
double targetX = 11;
double targetY = 11;
int shipRadius = 26;
int targetRadius = 3;
//get the difference in locations:
double dX = shipX - targetX;
double dY = shipY - targetY;
// find angle
double theta = Math.toDegrees(Math.atan( ( dY / dX ) ));
// find length of line ship centre - target centre
double hypotemuse = dY / Math.sin(theta);
System.out.println(hypotemuse);
// finally range between ship/target is:
float range = (float) (hypotemuse - shipRadius - targetRadius);
System.out.println(range);
long lEndTime = new Date().getTime(); //end time
long difference = lEndTime - lStartTime; //check different
System.out.println("Elapsed milliseconds: " + difference);
}
Ответ - 639.3204215458475, 610,32043, Истекшие миллисекунды: 2
И когда мы пытаемся с помощью root sqrt one:
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
long lStartTime = new Date().getTime(); //start time
double shipX = 555;
double shipY = 555;
double targetX = 11;
double targetY = 11;
int shipRadius = 26;
int targetRadius = 3;
//get the difference in locations:
double dX = shipX - targetX;
double dY = shipY - targetY;
// find angle
double theta = Math.toDegrees(Math.atan( ( dY / dX ) ));
// find length of line ship centre - target centre
double hypotemuse = Math.sqrt(Math.pow(dX,2) + Math.pow(dY,2));
System.out.println(hypotemuse);
float range = (float) (hypotemuse - shipRadius - targetRadius);
System.out.println(range);
long lEndTime = new Date().getTime(); //end time
long difference = lEndTime - lStartTime; //check different
System.out.println("Elapsed milliseconds: " + difference);
}
Ответ - +769,3321779309637, 740,33215, Истекшие миллисекунды: 1
Теперь, если мы проверим разницу, разница между двумя ответами также огромна.
следовательно, я бы сказал, что если вы сделаете игру более точной, данные будут более интересными для пользователя.
Проблема, обычно возникающая с sqrt в "жестком" программном обеспечении геометрии, - это не ее производительность, а потеря точности, которая приходит с ней. В вашем случае sqrt отлично подходит для счета.
Если вы обнаружите, что sqrt действительно приносит штрафы за производительность - вы знаете, оптимизируйте только при необходимости - вы можете попробовать с линейным приближением.
f(x) ~ f(X0) + f'(x0) * (x - x0)
sqrt(x) ~ sqrt(x0) + 1/(2*sqrt(x0)) * (x - x0)
Итак, вы вычисляете таблицу поиска (LUT) для sqrt и, учитывая x, использует ближайшую x0. Конечно, это ограничивает ваши возможные диапазоны, когда вы должны отступать от обычных вычислений. Теперь, некоторый код.
class MyMath{
private static double[] lut;
private static final LUT_SIZE = 101;
static {
lut = new double[LUT_SIZE];
for (int i=0; i < LUT_SIZE; i++){
lut[i] = Math.sqrt(i);
}
}
public static double sqrt(final double x){
int i = Math.round(x);
if (i < 0)
throw new ArithmeticException("Invalid argument for sqrt: x < 0");
else if (i >= LUT_SIZE)
return Math.sqrt(x);
else
return lut[i] + 1.0/(2*lut[i]) * (x - i);
}
}
(я не тестировал этот код, прошу простить и исправить любые ошибки)
Кроме того, после написания всего этого, вероятно, есть уже некоторая приблизительная, эффективная альтернативная математическая библиотека. Вы должны искать его, но только если вы обнаружите, что производительность действительно необходима.