15

所以显然计算平方根不是很有效，这让我想知道找出两个圆之间的距离（我在下面称为范围）的最佳方法是什么？

查找两个圆之间的范围

所以通常我会解决：

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

然后找到下位点 Sin(theta) = dy/h h = dy/Sin(theta)

最后计算出范围 range + 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 值，这值得吗？

还是完全有另一种方式？

如果我问的很明显，或者犯了任何基本错误，请原谅，我已经很久没有用高中数学做任何事情了......

欢迎任何提示或建议！

****编辑****

具体来说，我正在尝试在游戏中创建一个“扫描仪”设备，以检测敌人/障碍物何时接近/消失等。扫描仪将通过音频或图形条或其他东西传递此信息。因此，虽然我不需要确切的数字，但理想情况下我想知道：

  1. 目标比以前更近/更远
  2. 目标 A 比目标 B、C、D 更近/更远……
  3. 一个（希望是线性的？）比率，表示目标与船的距离相对于 0（碰撞）和最大范围（某个常数）
  4. 一些目标会非常大（行星？）所以我需要考虑半径

我希望有一些聪明的优化/近似可能（dx + dy +（更长的dx，dy？），但有所有这些要求，也许不是......

4

4 回答 4

12

Math.hypot旨在获得更快、更准确的表格计算sqrt(x^2 + y^2)。所以这应该只是

return Math.hypot(x1 - x2, y1 - y2) - r1 - r2;

我无法想象任何代码会比这更简单，也不会更快。

于 2012-05-19T16:54:58.910 回答
9

如果您真的需要准确的距离，那么您将无法真正避免平方根。三角函数至少和平方根计算一样糟糕，如果不是更糟的话。

但是，如果您只需要近似距离，或者如果您只需要各种圆组合的相对距离，那么您肯定可以做一些事情。例如，如果您只需要相对距离，请注意平方数与其平方根具有相同的大于关系。如果您只是比较不同的配对，请跳过平方根步骤，您将得到相同的答案。

如果您只需要近似距离，那么您可能会认为它h大致等于较长的相邻边。这个近似值的偏差永远不会超过两倍。或者您可以为三角函数使用查找表——这比查找任意平方根的查找表更实用。

于 2012-05-19T14:46:06.573 回答
1

我厌倦了首先弄清楚当我们使用 tan、sine 时的答案是否与使用 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 更正确的值之间似乎存在差异。

  1. 谈论性能：考虑您的代码片段：

我计算了表演时间——结果如下：

    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

当我们尝试使用 sqrt root 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

现在，如果我们检查差异，两个答案之间的差异也很大。

因此我会说，如果你让游戏更准确，数据会更有趣，它对用户来说应该是更有趣的。

于 2012-05-19T15:53:03.900 回答
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);
    }
}

（我没有测试此代码，请原谅并纠正任何错误）

此外，在写完这一切之后，可能已经有一些近似的、高效的、替代的数学库了。您应该寻找它，但前提是您发现性能确实是必要的。

于 2012-05-19T16:24:11.240 回答