三维计算几何模板整理(二)
int i = 0; i < 3; i++) {
if(TriSegIntersection(T1[0], T1[1], T1[2], T2[i], T2[(i+1)%3], P)) return true;
if(TriSegIntersection(T2[0], T2[1], T2[2], T1[i], T1[(i+1)%3], P)) return true;
}
return false;
}
//空间两直线上最近点对 返回最近距离 点对保存在ans1 ans2中
double SegSegDistance(Point3 a1, Point3 b1, Point3 a2, Point b2)
{
Vector v1 = (a1-b1), v2 = (a2-b2);
Vector N = Cross(v1, v2);
Vector ab = (a1-a2);
double ans = Dot(N, ab) / Length(N);
Point p1 = a1, p2 = a2;
Vector d1 = b1-a1, d2 = b2-a2;
double t1, t2;
t1 = Dot((Cross(p2-p1, d2)), Cross(d1, d2));
t2 = Dot((Cross(p2-p1, d1)), Cross(d1, d2));
double dd = Length((Cross(d1, d2)));
t1 /= dd*dd;
t2 /= dd*dd;
ans1 = (a1 + (b1-a1)*t1);
ans2 = (a2 + (b2-a2)*t2);
return fabs(ans);
}
// 判断P是否在三角形A, B, C中，并且到三条边的距离都至少为mindist。保证P, A, B, C共面
bool InsideWithMinDistance(const Point3& P, const Point3& A, const Point3& B, const Point3& C, double mindist) {
if(!PointInTri(P, A, B, C)) return false;
if(DistanceToLine(P, A, B) < mindist) return false;
if(DistanceToLine(P, B, C) < mindist) return false;
if(DistanceToLine(P, C, A) < mindist) return false;
return true;
}
// 判断P是否在凸四边形ABCD（顺时针或逆时针）中，并且到四条边的距离都至少为mindist。保证P, A, B, C, D共面
bool InsideWithMinDistance(const Point3& P, const Point3& A, const Point3& B, const Point3& C, const Point3& D, double mindist) {
if(!PointInTri(P, A, B, C)) return false;
if(!PointInTri(P, C, D, A)) return false;
if(DistanceToLine(P, A, B) < mindist) return false;
if(DistanceToLine(P, B, C) < mindist) return false;
if(DistanceToLine(P, C, D) < mindist) return false;
if(DistanceToLine(P, D, A) < mindist) return false;
return true;
}
/*************凸包相关问题*******************/
//加干扰
double rand01() { return rand() / (double)RAND_MAX; }
double randeps() { return (rand01() - 0.5) * eps; }
Point3 add_noise(const Point3& p) {
return Point3(p.x + randeps(), p.y + randeps(), p.z + randeps());
}
struct Face {
int v[3];
Face(int a, int b, int c) { v[0] = a; v[1] = b; v[2] = c; }
Vector3 Normal(const vector
& P) const {
return Cross(P[v[1]]-P[v[0]], P[v[2]]-P[v[0]]);
}
// f是否能看见P[i]
int CanSee(const vector& P, int i) const {
return Dot(P[i]-P[v[0]], Normal(P)) > 0;
}
};
// 增量法求三维凸包
// 注意：没有考虑各种特殊情况（如四点共面）。实践中，请在调用前对输入点进行微小扰动
vector CH3D(const vector& P) {
int n = P.size();
vector > vis(n);
for(int i = 0; i < n; i++) vis[i].resize(n);
vector cur;
cur.push_back(Face(0, 1, 2)); // 由于已经进行扰动，前三个点不共线
cur.push_back(Face(2, 1, 0));
for(int i = 3; i < n; i++) {
vector next;
// 计算每条边的“左面”的可见性
for(int j = 0; j < cur.size(); j++) {
Face& f = cur[j];
int res = f.CanSee(P, i);
if(!res) next.push_back(f);
for(int k = 0; k < 3; k++) vis[f.v[k]][f.v[(k+1)%3]] = res;
}
for(int j = 0; j < cur.size(); j++)
for(int k = 0; k < 3; k++) {
int a = cur[j].v[k], b = cur[j].v[(k+1)%3];
if(vis[a][b] != vis[b][a] && vis[a][b]) // (a,b)是分界线，左边对P[i]可见
next.push_back(Face(a, b, i));
}
cur = next;
}
return cur;
}
struct ConvexPolyhedron {
int n;
vector P, P2;
vector faces;
bool read() {
if(scanf("%d", &n) != 1) return false;
P.resize(n);
P2.resize(n);
for(int i = 0; i < n; i++) { P[i] = read_point3(); P2[i] = add_noise(P[i]); }
faces = CH3D(P2);
return true;
}
//三维凸包重心
Point3 centroid() {
Point3 C = P[0];
double totv = 0;
Point3 tot(0,0,0);
for(int i = 0; i < faces.size(); i++) {
Point3 p1 = P[faces[i].v[0]], p2 = P[faces[i].v[1]], p3 = P[faces[i].v[2]];
double v = -Volume6(p1, p2, p3, C);
totv += v;
tot = tot + Centroid(p1, p2, p3, C)*v;
}
return tot / totv;
}
//凸包重心到表面最近距离
double mindist(Point3 C) {
double ans = 1e30;
for(int i = 0; i < faces.size(); i++) {
Point3 p1 = P[faces[i].v[0]], p2 = P[faces[i].v[1]], p3 = P[faces[i].v[2]];
ans = min(ans, fabs(-Volume6(p1, p2, p3, C) / Area2(p1, p2, p3)));
}
return ans;
}
};