1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fastest way to determine if a circle fully covers a rectangle

  1. Sep 30, 2011 #1
    As usual I'm working on a program and I'm having trouble with math/efficiency.

    1. The problem statement, all variables and given/known data
    I need a way to find out if a circle given as a point and a radius C(x,y,r) fully encloses a rectangle given by the top left corner and the width and height R(x,y,w,h)

    I only need to know IF it fully covers the rectangle and not any of the areas.





    2. The attempt at a solution
    The only solution I can think of is simple but not fast:
    1) get all points of the rectangle (xi,yi) i from 1-4
    2) for every i check if (cx-xi)2+(cy-xi)2 <= cr2
    3) if any of the checks in 2 are false it is not covered by the circle otherwise it does

    I am sure that this solution will work, but I'm hoping there may be a faster way to do it. Is this the best (most efficient) solution or is there a better one?
     
  2. jcsd
  3. Sep 30, 2011 #2
    I think you misunderstood the question. I attached a picture to make it clear, I need to know which rectangles are enclosed by the circle, in the image C and D. I'm trying to find faster way than checking if all four points are in the circle to determine if the rectangle is.
     

    Attached Files:

  4. Sep 30, 2011 #3

    olivermsun

    User Avatar
    Science Advisor

    I think that's about as "efficient" in simplicity of algorithm as you can make it.

    If you know more information, you may be able to make it more computationally efficient. For example, if the circle is relatively small compared to the domain and you have many rectangles to check, it might work out to be faster to find the maximum x, y coordinates of the circle (essentially, approximate the circle with a square) and reject rectangles whose origin point is outside those bounds (you might even check all four points in this way).
     
    Last edited: Sep 30, 2011
  5. Sep 30, 2011 #4
    Thanks for the advice, perhaps more information could help.

    I'm building a region quad-tree based image like the one in http://donar.umiacs.umd.edu/quadtree/regions/regionquad.html" [Broken]. I have generalized it slightly, and I want to add a circle drawing function.

    I'm just trying to figure out a good algorithm to use to draw a circle into a quad-tree image, and checking if the current node is covered by the circle is a key component and I wanted to make sure it was as fast as i could get it.

    I tend to oversimplify the problem I'm having when asking questions on forums.
     
    Last edited by a moderator: May 5, 2017
  6. Oct 19, 2012 #5
    1.
    Find the farthest point on the rectangle from the circle center point.
    It's quite easy because the rectangle is axis-parallel.

    2.
    Test the point in the circle.

    Code (Text):

    double xFarthest;
    if abs(center.x - rect.left) < abs(center.x - rect.right)
       xFarthest = rect.right;
    else
       xFarthest = rect.left;

    double yFarthest;
    if abs(center.y - rect.bottom) < abs(center.y - rect.top)
       yFarthest = rect.top;
    else
       yFarthest = rect.bottom;

    double dx = center.x - xFarthest;
    double dy = center.y - yFarthest;
    return ((dx * dx - dy * dy) <= r * r);
     
    I don't know this method is faster.
    But if abs function is faster than multiplication operator, it could be faster.
     
    Last edited: Oct 19, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fastest way to determine if a circle fully covers a rectangle
Loading...