Ask a question about algorithm

[specterzou]

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 ?

[nuzzle]

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.

[specterzou]

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.

[nuzzle]

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

[specterzou]

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

[nuzzle]

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.

[specterzou]

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.