計算幾何相關模板（更新中……）
最近在學計算幾何，邊學，邊整理模板，有錯的話請大家指出！
1
//計算幾何模板 ~ alpc02
2const double PRECISION = 1e-8;
3
struct Point 
{
4
double x, y;
5
};
6int dblcmp(double d) {
7 return (fabs(d) < PRECISION) ? 0:(d>0 ? 1:-1);
8} //三叉口函數，避免精度誤差
9double length(double x, double y) {
10 return sqrt(x*x + y*y);
11} //向量長度
12double dotdet(double x1, double y1, double x2, double y2) {
13 return x1*x2 + y1*y2;
14} //點積
15double det(double x1, double y1, double x2, double y2) {
16 return x1*y2 - x2*y1;
17} //叉積
18int cross(const Point &a, const Point &c, const Point &d) {
19 return dblcmp( det(a.x-c.x, a.y-c.y, d.x-c.x, d.y-c.y) );
20} //右手螺旋定則，1——a在cd右側，-1——a在cd左側，0——三點共線
21bool between(const Point &a, const Point &c, const Point &d) {
22 return dblcmp( dotdet(c.x-a.x, c.y-a.y, d.x-a.x, d.y-a.y) ) != 1;
23} //在cross(a,c,d)==0的基礎上，可判斷點a是否在cd內部
24int segIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
25 int a_cd = cross(a,c,d);
26 if(a_cd == 0 && between(a,c,d)) return 2;
27 int b_cd = cross(b,c,d);
28 if(b_cd == 0 && between(b,c,d)) return 2;
29 int c_ab = cross(c,a,b);
30 if(c_ab == 0 && between(c,a,b)) return 2;
31 int d_ab = cross(d,a,b);
32 if(d_ab == 0 && between(d,a,b)) return 2;
33 if ((a_cd ^ b_cd) == -2 && (c_ab ^ d_ab) == -2)
34 return 1;
35 return 0;
36} //兩線段相交情況：0——不相交，1——規范相交，2——不規范相交（交于端點或重合）
37void intersectPoint(const Point &a, const Point &b, const Point &c, const Point &d, Point &e) {
38 double sc, sd;
39 sc = fabs( det(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y) );
40 sd = fabs( det(b.x-a.x, b.y-a.y, d.x-a.x, d.y-a.y) );
41 e.x = (sc * d.x + sd * c.x) / (sc + sd);
42 e.y = (sc * d.y + sd * c.y) / (sc + sd);
43} //兩線段規范相交時，求交點坐標
44int linesegIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
45 int c_ab = cross(c,a,b);
46 if(c_ab == 0) return 2;
47 int d_ab = cross(d,a,b);
48 if(d_ab == 0) return 2;
49 if(c_ab ^ d_ab == -2)
50 return 1;
51 return 0;
52} //直線ab和線段cd相交情況：0——不相交，1——規范相交，2——不規范相交（交于端點或重合）
53int lineIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
54 if(dblcmp(det(b.x-a.x, b.y-a.y, d.x-c.x, d.y-c.y)) != 0)
55 return 1;
56 if(cross(a,c,d) == 0)
57 return 2;
58 return 0;
59} //兩直線相交情況：0——平行，1——規范相交，2——不規范相交（重合）
60
posted on 2007-08-22 18:39
LSM 閱讀(1930)
評論(6) 編輯 收藏 引用 所屬分類:
計算幾何