how to find the minimum covering radius for a set of scattered points
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 15

Thread: how to find the minimum covering radius for a set of scattered points

  1. #1
    Join Date
    Jun 2004
    Location
    Holland
    Posts
    25

    how to find the minimum covering radius for a set of scattered points

    anyone can recommend any tool to do that?

    thanks a lot
    Tao does nothing but there is nothing Tao does not do.

  2. #2
    Join Date
    Mar 2004
    Location
    Temuco, CHILE
    Posts
    161

    Re: how to find the minimum covering radius for a set of scattered points

    Hi there:

    Im not sure but this post should go to Data Structures & Algorithms?

    Anyway, a bound for this problem is to find the two farest points of the set. That is, the two points that are the most separated. Taking half that distance determines the radius of a circle that covers these two points and therefore any other point in the set -- as any other point is nearer --.

    The rationale for this is that if exists another point that is outside this circle, its distance to at least one of the points determining the circle would be greater than the 2*radius and then you could use that distance [new point, old point] to determine a new radius, and then a new circle that covers the original points plus the new one.

    I hope this works, or at elast can give you a starting point.
    You're not watching "24"?
    Well... you should.

    24
    Jack IS back...

  3. #3
    Join Date
    Sep 2004
    Posts
    519

    Re: how to find the minimum covering radius for a set of scattered points

    I might show my stupidity here but are you sure about this:

    Anyway, a bound for this problem is to find the two farest points of the set. That is, the two points that are the most separated. Taking half that distance determines the radius of a circle that covers these two points and therefore any other point in the set -- as any other point is nearer --.
    Consider these three points: (-1, 0), (1, 0), (0, 1.1)
    The two most seperated points should be (-1,0) and (1,0) the distance being 2.
    According to the reasoning above the the radius of the circle should be 1. There is only one such circle that encloses (-1,0), (1,0) and that is the unit circle centered around origo. But (0,1.1) is outside the unit circle.

    Like I said I may just be stupid.

    An upper bound that would work in my eyes is radius of circle is the distance between the two most seperated point (same as your reasoning above except that no divide by 2). The circle is centered around one of the two most seperated points.

    A trivial algorithm for finding a slightly better circle could be to traverse over the points randomly (as it feels like the ordering matters). When you pick a point you create new bounding circle that encloses both the point and previous bounding circle.

    A slightly more advanced algorithm could be to use a modified A-* tree.

    But I'm just guessing here. I'm sure lot of game developers out there are much more comfortable with using bounding circles/spheres than I am.

  4. #4
    Join Date
    Apr 1999
    Location
    Altrincham, England
    Posts
    4,471

    Re: how to find the minimum covering radius for a set of scattered points

    Simplex algorithm should do the trick.

    You just need to minimise the function f(x, y), where f = the maximum distance from the point (x, y) to one of the points in the set (i.e. the radius of a circle centred at (x,y) that will cover all the points).
    Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
    --
    Sutter and Alexandrescu, C++ Coding Standards

    Programs must be written for people to read, and only incidentally for machines to execute.

    --
    Harold Abelson and Gerald Jay Sussman

    The cheapest, fastest and most reliable components of a computer system are those that aren't there.
    -- Gordon Bell


  5. #5
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,062

    Re: how to find the minimum covering radius for a set of scattered points

    To find the smallest circle enclosing some points, try something like the following:
    Code:
          int iXSum = 0;
          int iYSum = 0;
          for (vector<POINT>::const_iterator citer = points.begin();
            citer != points.end(); ++citer)
          {
            iXSum += (*citer).x;
            iYSum += (*citer).y;
          }
          center.x = int(double(iXSum)/double(points.size())+0.5);
          center.y = int(double(iYSum)/double(points.size())+0.5);
    
          radius = INT_MIN;
          for (vector<POINT>::const_iterator citer = points.begin();
            citer != points.end(); ++citer)
          {
            int iRadius = ceil(sqrt(pow(double(center.x-(*citer).x), 2.0) +
              pow(double(center.y-(*citer).y), 2.0)) + 0.5);
            if (iRadius > radius)
              radius = iRadius;
          }
    center will contain the coordinates of the center of the circle and radius contains the radius.

  6. #6
    Join Date
    Nov 2003
    Posts
    1,405

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by marten_range
    I might show my stupidity here but are you sure about this:
    I may be stupid too but don't you just have to first find the bounding rectangle (the smallest rectangle that contains all points)? The diagonal of this rectangle will be the diameter of the smallest covering circle.

    To find the bounding rectangle is easy. Just find the minimum and maximum x and y coordinates. The diagonal is then the line from (x_min, y_min) to (x_max, y_max). The length of this line is sqrt((y_max - y_min)^2 + (x_max - x_min)^2). This is also the diameter of the covering circle. Half it and you get the radius.

    The centre of the covering circle is placed in the middle of the bounding rectangle which is the mid-point of the diagonal line calculated above.
    Last edited by _uj; December 1st, 2004 at 11:21 AM.

  7. #7
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,062

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by _uj
    I may be stupid too but don't you just have to first find the bounding rectangle (the smallest rectangle that contains all points)? The diagonal of this rectangle will be the diameter of the smallest covering circle.

    To find the bounding rectangle is easy. Just find the minimum and maximum x and y coordinates. The diagonal is then the line from (x_min, y_min) to (x_max, y_max). The length of this line is sqrt((y_max - y_min)^2 + (x_max - x_min)^2). This is also the diameter of the covering circle. Half it and you get the radius.

    The centre of the covering circle is placed in the middle of the bounding rectangle which is the mid-point of the diagonal line calculated above.
    This isn't the smallest bounding circle. To see this, just draw 4 points in a cross-like manner and apply your algorithm to it.

  8. #8
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588

    Re: how to find the minimum covering radius for a set of scattered points

    Not only that but the center of the circle is not necessarily the same as the center of the bounding rectangle. Think about three points arranged like an L.

    So Simplex seems to be the best method yet.

    P.S. Marc, your solution doesn't work either. As an example, consider (-1,0), (0.9,0), (0.95,0), (1,0)

    [moved the post to Algorithms]
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  9. #9
    Join Date
    Nov 2002
    Location
    California
    Posts
    4,553

    Re: how to find the minimum covering radius for a set of scattered points

    This is actually a difficult problem, and is one special case of a general class of problems called "covering problems".

    One widely quoted solution was proposed by Elzinga and Hearn in 1972: D. Jack Elzinga, Donald W. Hearn, "Geometrical Solutions for some minimax location problems," Transportation Science, 6, (1972), pp 379 - 394.

    Here's a description of another algorithm from http://forums.wolfram.com/mathgroup/.../msg00486.html
    1) Take all pairs of points and calculate the minimal circle
    covering each pair. (The radius of such a circle is just half
    the distance between the pair of points, the center is the
    midpoint between them.)

    2) Take all triples of points and calculate the minimal circle
    covering each triple. (That is just the circum circle.)

    3) Throw away all circles which do not cover all points.

    4) From the remaining circles take the one with the minimal
    radius.

    This algorithm guarantees to give the correct result.
    The following site gives C source code which solves the problem in up to n-dimensional space: http://www2.inf.ethz.ch/personal/gaertner/miniball.html

    Mike

  10. #10
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,062

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by Yves M
    P.S. Marc, your solution doesn't work either. As an example, consider (-1,0), (0.9,0), (0.95,0), (1,0)
    Yes you're right. My solution generates a bounding circle but not minimal...
    Maybe an interesting working solution can be found at:
    WmlContMinCircle2.h
    WmlContMinCircle2.cpp

  11. #11
    Join Date
    Nov 2003
    Posts
    1,405

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by Marc G
    This isn't the smallest bounding circle. To see this, just draw 4 points in a cross-like manner and apply your algorithm to it.
    If you please would give me an example where my bounding circle wouldn't be minimal? You first define the bounding rectangle and then based on that the bounding circle. It seems logical to me but I am not a matematician. I would need a counter-example. Then I'll come up with something better.

  12. #12
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,062

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by Yves M
    P.S. Marc, your solution doesn't work either. As an example, consider (-1,0), (0.9,0), (0.95,0), (1,0)
    What about the following solution?
    Code:
          double dBiggestDistance = DBL_MIN;
          for (int i=0; i<g_points.size(); ++i)
          {
            for (int j=i+1; j<g_points.size(); ++j)
            {
              double distance = sqrt(pow(g_points[j].x-g_points[i].x, 2.0) +
                pow(g_points[j].y-g_points[i].y, 2.0));
              if (distance > dBiggestDistance)
              {
                dBiggestDistance = distance;
                g_radius = dBiggestDistance / 2.0;
                g_center.x = (g_points[j].x + g_points[i].x) / 2.0;
                g_center.y = (g_points[j].y + g_points[i].y) / 2.0;
              }
            }
          }
    Might not be the fastest way, but it certainly isn't slow either because of the way the second loop is written. It can be optimized a bit by calculating the g_center and g_radius after all the loops.

  13. #13
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,062

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by _uj
    If you please would give me an example where my bounding circle wouldn't be minimal? You first define the bounding rectangle and then based on that the bounding circle. It seems logical to me but I am not a matematician. I would need a counter-example. Then I'll come up with something better.
    Check the attached image.
    The blue crosses are the 4 points I was talking about. The red rectangle is the bounding rectangle. The circle is not the minimal circle.
    Attached Images Attached Images  

  14. #14
    Join Date
    Nov 2003
    Posts
    1,405

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by Marc G
    Check the attached image.
    The blue crosses are the 4 points I was talking about. The red rectangle is the bounding rectangle. The circle is not the minimal circle.
    Thank you very much for your effort. I really appreciate this. At least my circle seems to be the outer bound of any solution meaning my circle is guaranteed to be covering.

  15. #15
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: how to find the minimum covering radius for a set of scattered points

    Quote Originally Posted by MikeAThon
    Here's a description of another algorithm from http://forums.wolfram.com/mathgroup/.../msg00486.html
    May I add the step
    0) Replace the set with the convex hull of the set. (complexity: O(n*ln(n)) )
    It can lead to square rooting of number of points in common case and therefore the following n^3 finding the circle for tripples can become just n^1.5.
    Last edited by RoboTact; December 4th, 2004 at 11:41 PM.
    "Programs must be written for people to read, and only incidentally for machines to execute."

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center