CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Feb 2010
    Posts
    13

    Question Ask a question about algorithm

    In the Cartesian coordinate system,, there is a circle and rectangle, when the circumstances under which a circle and rectangle intersection region has the largest number of integer coordinates which refers to the X-axis, Y axis is an integer ?

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Ask a question about algorithm

    Do you want to overlap a rectangle with a circle in such a way that the overlap shape contains as many integer points as possible?

    Well, I don't know how to do that but I can try something as a start.

    The rectangle is simple. If you put one of its corners on an integer point it will contain the maximum number of integer points.

    If you put the middle of a circle on an integer point it will contain a certain number of integer points. Now if you slowly move the circle to another integer point the number of integer points it contains will vary with position. But one thing is for sure. When it arrives at the new integer point the number of integer points it contains will be the same as it was at the old integer point.

    Now my hunch is that the variation of integer points within a circle when you move it from one integer point to another will be at maximum halfway between integer points. Not only exactly there necessarily, but there too. At least this is the case when you move a line segment along the x-axis. If you put the middle of the line segment on integer points it will cover the same number of integers. If you put it halfway between integer points it will manifest its largest variation in coverage. So I just assume the circle behaves the same.

    If my assumption is correct you first place the rectangle with a corner at an integer point. Then you place the middle of the circle on all integer points and half integer points within the rectangle including the borders and check which one gives the overlap shape with the biggest number of integer points in it.

  3. #3
    Join Date
    Feb 2010
    Posts
    13

    Re: Ask a question about algorithm

    Quote Originally Posted by nuzzle View Post
    Do you want to overlap a rectangle with a circle in such a way that the overlap shape contains as many integer points as possible?

    Well, I don't know how to do that but I can try something as a start.

    The rectangle is simple. If you put one of its corners on an integer point it will contain the maximum number of integer points.

    If you put the middle of a circle on an integer point it will contain a certain number of integer points. Now if you slowly move the circle to another integer point the number of integer points it contains will vary with position. But one thing is for sure. When it arrives at the new integer point the number of integer points it contains will be the same as it was at the old integer point.

    Now my hunch is that the variation of integer points within a circle when you move it from one integer point to another will be at maximum halfway between integer points. Not only exactly there necessarily, but there too. At least this is the case when you move a line segment along the x-axis. If you put the middle of the line segment on integer points it will cover the same number of integers. If you put it halfway between integer points it will manifest its largest variation in coverage. So I just assume the circle behaves the same.

    If my assumption is correct you first place the rectangle with a corner at an integer point. Then you place the middle of the circle on all integer points and half integer points within the rectangle including the borders and check which one gives the overlap shape with the biggest number of integer points in it.

    Thank you very much, your idea may be correct , and i will try to prove it.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Ask a question about algorithm

    Good luck. I get the feeling it may be a known problem with a name and a solution.

  5. #5
    Join Date
    Feb 2010
    Posts
    13

    Re: Ask a question about algorithm

    Quote Originally Posted by nuzzle View Post
    Good luck. I get the feeling it may be a known problem with a name and a solution.
    This is my program on the basis of your idea.

    public class MaxIntersection {
    private final double LENGTH = 2;// the length of the rectangle

    private final double WIDTH = 3;// the width of the rectangle

    private final double R = 3;// the radius of the circle

    // position
    class Point {
    double x;

    double y;

    public Point(double x, double y) {
    this.x = x;
    this.y = y;
    }
    }

    // one of the rectanle's corners
    private final Point recVertex = new Point(0, 0);

    public boolean isInRec(Point point) {
    if (point.x >= recVertex.x && point.x <= recVertex.x + LENGTH
    && point.y >= recVertex.y && point.y <= recVertex.y + WIDTH)
    return true;
    else
    return false;
    }

    public boolean isInCircle(Point point, Point center) {
    double x = (point.x - center.x) * (point.x - center.x);
    double y = (point.y - center.y) * (point.y - center.y);

    if (x + y <= R * R)
    return true;
    else
    return false;
    }

    public int getMaxIntersection() {
    int max = 0;
    // the center of a circle which has the maximum number of integer points
    Point c = null;
    for (double cx = recVertex.x; cx <= recVertex.x + LENGTH; cx += 0.5)
    for (double cy = recVertex.y; cy <= recVertex.y + WIDTH; cy += 0.5) {
    int temp = 0;
    // the temporary center of a circle
    Point tc = new Point(cx, cy);
    for (int x = Double.valueOf(cx - R).intValue(); x <= cx + R; x++)
    for (int y = Double.valueOf(cy - R).intValue(); y <= cy + R; y++) {
    Point p = new Point(x, y);
    if (isInCircle(p, tc) && isInRec(p))
    ++temp;
    }
    if (temp > max) {
    max = temp;
    c = tc;
    }
    }
    if (c != null)
    // print the center of a circle
    System.out.println("(" + c.x + "," + c.y + ")");

    return max;
    }

    public static void main(String[] args) {
    MaxIntersection MI = new MaxIntersection();
    // print the maximum number of integer points
    System.out.println(MI.getMaxIntersection());
    }
    }

    //(0.0,1.0)
    //12

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: Ask a question about algorithm

    Well, does it seem to work?

    Note that incrementing a floating point in a loop like this,

    for (double cx = recVertex.x; cx <= recVertex.x + LENGTH; cx += 0.5)

    generally should be avoided because small conversion errors tend to be magnified as looping proceeds. It may not cause any harm in this case because the increment 0.5 can be exactly represented in binary but still it's safer to avoid it.
    Last edited by nuzzle; February 12th, 2010 at 11:13 AM.

  7. #7
    Join Date
    Feb 2010
    Posts
    13

    Re: Ask a question about algorithm

    Quote Originally Posted by nuzzle View Post
    Well, does it seem to work?

    Note that incrementing a floating point in a loop like this,

    for (double cx = recVertex.x; cx <= recVertex.x + LENGTH; cx += 0.5)

    generally should be avoided because small conversion errors tend to be magnified as looping proceeds. It may not cause any harm in this case because the increment 0.5 can be exactly represented in binary but still it's safer to avoid it.
    Thank you very much,it seems to work well.

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured