11.02_点线关系
点线关系
问题描述
点线关系处理平面上点与直线/线段之间的基本关系，包括点到线的距离、点在线的位置等。常用于几何判定和距离计算问题。
基本操作
算法思想
- 使用向量表示直线方向
- 基于叉积判断方向
- 适用于位置和距离计算
- 时间复杂度
代码实现
class Line {
public:
Point p1, p2; // 直线上两点
Line(Point p1 = Point(), Point p2 = Point()) : p1(p1), p2(p2) {}
// 点到直线距离
double distanceToLine(const Point& p) const {
return abs((p2 - p1).cross(p - p1)) / p1.distance(p2);
}
// 点到线段距离
double distanceToSegment(const Point& p) const {
if (p2 - p1).dot(p - p1) <= 0) return p1.distance(p);
if ((p1 - p2).dot(p - p2) <= 0) return p2.distance(p);
return distanceToLine(p);
}
// 判断点在直线上
bool onLine(const Point& p) const {
return abs((p2 - p1).cross(p - p1)) < EPS;
}
// 判断点在线段上
bool onSegment(const Point& p) const {
return onLine(p) &&
p.x >= min(p1.x, p2.x) && p.x <= max(p1.x, p2.x) &&
p.y >= min(p1.y, p2.y) && p.y <= max(p1.y, p2.y);
}
};
class Line {
Point p1, p2; // 直线上两点
static final double EPS = 1e-10;
Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
// 点到直线距离
double distanceToLine(Point p) {
return Math.abs(p2.subtract(p1).cross(p.subtract(p1))) / p1.distance(p2);
}
// 点到线段距离
double distanceToSegment(Point p) {
if (p2.subtract(p1).dot(p.subtract(p1)) <= 0) return p1.distance(p);
if (p1.subtract(p2).dot(p.subtract(p2)) <= 0) return p2.distance(p);
return distanceToLine(p);
}
// 判断点在直线上
boolean onLine(Point p) {
return Math.abs(p2.subtract(p1).cross(p.subtract(p1))) < EPS;
}
// 判断点在线段上
boolean onSegment(Point p) {
return onLine(p) &&
p.x >= Math.min(p1.x, p2.x) && p.x <= Math.max(p1.x, p2.x) &&
p.y >= Math.min(p1.y, p2.y) && p.y <= Math.max(p1.y, p2.y);
}
}
class Line:
def __init__(self, p1: Point = Point(), p2: Point = Point()):
self.p1 = p1
self.p2 = p2
self.EPS = 1e-10
# 点到直线距离
def distance_to_line(self, p: Point) -> float:
return abs((self.p2 - self.p1).cross(p - self.p1)) / self.p1.distance(self.p2)
# 点到线段距离
def distance_to_segment(self, p: Point) -> float:
if (self.p2 - self.p1).dot(p - self.p1) <= 0:
return self.p1.distance(p)
if (self.p1 - self.p2).dot(p - self.p2) <= 0:
return self.p2.distance(p)
return self.distance_to_line(p)
# 判断点在直线上
def on_line(self, p: Point) -> bool:
return abs((self.p2 - self.p1).cross(p - self.p1)) < self.EPS
# 判断点在线段上
def on_segment(self, p: Point) -> bool:
return (self.on_line(p) and
min(self.p1.x, self.p2.x) <= p.x <= max(self.p1.x, self.p2.x) and
min(self.p1.y, self.p2.y) <= p.y <= max(self.p1.y, self.p2.y))
时间复杂度分析
| 点到直线距离 | ||
| 点到线段距离 | ||
| 点在直线判断 | ||
| 点在线段判断 |
应用场景
- 距离计算
- 位置判断
- 相对方向
- 几何构造
- 碰撞检测
注意事项
- 浮点数精度
- 除零判断
- 边界情况
- 平行处理
- 数值稳定性
常见变形
- 点到折线距离
class Solution {
public:
// 计算点到折线的最短距离
double distanceToPolyline(const Point& p, const vector<Point>& points) {
double minDist = DBL_MAX;
for (int i = 0; i < points.size() - 1; i++) {
Line segment(points[i], points[i + 1]);
minDist = min(minDist, segment.distanceToSegment(p));
}
return minDist;
}
// 判断点是否在折线上
bool onPolyline(const Point& p, const vector<Point>& points) {
for (int i = 0; i < points.size() - 1; i++) {
Line segment(points[i], points[i + 1]);
if (segment.onSegment(p)) return true;
}
return false;
}
};
class Solution {
// 计算点到折线的最短距离
public double distanceToPolyline(Point p, Point[] points) {
double minDist = Double.MAX_VALUE;
for (int i = 0; i < points.length - 1; i++) {
Line segment = new Line(points[i], points[i + 1]);
minDist = Math.min(minDist, segment.distanceToSegment(p));
}
return minDist;
}
// 判断点是否在折线上
public boolean onPolyline(Point p, Point[] points) {
for (int i = 0; i < points.length - 1; i++) {
Line segment = new Line(points[i], points[i + 1]);
if (segment.onSegment(p)) return true;
}
return false;
}
}
class Solution:
# 计算点到折线的最短距离
def distance_to_polyline(self, p: Point, points: List[Point]) -> float:
min_dist = float('inf')
for i in range(len(points) - 1):
segment = Line(points[i], points[i + 1])
min_dist = min(min_dist, segment.distance_to_segment(p))
return min_dist
# 判断点是否在折线上
def on_polyline(self, p: Point, points: List[Point]) -> bool:
return any(Line(points[i], points[i + 1]).on_segment(p)
for i in range(len(points) - 1))
- 点到直线投影
class Solution {
public:
// 计算点在直线上的投影点
Point projectToLine(const Point& p, const Line& line) {
Point dir = line.p2 - line.p1;
double t = dir.dot(p - line.p1) / dir.dot(dir);
return line.p1 + Point(dir.x * t, dir.y * t);
}
// 计算点关于直线的对称点
Point reflectPoint(const Point& p, const Line& line) {
Point proj = projectToLine(p, line);
return proj * 2 - p;
}
};
class Solution {
// 计算点在直线上的投影点
public Point projectToLine(Point p, Line line) {
Point dir = line.p2.subtract(line.p1);
double t = dir.dot(p.subtract(line.p1)) / dir.dot(dir);
return line.p1.add(new Point(dir.x * t, dir.y * t));
}
// 计算点关于直线的对称点
public Point reflectPoint(Point p, Line line) {
Point proj = projectToLine(p, line);
return new Point(
2 * proj.x - p.x,
2 * proj.y - p.y
);
}
}
class Solution:
# 计算点在直线上的投影点
def project_to_line(self, p: Point, line: Line) -> Point:
dir = line.p2 - line.p1
t = dir.dot(p - line.p1) / dir.dot(dir)
return line.p1 + Point(dir.x * t, dir.y * t)
# 计算点关于直线的对称点
def reflect_point(self, p: Point, line: Line) -> Point:
proj = self.project_to_line(p, line)
return Point(2 * proj.x - p.x, 2 * proj.y - p.y)
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
