whether circles intersect or not

Question

I have a matrix, which looks like this:

0 0 1
0 0 2
0 2 1.5

which means (X, Y, R) of the circle (first it's circle's center, second it's radius)

this matrix is dynamically created, so it can have all sizes you wish, just enter it's one.

I need to find out whether these circles intersect or not, I'm doing it like this:

 for( int i = 0; i < n; i++ ) {
    dis_x = fabs(*(matrix + (i+1) * 3 + 0) - *(matrix + i * 3 + 0));
    dis_y = fabs(*(matrix + (i+1) * 3 + 1) - *(matrix + i * 3 + 1));
    hypotenuse = sqrt( pow(dis_x,2) + pow(dis_y,2) );

    radius_i = *(matrix + i * 3 + 2);
    radius_i_plus_1 = *(matrix + (i+1) * 3 + 2);

    sum_of_radius = radius_i_plus_1 + radius_i;

    if( sum_of_radius >= hypotenuse && hypotenuse != 0) {
        *(array_of_numbers_of_circles + i * 2 + 0) = i + 1;
        *(array_of_numbers_of_circles + i * 2 + 1) = i + 2;
    }

}

if I take the example above, I will see: 2 3

but I need:

1 3
2 3

in other words I need to compare ALL elements even first with last (if the size is 3) and all elements : the second with the forth (if the size is 4+)

thank you in advance!

Answer 1

count = 0;
for( int i = 0; i < n-1; i++ ) {
  for( int j= i + 1;  j < n ; j++) {
    dis_x = *(matrix + j * 3 + 0) - *(matrix + i * 3 + 0); // no need for fabs
    dis_y = *(matrix + j * 3 + 1) - *(matrix + i * 3 + 1);

    // use squared form, use multiplication rather than pow
    hypSquared = dis_x * dis_x + dis_y * dis_y; 

    radius_i = *(matrix + i * 3 + 2);
    radius_j = *(matrix + j * 3 + 2);

    sum_of_radius = radius_i + radius_j;
    diff_of_radius = radius_i - radius_j;
    // compare square of radius to the square of hyp. Eliminates call to sqrt()
    if( sum_of_radius * sum_of_radius >= hypSquared
     && diff_of_radius * diff_of_radius < hypSquared  ) {
        *(array_of_numbers_of_circles + count * 2 + 0) = i + 1;
        *(array_of_numbers_of_circles + count * 2 + 1) = j + 2;
        ++count;
    }

}

Answer 2

How about this:

struct circle
{
    double x, y, r;
    bool empty() { return x==0.0 && y==0.0 && r==0.0; }
};

circle matrix[] = {
    {0, 0, 1},
    {0, 0, 2},
    {0, 2, 1.5},
    {0,0,0}  // end marker
};

bool intersect(circle &c1, circle &c2)
{
    double dx = c2.x - c1.x;
    double dy = c2.y - c1.y;
    double dist = sqrt(dx*dx + dy*dy);
    double sumRad = c2.r + c1.r;
    bool yes = false;
    if (sumRad >= dist)
    {
        double minR = c1.r;
        double maxR = c2.r;
        if (minR > maxR) std::swap(minR, maxR);
        if (dist + minR >= maxR || (dist == 0.0 && minR == maxR))
            yes = true;
    }
    return yes;
}

void test()
{
    std::vector<std::pair<int, int>> result;
    for (int i=0; !matrix[i].empty(); i++)
        for (int j=i+1; !matrix[j].empty(); j++)
            if (intersect(matrix[i], matrix[j]))
                result.push_back(std::pair<int, int>(i+1,j+1));

    for (int i =0; i < result.size(); i++)
        printf("%d %d\n", result[i].first, result[i].second);
}

Output of executing test() is:

1 3
2 3

Answer 3

I'd be inclined to approach it like this. The first thing is to create a Circle class

class Circle 
{
public:
    friend std::ostream &operator<<(std::ostream &out, const Circle &c) 
        { return out << '(' << c.x << ", " << c.y << ", " << c.r << ')'; };
    friend std::istream &operator>>(std::istream &in, Circle &c) 
        { return in >> c.x >> c.y >> c.r; };
    bool intersects(const Circle &c2) const;
private:
    float x, y, r;
};

bool Circle::intersects(const Circle &c2) const
{
    float dist_squared = (x-c2.x)*(x-c2.x)+(y-c2.y)*(y-c2.y);
    if ((r-c2.r)*(r-c2.r) > dist_squared)
        return false;
    return (r+c2.r)*(r+c2.r) >= dist_squared;
}

Note that this class includes its own stream inserter and extractor and a member function intersects which tells whether any two Circle class instances intersect. Obviously, all error checking is omitted here, but it gives the essence of the technique.

I show how to use it in a complete program below. This program uses C++ 2011 features which make it quite compact, but they're not essential to using the Circle class.

#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>

//  the above Circle code would go here...

int main()
{
    std::ifstream in("circles.txt");
    std::vector<Circle> circles;

    std::copy(std::istream_iterator<Circle>(in), 
        std::istream_iterator<Circle>(), 
        std::back_inserter(circles));

    for (auto i : circles)
        for (auto j : circles)
            if (i.intersects(j))
                std::cout << i << " intersects " << j << std::endl;
    return 0;
}

If the file circles.txt is a text file containing exactly the input given:

0 0 1
0 0 2
0 2 1.5

the output is:

(0, 0, 1) intersects (0, 0, 1)
(0, 0, 1) intersects (0, 2, 1.5)
(0, 0, 2) intersects (0, 0, 2)
(0, 0, 2) intersects (0, 2, 1.5)
(0, 2, 1.5) intersects (0, 0, 1)
(0, 2, 1.5) intersects (0, 0, 2)
(0, 2, 1.5) intersects (0, 2, 1.5)

Note that this version reports that each circle intersects with itself. Technically true, but probably not very useful! The driver code could, of course, be rewritten without C++11 features and to give some alternate form of output. One way to do that would be to substitute this code for the nested for loops in the code above:

for (int i = 0; i < circles.size(); ++i)
    for (int j = i+1; j < circles.size(); ++j)
        if (circles[i].intersects(circles[j]))
            std::cout << i+1 << " " << j+1 << std::endl;

Doing so yields the following output:

1 3
2 3