Hình học tính toán (Computational Geometry) là nhánh thuật toán xử lý các bài toán về điểm, đường thẳng, đa giác và các đối tượng hình học khác.
Cơ sở: Vector và tích có hướng
struct Point {
long long x, y;
Point(long long x=0, long long y=0): x(x), y(y) {}
Point operator-(const Point& p) const { return {x-p.x, y-p.y}; }
Point operator+(const Point& p) const { return {x+p.x, y+p.y}; }
};
// Tích có hướng (cross product) của vector OA và OB
// > 0: B nằm bên trái OA (ngược chiều kim đồng hồ)
// < 0: B nằm bên phải OA (cùng chiều kim đồng hồ)
// = 0: A, O, B thẳng hàng
long long cross(Point O, Point A, Point B) {
return (long long)(A.x-O.x)*(B.y-O.y) - (long long)(A.y-O.y)*(B.x-O.x);
}
// Tích vô hướng (dot product)
long long dot(Point A, Point B) { return A.x*B.x + A.y*B.y; }
// Khoảng cách bình phương (tránh sqrt)
long long dist2(Point A, Point B) {
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
Kiểm tra điểm nằm trong tam giác
bool point_in_triangle(Point P, Point A, Point B, Point C) {
long long d1 = cross(A, B, P);
long long d2 = cross(B, C, P);
long long d3 = cross(C, A, P);
bool has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
bool has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}
Giao điểm hai đoạn thẳng
// Kiểm tra hai đoạn AB và CD có giao nhau không
bool segments_intersect(Point A, Point B, Point C, Point D) {
long long d1 = cross(C, D, A);
long long d2 = cross(C, D, B);
long long d3 = cross(A, B, C);
long long d4 = cross(A, B, D);
if (((d1>0&&d2<0)||(d1<0&&d2>0)) && ((d3>0&&d4<0)||(d3<0&&d4>0)))
return true;
// Kiểm tra trường hợp thẳng hàng
auto on_segment = [](Point P, Point A, Point B) {
return min(A.x,B.x)<=P.x && P.x<=max(A.x,B.x)
&& min(A.y,B.y)<=P.y && P.y<=max(A.y,B.y);
};
if (d1==0 && on_segment(A,C,D)) return true;
if (d2==0 && on_segment(B,C,D)) return true;
if (d3==0 && on_segment(C,A,B)) return true;
if (d4==0 && on_segment(D,A,B)) return true;
return false;
}
Diện tích đa giác (Shoelace Formula)
long long polygon_area2(vector<Point>& pts) {
long long area = 0;
int n = pts.size();
for (int i = 0; i < n; i++) {
int j = (i+1) % n;
area += pts[i].x * pts[j].y;
area -= pts[j].x * pts[i].y;
}
return abs(area); // diện tích thực = area/2
}
Các trang con
- Convex Hull — Bao lồi của tập điểm,
- Sweep Line — Quét đường thẳng cho bài toán hình học
- Point in Polygon — Kiểm tra điểm trong đa giác
- Closest Pair — Cặp điểm gần nhất,
Child pages
- Closest Pair (Cặp điểm gần nhất)
- Convex Hull (Bao lồi)
- Point in Polygon (Điểm trong đa giác)
- Sweep Line (Quét đường thẳng)
Bình luận