点圆关系
点圆关系
问题描述
点圆关系处理平面上点与圆之间的基本关系，包括点到圆的距离、点在圆内外的判断等。常用于范围查询和碰撞检测问题。
基本操作
算法思想
- 使用圆心和半径表示圆
- 基于距离进行判断
- 适用于范围和位置判断
- 时间复杂度
代码实现
class Circle {
public:
Point center;
double radius;
Circle(Point c = Point(), double r = 0) : center(c), radius(r) {}
// 判断点在圆内
bool contains(const Point& p) const {
return center.distance(p) <= radius + EPS;
}
// 判断点在圆上
bool onCircle(const Point& p) const {
return abs(center.distance(p) - radius) < EPS;
}
// 点到圆的最短距离
double distanceToPoint(const Point& p) const {
double d = center.distance(p);
return max(0.0, d - radius);
}
// 计算圆的面积
double area() const {
return M_PI * radius * radius;
}
// 计算圆的周长
double perimeter() const {
return 2 * M_PI * radius;
}
};
class Circle {
Point center;
double radius;
static final double EPS = 1e-10;
static final double PI = Math.PI;
Circle(Point c, double r) {
this.center = c;
this.radius = r;
}
// 判断点在圆内
boolean contains(Point p) {
return center.distance(p) <= radius + EPS;
}
// 判断点在圆上
boolean onCircle(Point p) {
return Math.abs(center.distance(p) - radius) < EPS;
}
// 点到圆的最短距离
double distanceToPoint(Point p) {
double d = center.distance(p);
return Math.max(0.0, d - radius);
}
// 计算圆的面积
double area() {
return PI * radius * radius;
}
// 计算圆的周长
double perimeter() {
return 2 * PI * radius;
}
}
class Circle:
def __init__(self, center: Point = Point(), radius: float = 0):
self.center = center
self.radius = radius
self.EPS = 1e-10
self.PI = math.pi
# 判断点在圆内
def contains(self, p: Point) -> bool:
return self.center.distance(p) <= self.radius + self.EPS
# 判断点在圆上
def on_circle(self, p: Point) -> bool:
return abs(self.center.distance(p) - self.radius) < self.EPS
# 点到圆的最短距离
def distance_to_point(self, p: Point) -> float:
d = self.center.distance(p)
return max(0.0, d - self.radius)
# 计算圆的面积
def area(self) -> float:
return self.PI * self.radius * self.radius
# 计算圆的周长
def perimeter(self) -> float:
return 2 * self.PI * self.radius
时间复杂度分析
| 点在圆内判断 | ||
| 点在圆上判断 | ||
| 点到圆距离 | ||
| 面积周长计算 |
应用场景
- 范围查询
- 碰撞检测
- 区域判断
- 面积计算
- 几何构造
注意事项
- 浮点数精度
- 边界情况
- 特殊情况
- 坐标范围
- 数值稳定性
常见变形
- 圆与点集
class Solution {
public:
// 找出圆内的所有点
vector<Point> pointsInCircle(const Circle& circle,
const vector<Point>& points) {
vector<Point> result;
for (const Point& p : points) {
if (circle.contains(p)) {
result.push_back(p);
}
}
return result;
}
// 找出离圆最近的k个点
vector<Point> nearestKPoints(const Circle& circle,
const vector<Point>& points,
int k) {
vector<pair<double, Point>> distances;
for (const Point& p : points) {
distances.emplace_back(circle.distanceToPoint(p), p);
}
partial_sort(distances.begin(),
distances.begin() + k,
distances.end());
vector<Point> result;
for (int i = 0; i < k && i < distances.size(); i++) {
result.push_back(distances[i].second);
}
return result;
}
};
class Solution {
// 找出圆内的所有点
public List<Point> pointsInCircle(Circle circle, Point[] points) {
List<Point> result = new ArrayList<>();
for (Point p : points) {
if (circle.contains(p)) {
result.add(p);
}
}
return result;
}
// 找出离圆最近的k个点
public List<Point> nearestKPoints(Circle circle, Point[] points, int k) {
PriorityQueue<Point> pq = new PriorityQueue<>(
(a, b) -> Double.compare(
circle.distanceToPoint(a),
circle.distanceToPoint(b)
)
);
for (Point p : points) {
pq.offer(p);
}
List<Point> result = new ArrayList<>();
for (int i = 0; i < k && !pq.isEmpty(); i++) {
result.add(pq.poll());
}
return result;
}
}
class Solution:
# 找出圆内的所有点
def points_in_circle(self, circle: Circle,
points: List[Point]) -> List[Point]:
return [p for p in points if circle.contains(p)]
# 找出离圆最近的k个点
def nearest_k_points(self, circle: Circle,
points: List[Point], k: int) -> List[Point]:
return sorted(points,
key=lambda p: circle.distance_to_point(p))[:k]
- 最小圆覆盖
class Solution {
public:
// 计算包含所有点的最小圆
Circle minCircleCover(vector<Point>& points) {
if (points.empty()) return Circle();
if (points.size() == 1) return Circle(points[0], 0);
// 随机打乱点的顺序
random_shuffle(points.begin(), points.end());
Circle circle(points[0], 0);
for (int i = 1; i < points.size(); i++) {
if (!circle.contains(points[i])) {
circle = Circle(points[i], 0);
for (int j = 0; j < i; j++) {
if (!circle.contains(points[j])) {
circle = makeCircleFromTwo(points[i], points[j]);
for (int k = 0; k < j; k++) {
if (!circle.contains(points[k])) {
circle = makeCircleFromThree(
points[i], points[j], points[k]
);
}
}
}
}
}
}
return circle;
}
private:
Circle makeCircleFromTwo(const Point& p1, const Point& p2) {
Point center((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
return Circle(center, center.distance(p1));
}
Circle makeCircleFromThree(const Point& p1, const Point& p2,
const Point& p3) {
// 三点确定一个圆
double a = p2.x - p1.x, b = p2.y - p1.y,
c = p3.x - p1.x, d = p3.y - p1.y;
double e = a * (p1.x + p2.x) + b * (p1.y + p2.y);
double f = c * (p1.x + p3.x) + d * (p1.y + p3.y);
double g = 2 * (a * (p3.y - p2.y) - b * (p3.x - p2.x));
if (abs(g) < EPS) return Circle();
Point center(
(d * e - b * f) / g,
(a * f - c * e) / g
);
return Circle(center, center.distance(p1));
}
};
class Solution {
// 计算包含所有点的最小圆
public Circle minCircleCover(Point[] points) {
if (points.length == 0) return new Circle(new Point(), 0);
if (points.length == 1) return new Circle(points[0], 0);
// 随机打乱点的顺序
List<Point> list = Arrays.asList(points);
Collections.shuffle(list);
points = list.toArray(new Point[0]);
Circle circle = new Circle(points[0], 0);
for (int i = 1; i < points.length; i++) {
if (!circle.contains(points[i])) {
circle = new Circle(points[i], 0);
for (int j = 0; j < i; j++) {
if (!circle.contains(points[j])) {
circle = makeCircleFromTwo(points[i], points[j]);
for (int k = 0; k < j; k++) {
if (!circle.contains(points[k])) {
circle = makeCircleFromThree(
points[i], points[j], points[k]
);
}
}
}
}
}
}
return circle;
}
private Circle makeCircleFromTwo(Point p1, Point p2) {
Point center = new Point(
(p1.x + p2.x) / 2,
(p1.y + p2.y) / 2
);
return new Circle(center, center.distance(p1));
}
private Circle makeCircleFromThree(Point p1, Point p2, Point p3) {
// 三点确定一个圆
double a = p2.x - p1.x, b = p2.y - p1.y,
c = p3.x - p1.x, d = p3.y - p1.y;
double e = a * (p1.x + p2.x) + b * (p1.y + p2.y);
double f = c * (p1.x + p3.x) + d * (p1.y + p3.y);
double g = 2 * (a * (p3.y - p2.y) - b * (p3.x - p2.x));
if (Math.abs(g) < EPS) return new Circle(new Point(), 0);
Point center = new Point(
(d * e - b * f) / g,
(a * f - c * e) / g
);
return new Circle(center, center.distance(p1));
}
}
class Solution:
# 计算包含所有点的最小圆
def min_circle_cover(self, points: List[Point]) -> Circle:
if not points:
return Circle()
if len(points) == 1:
return Circle(points[0], 0)
# 随机打乱点的顺序
random.shuffle(points)
circle = Circle(points[0], 0)
for i in range(1, len(points)):
if not circle.contains(points[i]):
circle = Circle(points[i], 0)
for j in range(i):
if not circle.contains(points[j]):
circle = self.make_circle_from_two(
points[i], points[j]
)
for k in range(j):
if not circle.contains(points[k]):
circle = self.make_circle_from_three(
points[i], points[j], points[k]
)
return circle
def make_circle_from_two(self, p1: Point, p2: Point) -> Circle:
center = Point(
(p1.x + p2.x) / 2,
(p1.y + p2.y) / 2
)
return Circle(center, center.distance(p1))
def make_circle_from_three(self, p1: Point, p2: Point,
p3: Point) -> Circle:
# 三点确定一个圆
a = p2.x - p1.x
b = p2.y - p1.y
c = p3.x - p1.x
d = p3.y - p1.y
e = a * (p1.x + p2.x) + b * (p1.y + p2.y)
f = c * (p1.x + p3.x) + d * (p1.y + p3.y)
g = 2 * (a * (p3.y - p2.y) - b * (p3.x - p2.x))
if abs(g) < self.EPS:
return Circle()
center = Point(
(d * e - b * f) / g,
(a * f - c * e) / g
)
return Circle(center, center.distance(p1))
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
查看7道真题和解析
