0

I'm trying to do distance checks between two circles without using square roots. According to many sources online (such as this one), the way to do this is to subtract the square of the sum of the circles' radii from the squared distance (using Pythagoras's theorem). However, this doesn't seem to work. According to Wolfram Alpha and my own tests, the check doesn't work like the sqrt version. Here's the two equations compared in Wolfram: http://www.wolframalpha.com/input/?i=sqrt%28d%29+-+%28r1%2Br2%29+%3C+y+%3D%3D+d+-+%28r1%2Br2%29%5E2+%3C+y

As well as the relevant code that fails to comply:

T DistanceTo(Point p) const {
    return sqrt((p.x - x)*(p.x - x) + (p.y - y)*(p.y - y));
}

T DistanceToSq(Point p) const {
    return (p.x - x)*(p.x - x) + (p.y - y)*(p.y - y);
}

float Unit::GetDistanceTo(Unit * tgt)   const {
    auto dist = _pos.DistanceTo(tgt->GetPos());
    dist -= GetRadius() + tgt->GetRadius();
    return dist;
}
float Unit::GetDistanceToSq(Unit * tgt) const {
    auto dist = _pos.DistanceToSq(tgt->GetPos());
    auto radii = (GetRadius() + tgt->GetRadius());
    dist -= radii * radii;
    return dist;
}

template<typename Func>
void ForEachRange(Unit * owner, float range, Func func = [](Unit * tgt)) {
    auto range_sq = range * range;

    for(Unit * p : m_players) {
        if(owner == p || owner->GetDistanceToSq(p) >= range_sq) {
            if(owner != p && owner->GetDistanceTo(p) < range)
                assert(0);

            continue;
        }

        assert(owner->GetDistanceTo(p) < range);

        func(p);
    }
}

Am I doing something wrong or is the formula simply incorrect?

Community
  • 1
  • 1
Cleroth
  • 144
  • 1
  • 11
  • What are you trying to find? the absolute distance between 2 circles? If they overlap? Both solutions actually work out the same: gap = (distance between centers) - r1 - r2. If the value is negative, they overlap. If positive, you have your gap – JonTheMon Aug 20 '14 at 21:46
  • Yes, I want the gap. But getting the actual distance between the centers requires a square root. Thus, what I want is the _squared_ gap between the circles. According to other people it should be `gap^2 = (distance between centers)^2 - (r1 + r2)^2` but this doesn't seem to work. – Cleroth Aug 20 '14 at 21:58

2 Answers2

1

You asked Wolfram Alpha if sqrt(d) - (r1+r2) < y is equivalent to d - (r1+r2)^2 < y and Alpha said “no”.

Let's take the first inequality from your query and eliminate the square root using algebra:

sqrt(d) - (r1 + r2) < y
            sqrt(d) < y + r1 + r2
                  d < (y + r1 + r2)²

Do you see how this is different from your second inequality d - (r1+r2)^2 < y?

You can follow your gut or you can follow the rules of algebra, but one of them gives better answers. ;^)

rob mayoff
  • 375,296
  • 67
  • 796
  • 848
  • Ah... That wasn't quite clear at first but now I understand. The reason I saw the form d < (r1 + r2)^2 was because y was zero (it's only checking for collision, and not the actual range). I need to brush up on my algebra as this was driving me nuts! Thanks a lot! – Cleroth Aug 20 '14 at 22:17
0

Your for loop doesn't end when you find something within range. I think you want a break instead of continue. You should also have something for when the loop failed to find anything within range.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • It `continue`s when the distance is larger than `range_sq`. The `assert` check is to make sure both functions work the same way, which they don't. There is no need for a break as this should be ran for every `Unit` in range, as the name `ForEachRange` suggests. – Cleroth Aug 20 '14 at 22:03
  • @ClerothSun but in this case the `continue` doesn't do anything, the code would work just the same if it wasn't there. So I'm confused. – Mark Ransom Aug 20 '14 at 23:39
  • It skips the `assert` and the `func` call. I'm not sure what you're seeing here. – Cleroth Aug 21 '14 at 00:39
  • @ClerothSun, sorry, your bracketing/indentation is not what I'm used to, and the final bracket was scrolled off the page. I totally misread the code. And I would have coded it with an `else` instead. – Mark Ransom Aug 21 '14 at 01:45