Article directory
- Circle and Rectangle Overlapping Whether the circle and rectangle overlap
-
- Problem Description:
- analyze
- the code
-
- tag
Circle and Rectangle Overlapping Whether the circle and rectangle overlap
Description of problem:
Given a circle represented by (radius, xCenter, yCenter) and a rectangle parallel to the coordinate axes (
x
1
x_1
x1?,
the y
1
y_1
y1?,
x
2
x_2
x2?,
the y
2
y_2
y2?), where (
x
1
x_1
x1?,
the y
1
y_1
y1?) are the coordinates of the lower left corner of the rectangle, while (
x
2
x_2
x2?,
the y
2
y_2
y2?) are the coordinates of the upper right corner.
If the circle and the rectangle overlap, please return true , otherwise return false .
In other words, you check for the existence of a point (
x
i
x_i
xi?,
the y
i
y_i
yi?) , which is both on the circle and on the rectangle (both including the case where the point falls on the boundary).
**radius range[1,2000]**
xCenter, yCenter range[
?
1
0
4
-10^4
?104,
1
0
4
10^4
104]
x
1
x_1
x1?,
the y
1
y_1
y1?range[
?
1
0
4
-10^4
?104,
1
0
4
10^4
104]
x
2
x_2
x2?,
the y
2
y_2
y2?range[
?
1
0
4
-10^4
?104,
1
0
4
10^4
104]
Analysis
If you want to determine whether there is overlap, you need to find a point on the rectangle, and the distance from the center of the circle <= radius.
One way is to enumerate the points on the sides of the rectangle, including the vertices. Since the coordinates given in the condition are all ints, there are no decimals. Therefore, the coordinate points on each side can be enumerated, and the range of a side is [1,
2
?
1
0
4
2*10^4
2?104], if it is calculated for all four sides, it is also possible in theory.
But if the coordinates given in the condition are
d
o
u
b
l
e
double
double, this violent enumeration method cannot be handled. Because there are too many decimals between every 2 integers, it is impossible to enumerate.
In this method, there is no need to enumerate all the sides, and the relative position of the circle and the rectangle can be judged to determine which side to use for verification.
Thinking from another angle, it is still based on the assumption that the center of the circle coordinates O(
x
,
the y
x,y
x,y), while the lower left corner of the rectangle (
x
l
,
the y
l
xl,yl
xl, yl), upper right corner (
x
r
,
the y
r
xr,yr
xr, yr), then if the coordinate point p(
p
x
,
p
the y
px,py
px, py) in the rectangle must satisfy that px belongs to
[
x
l
,
x
r
]
[xl,xr]
[xl,xr] & &py belongs to
[
the y
l
,
the y
r
]
[yl,yr]
[yl,yr].
The distance between p and the center O is
d
i
the s
2
=
[
a
b
the s
(
p
x
?
x
)
]
2
+
[
a
b
the s
(
p
the y
?
the y
)
]
2
dis^2 = [abs(px-x)]^2 + [abs(py-y)]^2
dis2=[abs(px?x)]2 + [abs(py?y)]2. If
d
i
the s
t
2
<
=
r
a
d
i
u
the s
2
dist^2<=radius^2
dist2<=radius2, can exist, which means that the two must overlap.
So the problem becomes that the value q is in the interval
[
L
,
R
]
[L,R]
Find one in [L,R]
a
b
the s
(
q
?
x
)
abs(q-X)
The minimum value of abs(q?X).
Code
public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {<!-- -->
double dist = 0;
if (xCenter < x1 || xCenter > x2) {<!-- -->
dist + = Math.min(Math.pow(x1 - xCenter, 2), Math.pow(x2 - xCenter, 2));
}
if (yCenter < y1 || yCenter > y2) {<!-- -->
dist + = Math.min(Math.pow(y1 - yCenter, 2), Math.pow(y2 - yCenter, 2));
}
return dist <= radius * radius;
}
Time complexity
o
(
1
)
O(1)
O(1)
Space Complexity
o
(
1
)
O(1)
O(1)
Tag
Math
Geometry