多边形
多边形
问题描述
多边形处理平面上由多条线段围成的封闭图形，包括面积计算、点位置判断等。常用于区域判断和几何构造问题。
基本操作
算法思想
- 使用点序列表示多边形
- 基于向量和叉积计算
- 适用于面积和位置判断
- 时间复杂度
代码实现
class Polygon {
public:
vector<Point> points; // 按顺时针或逆时针顺序存储顶点
Polygon(vector<Point> p = {}) : points(p) {}
// 计算多边形面积
double area() const {
double result = 0;
int n = points.size();
for (int i = 0; i < n; i++) {
result += points[i].cross(points[(i + 1) % n]);
}
return abs(result) / 2;
}
// 判断点是否在多边形内部
// 返回值: -1外部 0边上 1内部
int containsPoint(const Point& p) const {
int n = points.size();
bool on_edge = false;
int wn = 0; // winding number
for (int i = 0; i < n; i++) {
const Point& p1 = points[i];
const Point& p2 = points[(i + 1) % n];
// 检查点是否在边上
if (Line(p1, p2).onSegment(p)) {
return 0;
}
// 检查射线相交
if (p1.y <= p.y) {
if (p2.y > p.y &&
(p2 - p1).cross(p - p1) > 0) {
wn++;
}
} else {
if (p2.y <= p.y &&
(p2 - p1).cross(p - p1) < 0) {
wn--;
}
}
}
return wn != 0 ? 1 : -1;
}
// 计算多边形周长
double perimeter() const {
double result = 0;
int n = points.size();
for (int i = 0; i < n; i++) {
result += points[i].distance(points[(i + 1) % n]);
}
return result;
}
};
class Polygon {
List<Point> points; // 按顺时针或逆时针顺序存储顶点
Polygon(List<Point> p) {
this.points = p;
}
// 计算多边形面积
double area() {
double result = 0;
int n = points.size();
for (int i = 0; i < n; i++) {
result += points.get(i).cross(points.get((i + 1) % n));
}
return Math.abs(result) / 2;
}
// 判断点是否在多边形内部
// 返回值: -1外部 0边上 1内部
int containsPoint(Point p) {
int n = points.size();
boolean onEdge = false;
int wn = 0; // winding number
for (int i = 0; i < n; i++) {
Point p1 = points.get(i);
Point p2 = points.get((i + 1) % n);
// 检查点是否在边上
if (new Line(p1, p2).onSegment(p)) {
return 0;
}
// 检查射线相交
if (p1.y <= p.y) {
if (p2.y > p.y &&
p2.subtract(p1).cross(p.subtract(p1)) > 0) {
wn++;
}
} else {
if (p2.y <= p.y &&
p2.subtract(p1).cross(p.subtract(p1)) < 0) {
wn--;
}
}
}
return wn != 0 ? 1 : -1;
}
// 计算多边形周长
double perimeter() {
double result = 0;
int n = points.size();
for (int i = 0; i < n; i++) {
result += points.get(i).distance(points.get((i + 1) % n));
}
return result;
}
}
class Polygon:
def __init__(self, points: List[Point] = None):
self.points = points or [] # 按顺时针或逆时针顺序存储顶点
# 计算多边形面积
def area(self) -> float:
result = 0
n = len(self.points)
for i in range(n):
result += self.points[i].cross(self.points[(i + 1) % n])
return abs(result) / 2
# 判断点是否在多边形内部
# 返回值: -1外部 0边上 1内部
def contains_point(self, p: Point) -> int:
n = len(self.points)
on_edge = False
wn = 0 # winding number
for i in range(n):
p1 = self.points[i]
p2 = self.points[(i + 1) % n]
# 检查点是否在边上
if Line(p1, p2).on_segment(p):
return 0
# 检查射线相交
if p1.y <= p.y:
if p2.y > p.y and (p2 - p1).cross(p - p1) > 0:
wn += 1
else:
if p2.y <= p.y and (p2 - p1).cross(p - p1) < 0:
wn -= 1
return 1 if wn != 0 else -1
# 计算多边形周长
def perimeter(self) -> float:
result = 0
n = len(self.points)
for i in range(n):
result += self.points[i].distance(self.points[(i + 1) % n])
return result
时间复杂度分析
| 面积计算 | ||
| 点位置判断 | ||
| 周长计算 | ||
| 凸包构造 |
应用场景
- 区域判断
- 面积计算
- 几何构造
- 凸包问题
- 碰撞检测
注意事项
- 点的顺序
- 边界情况
- 凸凹性质
- 精度问题
- 特殊形状
常见变形
- 多边形凸包
class Solution {
public:
// Graham扫描法求凸包
vector<Point> convexHull(vector<Point>& points) {
int n = points.size();
if (n <= 3) return points;
// 找到最下方的点
int bottom = 0;
for (int i = 1; i < n; i++) {
if (points[i].y < points[bottom].y ||
(points[i].y == points[bottom].y &&
points[i].x < points[bottom].x)) {
bottom = i;
}
}
swap(points[0], points[bottom]);
// 按极角排序
Point p0 = points[0];
sort(points.begin() + 1, points.end(),
[&p0](const Point& a, const Point& b) {
double cross = (a - p0).cross(b - p0);
if (abs(cross) < EPS) {
return p0.distance(a) < p0.distance(b);
}
return cross > 0;
});
// Graham扫描
vector<Point> hull = {points[0], points[1]};
for (int i = 2; i < n; i++) {
while (hull.size() >= 2 &&
(hull.back() - hull[hull.size()-2])
.cross(points[i] - hull.back()) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
return hull;
}
};
class Solution {
// Graham扫描法求凸包
public List<Point> convexHull(List<Point> points) {
int n = points.size();
if (n <= 3) return points;
// 找到最下方的点
int bottom = 0;
for (int i = 1; i < n; i++) {
if (points.get(i).y < points.get(bottom).y ||
(points.get(i).y == points.get(bottom).y &&
points.get(i).x < points.get(bottom).x)) {
bottom = i;
}
}
Collections.swap(points, 0, bottom);
// 按极角排序
final Point p0 = points.get(0);
points.subList(1, n).sort((a, b) -> {
double cross = a.subtract(p0).cross(b.subtract(p0));
if (Math.abs(cross) < EPS) {
return Double.compare(p0.distance(a), p0.distance(b));
}
return cross > 0 ? -1 : 1;
});
// Graham扫描
List<Point> hull = new ArrayList<>();
hull.add(points.get(0));
hull.add(points.get(1));
for (int i = 2; i < n; i++) {
while (hull.size() >= 2 &&
hull.get(hull.size()-1).subtract(
hull.get(hull.size()-2))
.cross(points.get(i).subtract(
hull.get(hull.size()-1))) <= 0) {
hull.remove(hull.size()-1);
}
hull.add(points.get(i));
}
return hull;
}
}
class Solution:
# Graham扫描法求凸包
def convex_hull(self, points: List[Point]) -> List[Point]:
n = len(points)
if n <= 3:
return points
# 找到最下方的点
bottom = min(range(n),
key=lambda i: (points[i].y, points[i].x))
points[0], points[bottom] = points[bottom], points[0]
# 按极角排序
p0 = points[0]
points[1:] = sorted(
points[1:],
key=lambda p: (
-(p - p0).cross(Point(1, 0)),
p0.distance(p)
)
)
# Graham扫描
hull = [points[0], points[1]]
for i in range(2, n):
while len(hull) >= 2 and \
(hull[-1] - hull[-2]).cross(
points[i] - hull[-1]) <= 0:
hull.pop()
hull.append(points[i])
return hull
- 多边形切割
class Solution {
public:
// 直线切割多边形
pair<Polygon, Polygon> cutPolygon(const Polygon& poly,
const Line& line) {
vector<Point> left, right;
int n = poly.points.size();
for (int i = 0; i < n; i++) {
Point cur = poly.points[i];
Point next = poly.points[(i + 1) % n];
// 当前点的位置
double cross1 = (line.p2 - line.p1).cross(cur - line.p1);
if (abs(cross1) < EPS) {
// 点在直线上
left.push_back(cur);
right.push_back(cur);
} else if (cross1 > 0) {
// 点在直线左侧
left.push_back(cur);
} else {
// 点在直线右侧
right.push_back(cur);
}
// 检查边是否与直线相交
double cross2 = (line.p2 - line.p1).cross(next - line.p1);
if (cross1 * cross2 < 0) {
// 边与直线相交
Point intersection = lineIntersection(
Line(cur, next), line
);
left.push_back(intersection);
right.push_back(intersection);
}
}
return {Polygon(left), Polygon(right)};
}
};
class Solution {
// 直线切割多边形
public Pair<Polygon, Polygon> cutPolygon(Polygon poly, Line line) {
List<Point> left = new ArrayList<>();
List<Point> right = new ArrayList<>();
int n = poly.points.size();
for (int i = 0; i < n; i++) {
Point cur = poly.points.get(i);
Point next = poly.points.get((i + 1) % n);
// 当前点的位置
double cross1 = line.p2.subtract(line.p1)
.cross(cur.subtract(line.p1));
if (Math.abs(cross1) < EPS) {
// 点在直线上
left.add(cur);
right.add(cur);
} else if (cross1 > 0) {
// 点在直线左侧
left.add(cur);
} else {
// 点在直线右侧
right.add(cur);
}
// 检查边是否与直线相交
double cross2 = line.p2.subtract(line.p1)
.cross(next.subtract(line.p1));
if (cross1 * cross2 < 0) {
// 边与直线相交
Point intersection = lineIntersection(
new Line(cur, next), line
);
left.add(intersection);
right.add(intersection);
}
}
return new Pair<>(new Polygon(left), new Polygon(right));
}
}
class Solution:
# 直线切割多边形
def cut_polygon(self, poly: Polygon, line: Line) -> Tuple[Polygon, Polygon]:
left, right = [], []
n = len(poly.points)
for i in range(n):
cur = poly.points[i]
next = poly.points[(i + 1) % n]
# 当前点的位置
cross1 = (line.p2 - line.p1).cross(cur - line.p1)
if abs(cross1) < self.EPS:
# 点在直线上
left.append(cur)
right.append(cur)
elif cross1 > 0:
# 点在直线左侧
left.append(cur)
else:
# 点在直线右侧
right.append(cur)
# 检查边是否与直线相交
cross2 = (line.p2 - line.p1).cross(next - line.p1)
if cross1 * cross2 < 0:
# 边与直线相交
intersection = self.line_intersection(
Line(cur, next), line
)
left.append(intersection)
right.append(intersection)
return Polygon(left), Polygon(right)
