Ask a question about algorithm

[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