图形学基础题汇总

#include<iostream>
struct Point
{
	double x, y;
};
// 是否在矩形内部
bool insideRectangle(Point p, Point rectMin, Point rectMax) {
	return p.x <= rectMax.x && p.x >= rectMin.x && p.y <= rectMax.y && p.y >= rectMin.y;
}
// 叉乘公式
double crossProduct(Point a, Point b, Point c) {
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
// 线段是否相交
bool isIntersecting(Point p1, Point p2, Point q1, Point q2) {
	double d1 = crossProduct(p1, p2, q1);
	double d2 = crossProduct(p1, p2, q2);
	double d3 = crossProduct(q1, q2, p1);
	double d4 = crossProduct(q1, q2, p2);
	return (d1 * d2 <= 0) && (d3 * d4 <= 0);
}

bool LineIntersectingRectangle(Point p1, Point p2, Point rectMin, Point rectMax) {
	if (insideRectangle(p1, rectMin, rectMax) || insideRectangle(p2, rectMin, rectMax)) return true;
	Point topLeft = { rectMin.x, rectMax.y };
	Point topRight = { rectMax.x, rectMax.y };
	Point bottomLeft = { rectMin.x, rectMin.y };
	Point bottomRight = { rectMax.x,rectMin.y };
	return isIntersecting(p1, p2, topLeft, topRight) ||
		isIntersecting(p1, p2, topLeft, bottomLeft) ||
		isIntersecting(p1, p2, bottomLeft, bottomRight) ||
		isIntersecting(p1, p2, bottomRight, topRight);
}

int main() {
	Point p1 = { 0, 0 };
	Point p2 = { 3, 2 };
	Point rectMin = { 2, 2 };
	Point rectMax = { 4,4 };
	if (LineIntersectingRectangle(p1, p2, rectMin, rectMax)) std::cout << "线段穿过矩形\n";
	else std::cout << "线段没有穿过矩形\n";
	return 0;
}

/*
	判断两个三角形是否相交
	1. 点在三角形内
	2. 两条边相交
*/
#include<iostream>
struct Point
{
	double x, y;
};

double crossProduct(Point a, Point b, Point c) {
	return (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
}
// 点是否在三角形内部
bool PointInTriangle(Point p, Point a, Point b, Point c) {
	double d1 = crossProduct(p, a, b);
	double d2 = crossProduct(p, b, c);
	double d3 = crossProduct(p, c, a);
	return (d1 > 0 && d2 > 0 && d3 > 0) || (d1 < 0 && d2 < 0 && d3 < 0);
}
// 两条线段是否相交
bool segmentIntersect(Point p1, Point p2, Point q1, Point q2) {
	double d1 = crossProduct(p1, p2, q1);
	double d2 = crossProduct(p1, p2, q2);
	double d3 = crossProduct(q1, q2, p1);
	double d4 = crossProduct(q1, q2, p2);
	return (d1 * d2 < 0) && (d3 * d4 < 0);
}

bool TriangleIntersect(Point a1, Point b1, Point c1, Point a2, Point b2, Point c2) {
	if (PointInTriangle(a1, a2, b2, c2) || PointInTriangle(b1, a2, b2, c2) || PointInTriangle(c1, a2, b2, c2))
		return true;
	if (PointInTriangle(a2, a1, b1, c1) || PointInTriangle(b2, a1, b1, c1) || PointInTriangle(c2, a1, b1, c1))
		return true;
	Point tr1[] = { a1, b1, c1 };
	Point tr2[] = { a2, b2, c2 };
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (segmentIntersect(tr1[i], tr1[(i + 1) % 3], tr2[j], tr2[(j + 1) % 3])) {
				return true;
			}
		}
	}
	return false;
}