Circle intersection


  • 0
    A

    Given 'n' circles (each defined by center and radius)

    Write an algorithm to detect if given circles intersect with any other circles in the same plane

    Looking for better than O(n^2) complexity


  • 0
    T

    Not sure my solution is correct, but I think it is better than O(n^2) because it has early break.

    idea is to according to X and R to build interval parallel X-axis, and check if cross intersect then verify whether this two circle is intersection : (x1-x2) ^2 + (y1-y2)^2 <= (r1+r2)^2

    /*
    
        public class Circle {
            public int x;
            public int y;
            public int r;
            public int start;
            public int end;
        }
             arrs[i,0] => X;
             arrs[i,1] => Y;
             arrs[i,2] => R 
                 */
            public bool validate(int[,] arrs) {
                int rows = arrs.GetLength(0);
                List<Circle> list = new List<Circle>();
                for (int i = 0; i < rows; i++) {
                    list.Add(new Circle() { x = arrs[i, 0], y = arrs[i, 1], r = arrs[i, 2],start = arrs[i, 0] - arrs[i, 2], end = arrs[i, 0] + arrs[i, 2] });
                }
    
                var orderByStart = list.OrderBy(x => x.x - x.r).ToList();
                var orderByEnd = list.OrderBy(x => x.x + x.r).ToList();
    
                int index = 0;
    
                for (int i = 0; i < rows; i++)
                {
                    for (int j = index; j < rows; j++)
                    {
                        if (orderByStart[i].start > orderByEnd[j].end)
                        {
                            index++;
                        }
                        else if (orderByStart[i].end < orderByEnd[j].start)
                        {
                            break;
                        }
                        else if (Math.Pow(Math.Abs(orderByStart[i].x - orderByEnd[j].x), 2) 
                            + Math.Pow(Math.Abs(orderByStart[i].y - orderByEnd[j].y), 2) <= Math.Pow(Math.Abs(orderByStart[i].r - orderByEnd[j].r), 2))
                        {
                            return true;
                        }
                    }
                }
                return false;
            }
    

  • 0
    A

    @tangalai Thanks. Sorry I wasn't more precise earlier.

    For every given circle we need to find if it intersects with other circles in the same plane

    I presented a similar idea based on line-sweep algorithm but the interviewer wasn't satisfied as the worst case would still be O(n^2) .

    ex: circle 1 => (0,0,5)
    circle 2 => (1,20,1)
    circle 3 => (1,15,1)
    circle 4 => (1,10,2)
    circle 5 => (1,9,1)

       circle 4 and circle 5 would intersect but it'll be O(n^2)

  • 0
    T

    @andrey42 yup, you are right, the worst case still O(n^2)


  • 1
    A

    How about distance between two points formula? In this case two points would be centers of any two given circles and if that distance is less than sum of their radius, they would intersect. But I guess this would be O(n^2) as well.


  • 0
    G

    @agrawalm said in Circle intersection:

    How about distance between two points formula? In this case two points would be centers of any two given circles and if that distance is less than sum of their radius, they would intersect. But I guess this would be O(n^2) as well.

    My thoughts exactly. On a different note though, if we want to check that just one such pair exists, we could break prematurely. Also, we would absolutely have to check all circles, with all other circles, and the worst case is n^2


  • 3
    Y

    2 circles intersect if:

    def intersect(r1, r2, c1, c2):
        return r1 + r2 >= dist(c1, c2)
    

    convert all the circles as points of (startX,startY) and (endX, endY). Now look at this problem as interval scheduling problem. Take a greedy approach. start off my sorting with starting X and consider all the interesting of endI and startJ. Now for all intersection call intersect function if intersect return true then return True and end the computation


  • 1
    G

    Can you please elaborate as to what are the values of (startx,starty) (endx,endy).


  • 0
    H

    I think O(nlogn) solution exists and it uses line sweep algorithm. In the following link shows implementation of finding the closest two pair in list of pairs. Finding closest part can be easily converted into circle intersection.

    https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.