內積與外積

電腦做運算時，會有浮點數誤差的問題。為避免浮點數誤差的問題，用電腦計算幾何問題時，會採用不同於一般數學運算時所用的公式和定理。

內積（inner product、dot product）、外積（outer product、cross product）這兩個運算只用了加法和乘法，而不包括除法，故能有效的避免除法所產生的浮點數誤差。內積與外積有許多很有用的特性。大部分的幾何問題，都可以用內積與外積來計算答案。

此處僅作簡單介紹，以下都是用二維空間當作範例。

資料結構

內積與外積是向量運算，所以得設計一個向量的資料結構。

struct Vector {int x, y;}; // 二維向量的資料結構 // 內積運算 int dot(Vector& v1, Vector& v2) { // 沒有除法，儘量避免誤差。 return v1.x * v2.x + v1.y * v2.y; } // 外積運算，回傳純量（除去方向） int cross(Vector& v1, Vector& v2) { // 沒有除法，儘量避免誤差。 return v1.x * v2.y - v1.y * v2.x; }

向量資料結構擁有一個座標，並擁有一支內積函式與一支外積函式。

兩個向量做內積的結果是一個純量。兩個向量做外積的結果為一個向量，然而我們通常只會用到純量部份，所以讓外積函式的回傳值為純量。

內積、外積跟長度的關係

內積後取絕對值，求得的是投影量，再除以投影標的的單位向量，則得到投影長度。

外積後取絕對值，求得的是平行四邊形的面積量，再除以底的單位向量，則得到高。

struct Point {double x, y;}; // 點的資料結構 typedef Point Vector; // 向量的資料結構，和點一樣 // 向量的長度 double length(Vector& v) { return sqrt(v1.x * v1.x + v2.y * v2.y); // return sqrt(dot(v, v)); } void print_d1_and_d2() { Point p, p1, p2; Vector v1 = p1 - p, v2 = p2 - p; cout << "d1:" << fabs(dot(v1, v2)) / length(v1); cout << "d2:" << fabs(cross(v1, v2)) / length(v1); }

內積、外積跟角度的關係

void print_θ() { Point p, p1, p2; Vector v1 = p1 - p, v2 = p2 - p; double l1 = length(v1), l2 = length(v2); cout << "cos(θ):" << dot(v1, v2) / l1 / l2; cout << "sin(θ):" << cross(v1, v2) / l1 / l2; cout << "θ:" << acos(dot(v1, v2) / l1 / l2); // [0, π] cout << "θ:" << asin(cross(v1, v2) / l1 / l2); // [-π/2, π/2] }

注意到acos與asin的回傳值，回傳的結果是弳度量（radian）而非度度量（grade），而且回傳值的範圍也不同。一般都以內積與acos求得介於0˚到180˚之間的夾角大小。

內積與向量夾角

利用內積的性質，可以粗略判斷夾角大小：內積大於0時，兩向量夾角小於90˚；等於0時，夾角等於90˚；小於零時，夾角大於90˚且小於180˚。

// 向量oa與向量ob進行內積。可以判斷∠aob之大小。 double dot(Point& o, Point& a, Point& b) { return (a.x-o.x) * (b.x-o.x) - (a.y-o.y) * (b.y-o.y); }

外積與向量旋轉

外積大於0時，兩向量前後順序為逆時針順序（在180˚之內）；等於0時，兩向量平行，也就是指夾角等於0˚或180˚；小於0時，兩向量前後順序為順時針順序（在180˚之內）。

// 向量oa與向量ob進行外積，可以判斷oa到ob旋轉的方向。 double cross(Point& o, Point& a, Point& b) { return (a.x-o.x) * (b.y-o.y) - (a.y-o.y) * (b.x-o.x); }

舉例來說，要判斷多邊形凹凸，就沿著多邊形外圍繞一圈，看看每一條邊是不是折向同方向即可。

點到原點距離

以下簡單介紹二維座標平面計算距離的方式。

double distance(Point& p) { return sqrt(p.x * p.x + p.y * p.y); } // 也可以運用pow來計算平方。但沒有多大好處。 double distance(Point& p) { return sqrt(pow(p.x, 2) + pow(p.y, 2)); } // 也可以運用dot來計算距離。但沒有多大好處。 double distance(Point& p) { return sqrt(dot(p, p)); }

開根號相當耗費時間。有時候做一些幾何計算時，會將數學式子簡化到不必開根號，以節省計算時間。因此，設計不開根號的程式碼，有時候也是會有用途的。

// 長度的平方倍，沒有開根號。 double distance2(Point& p) { return p.x * p.x + p.y * p.y; }

點到點距離

畢氏定理、勾股定理。

double distance(Point& p1, Point& p2) { return sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)); } double distance(Point& p1, Point& p2) { return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2)); } // 重複利用之前的程式碼 // 好處是程式碼結構較穩定、可讀性高 // 壞處是程式執行時要多呼叫一次函式，各有利弊 double distance(Point& p1, Point& p2) { return distance(p2 - p1); }

點到線距離

用數學計算時常會用ax+by=c來表示直線，但是在電腦中通常會直接以相異兩點表示直線，而不會去計算abc。這種情況下可以運用外積來計算點到線距離。

外積可求出v1 v2組成的平行四邊形面積，然後除以v2的長度，便是垂直距離。外積可能會有負值，請記得取絕對值，才不會得到負的距離。

struct Line {Point p1, p2;}; // 線的資料結構，注意p1和p2不能相等！ double distance(Point& p, Line& l) { Vector v1 = p - p1, v2 = p2 - p1; return fabs(cross(v1, v2)) / length(v2); // 面積除以底得高 }

點到線段距離

點到線段的最短距離，有時候是點到線上的垂直距離，有時候卻是點到線段端點的距離。

由圖片可觀察到，點到線段的距離，和三點共線、點在線上這些因素無關，所以這裡將空間劃分為垂直距離區和端點距離區兩塊，用內積進行判斷。這只是一種劃分方式，各位也可以自行發明適合的劃分方式。

struct Line {Point p1, p2;}; // 線的資料結構，注意p1和p2不能相等！ typedef Line Segment; // 線段的資料結構，注意p1和p2不能相等！ double distance(Point& p, Segment& s) { // 建立向量求內積，以判斷點在哪一區。 Vector p1p = p - s.p1, p1p2 = s.p2 - s.p1; Vector p2p = p - s.p2, p2p1 = s.p1 - s.p2; // 用大於等於零也可以 if (dot(p1p, p1p2) > 0 && dot(p2p, p2p1) > 0) // 垂直距離區 return distance(p, (Line)s); // 點到線距離 else // 端點距離區 return min(distance(p, s.p1), distance(p, s.p2)); // 點到點距離 } // 分成三個區域更清楚 double distance(Point& p, Segment& s) { // 建立向量求內積，以判斷點在哪一區 Vector p1p = p - s.p1, p1p2 = s.p2 - s.p1; Vector p2p = p - s.p2, p2p1 = s.p1 - s.p2; double d1 = dot(p1p, p1p2), d2 = dot(p2p, p2p1); if (d1 <= 0) // p在p1外側，端點距離區 // return distance(p, p1); return distance(p1p); else if (d2 <= 0) // p在p2外側，端點距離區 // return distance(p, p2); return distance(p2p); else // 垂直距離區 // return distance(p, (Line)s); return fabs(cross(p1p, p1p2)) / length(p1p2); } // 向量oa與向量ob進行外積 double cross(Point& o, Point& a, Point& b) { return (a.x-o.x) * (b.y-o.y) - (a.y-o.y) * (b.x-o.x); } // 向量oa與向量ob進行內積 double dot(Point& o, Point& a, Point& b) { return (a.x-o.x) * (b.x-o.x) - (a.y-o.y) * (b.y-o.y); } // 懶人寫法，直接套用修改過的外積與內積函式，不必相減求向量。 double distance(Point& p, Segment& s) { Point& p1 = s.p1; Point& p2 = s.p2; // 用大於等於零也可以。 if (dot(p1, p2, p) > 0 && dot(p2, p1, p) > 0) // 垂直距離區：點到線距離，面積除以底得高。 return fabs(cross(p1, p2, p)) / distance(p1, p2); else // 端點距離區：點到點距離。 return min(distance(p, p1), distance(p, p2)); }

線段到線距離

判斷線段的兩個端點是不是在線的同側。如果在同側則計算點到線距離；如果在不同側或者有任一點在線上，則距離為零。用外積判斷是否同側。

double distance(Segment& s, Line& l) { // 計算外積，根據正負號來判斷同側。 Vector v = l.p2 - l.p1; Vector v1 = s.p1 - l.p1, v2 = s.p2 - l.p1; double c1 = cross(v, v1), c2 = cross(v, v2); // 由於外積結果通常數值很大， // 故不用 c1*c2 > 0 來判斷同側，避免溢位。 if (c1 > 0 && c2 > 0 || c1 < 0 && c2 < 0) // 同側，且不在線上 // return min(distance(s.p1, l), // distance(s.p2, l)); // 點到線距離 return min(fabs(c1), fabs(c2)) / length(v); else // 不同側，或有一點在線上 return 0; } // 懶人寫法，直接套用修改過的外積與內積函式，不必相減求向量。 double distance(Segment& s, Line& l) { double c1 = cross(l.p1, l.p2, s.p1); double c2 = cross(l.p1, l.p2, s.p2); if (c1 * c2 > 0) // 同側，且不在線上 return min(fabs(c1), fabs(c2)) / distance(l.p1, l.p2); else // 不同側，或有一點在線上 return 0; }

線段到線段距離

這個問題似乎沒有更簡單的方式：如果線段有相交，則距離為零；如果不相交，則窮舉所有的端點到線段距離。點到線段的距離已經在先前的段落提過了，現在剩下線段相交尚待解決。

線段相交，也就是一條線段被另一條線段分為兩邊。所以我們只要檢查線段的兩頭，是不是位於另一條線段的兩側即可。

考慮線段平行的特殊情況。兩線段平行但不共線時，恰好可以直接用端點到線段的距離求出答案。至於兩線段共線時，不管兩線段有沒有相交，恰好也可以直接用端點到線段的距離求出答案。結論就是：只要兩線段平行或共線，便可以直接用端點到線段的距離求出答案，不用理會這兩條線段是否相交。

// 判斷線段相交 // 懶人寫法，直接套用修改過的外積與內積函式，不必相減求向量。 bool intersect(Segment& s1, Segment& s2) { Point& p1 = s1.p1; Point& p2 = s1.p2; Point& p3 = s2.p1; Point& p4 = s2.p2; // 兩線段平行或共線，恰好可以用端點到線段的距離求出答案， // 不用理會兩線段是否相交 if (cross(p2 - p1, p4 - p3) == 0) return false; // 看看線段的兩端點是否位於另一線段的兩側，如此才會相交 return cross(p1, p2, p3) * cross(p1, p2, p4) < 0 && cross(p3, p4, p1) * cross(p3, p4, p2) < 0 } double distance(Segment& s1, Segment& s2) { if (intersect(s1, s2)) // 線段不平行又相交時 return 0; else // 線段不平行又不相交時，或者兩線段平行或共線時 return min(distance(s1.p1, s2), distance(s1.p2, s2), distance(s2.p1, s1), distance(s2.p2, s1)); // 點到線段距離 }

各位可以整合「線段相交」與「點到線段距離」的程式碼，避免重複計算相同的向量，以節省時間。

線段到線段距離

線段相交，可以想像成是兩條交錯的四邊形對角線。換句話說，就是將線段的端點安排成四邊形的頂點，讓四邊形的對角線成為原來的兩條線段。如此一來，只要用一個四邊形，便可代表這兩條線段。

凸四邊形的對角線，都會相交；凹四邊形、交叉四邊形的對角線，不會相交──於是判斷線段相交，可以轉化做判斷凸四邊形。要判斷凸多邊形，只要順著多邊形的外圍繞一圈，看看是否一直往同側轉彎即可。判斷轉彎得利用外積：順時針轉彎外積得正值，逆時針得負值。

另外，外積等於零則表示線段的端點產生三點共線，分析各種情況後，發現此時可以直接用端點到線段的距離求出答案。

// 判斷線段相交，但不能處理端點共線的情況 bool intersect(Segment& s1, Segment& s2) { Vector v1 = s2.p1 - s1.p1, v2 = s1.p2 - s2.p1; Vector v3 = s2.p2 - s1.p2, v4 = s1.p1 - s2.p2; double c1 = cross(v1, v2), c2 = cross(v2, v3); double c3 = cross(v3, v4), c4 = cross(v4, v1); // 朝同一方向轉彎。都是順時針，或者都是逆時針。 return (c1 > 0 && c2 > 0 && c3 > 0 && c4 > 0) || (c1 < 0 && c2 < 0 && c3 < 0 && c4 < 0); } double distance(Segment& s1, Segment& s2) { if (intersect(s1, s2)) // 線段端點不共線，又相交時 return 0; else // 線段端點不共線，必不相交時 // 或者線端端點共線，可能相交或不相交時 return min(distance(s1.p1, s2), distance(s1.p2, s2), distance(s2.p1, s1), distance(s2.p2, s1)); // 點到線段距離 }

各位可以整合「線段相交」與「點到線段距離」的程式碼，避免重複計算相同的向量，以節省時間。

線到線距離

兩線相交距離為零，兩線平行距離為l1上任取一點到l2的距離。用外積判斷平行。

double distance(Line& l1, Line& l2) { Vector v1 = l1.p2 - l1.p1, v2 = l2.p2 - l2.p1; if (cross(v1, v2) == 0) // 平行、不相交 return distance(l1.p1, l2); // 點到線距離 else // 相交 return 0; }

UVa 152 10514 10709

Intersection

人類比電腦擅長判斷相交。人類可以追著線條移動，快速找到交點；人類也有很強的空間感，能夠迅速劃分地理位置，看一眼就能區隔出成堆的線段。但是電腦卻做不到這些，電腦只會算數字、分條件。

判斷相交原本是極容易的事情，主角改為電腦之後，卻變成極複雜的事情了。下面介紹二維座標平面上判斷相交的方式、計算交點的方式。

線段與點，判斷相交

三角不等式，開根號後又相加，會有點誤差，一般沒人用。

bool intersect(Segment& s, Point& p) { return distance(s.p1, p) + distance(s.p2, p) <= distance(s.p2, s.p1); }

比較妥當的方式，是先用外積判斷點與線段是否共線，再看看點是否在線段端點之間。

bool intersect(Segment& s, Point& p) { // 點與線段共線，而且點要在線段之間。 return cross(s.p1, s.p2, p) == 0 && dot(p, s.p1, s.p2) <= 0; }

兩共線線段，判斷相交

判斷四個端點，是否位在另一條線段上面。偵測點與線段相交，一共四次。

兩線段，判斷相交

http://www.csie.nctu.edu.tw/~sctsai/adprog/notes/CompGeo.ppt

看看線段的兩端點是否位於另一線段的兩側，如此才會相交。

bool intersect(Point& a1, Point& a2, Point& b1, Point& b2) { double c1 = cross(a1, a2, b1); double c2 = cross(a1, a2, b2); double c3 = cross(b1, b2, a1); double c4 = cross(b1, b2, a2); if (c1 * c2 < 0 && c3 * c4 < 0) return true; if (c1 == 0) return intersect(a1, a2, b1); if (c2 == 0) return intersect(a1, a2, b2); if (c3 == 0) return intersect(b1, b2, a1); if (c4 == 0) return intersect(b1, b2, a2); return false; }

兩共線線段交點

兩線段重疊，交點無限多；兩線段端點相接觸，交點恰為一點；兩線段不相交，交點不存在。

如果兩共線線段要有剛好一個交點，那麼交點就一定是線段端點。只要先檢查線段是否重疊，再檢查端點是否相同就可以了。

// 用於特殊情形。例如交點不存在，或者交點有無限多個。 Point INF = {1e9, 1e9}; // 判斷點是否在線段之中，並且不得在線段端點上。 bool inside(Point& a1, Point& a2, Point& p) { return cross(a1, a2, p) == 0 && dot(p, a1, a2) < 0; } Point intersection(Point& a1, Point& a2, Point& b1, Point& b2) { // 線段共線又重疊，交點無限多。 if (inside(a1, a2, b1) || inside(a1, a2, b2) inside(b1, b2, a1) || inside(b1, b2, a2)) return INF; // 線段共線但不重疊，若有交點，一定是線段端點。 if (a1 == b1) return a1; if (a1 == b2) return a1; if (a2 == b1) return a2; if (a2 == b2) return a2; // 線段共線但不相交。 return INF; } Point intersection(Point& a1, Point& a2, Point& b1, Point& b2) { // 確定交點後，剩下的線段端點必須位於交點的不同側。 if (a1 == b1 && dot(a1, a2, b2) <= 0) return a1; if (a1 == b2 && dot(a1, a2, b1) <= 0) return a1; if (a2 == b1 && dot(a2, a1, b2) <= 0) return a2; if (a2 == b2 && dot(a2, a1, b1) <= 0) return a2; // 交點無限多、交點不存在。 return INF; }

兩線交點

可參考：http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/，這是數學公式解，是用聯立多項式推導出來的。

Point intersection(Point& a1, Point& a2, Point& b1, Point& b2) { Point a = a2 - a1, b = b2 - b1, s = b1 - a1; // 兩線平行，交點不存在。 // 兩線重疊，交點無限多。 if (cross(a, b) == 0) return INF; // 計算交點 return a1 + a * cross(s, b) / cross(a, b); }

兩線段交點

Point intersection(Point& a1, Point& a2, Point& b1, Point& b2) { double c1 = cross(a1, a2, b1); double c2 = cross(a1, a2, b2); double c3 = cross(b1, b2, a1); double c4 = cross(b1, b2, a2); if (c1 * c2 < 0 && c3 * c4 < 0) return 兩線交點; if (c1 == 0 && c2 == 0) return 兩共線線段交點; // 兩線不平行、不共線、不交叉，有可能接觸於一點。 if (c1 == 0) return intersect(a1, a2, b1) ? b1 : INF; if (c2 == 0) return intersect(a1, a2, b2) ? b2 : INF; if (c3 == 0) return intersect(b1, b2, a1) ? a1 : INF; if (c4 == 0) return intersect(b1, b2, a2) ? a2 : INF; return INF; }

UVa 191 273 378 527 866 10902 10907

線段與點，判斷相交

還有一種方式是用座標大小關係判斷。

bool operator<=(cosnt Point& p1, cosnt Point& p2) { return p1.x <= p2.x && p1.y <= p2.y; } bool intersect(Segment& s, Point& p) { // 點與線段不共線，不可能相交。 if (cross(s.p2 - s.p1, p - s.p1) != 0) return false; // 判斷點是否在線段之間。 Point maxp = {max(s.p1.x, s.p2.x), max(s.p1.y, s.p2.y)}; Point minp = {min(s.p1.x, s.p2.x), min(s.p1.y, s.p2.y)}; return minp <= p && p <= maxp; }

更簡潔的方式，是判斷點是否在線段之外。如此就不必擔心線段的兩個端點誰大誰小了。

實作時要小心兩條線段恰好是水平線、垂直線的情況，也要小心線段斜率小於零的情況。

bool operator>(const Point& p1, const Point& p2) { // 若寫&&，則無法處理水平線、垂直線， // 況且也無法處理斜率小於零的線段。 return p1.x > p2.x || p1.y > p2.y; } bool operator<(const Point& p1, const Point& p2) { return p1.x < p2.x || p1.y < p2.y; } bool intersect(Segment& s, Point& p) { // 點與線段不共線，不可能相交。 if (cross(s.p2 - s.p1, p - s.p1) != 0) return false; // 在線段的延伸線上，但是不在線段內。 // 因為我們不知道s.p1與s.p2的大小關係， // 所以只好反過來求例外， // 而不是直接判斷點是否在線段之間。 if (p > s.p1 && p > s.p2) return false; if (p < s.p1 && p < s.p2) return false; return true; } // 只留下大於就好了。 bool operator>(const Point& p1, const Point& p2) { return p1.x > p2.x || p1.y > p2.y; } bool intersect(Segment& s, Point& p) { // 點與線段不共線，不可能相交。 if (cross(s.p2 - s.p1, p - s.p1) != 0) return false; // 在線段的延伸線上，但是不在線段內。 // 因為我們不知道s.p1與s.p2的大小關係， // 所以只好反過來求例外， // 而不是直接判斷點是否在線段之間。 if (p > s.p1 && p > s.p2) return false; if (s.p1 > p && s.p2 > p) return false; return true; }

兩共線線段，判斷相交

判斷四個端點，是否位在另一條線段上面。偵測點與線段相交，一共四次。

bool operator<=(cosnt Point& p1, cosnt Point& p2) { return p1.x <= p2.x && p1.y <= p2.y; } // p1 p2 是第一條線段，p3 p4 是第二條線段。 bool intersect(Point& p1, Point& p2, Point& p3, Point& p4) { Point max12 = {max(p1.x, p2.x), max(p1.y, p2.y)}; Point min12 = {min(p1.x, p2.x), min(p1.y, p2.y)}; Point max34 = {max(p3.x, p4.x), max(p3.y, p4.y)}; Point min34 = {min(p3.x, p4.x), min(p3.y, p4.y)}; return (min12 <= p3) && (p3 <= max12) || (min12 <= p4) && (p4 <= max12) || (min34 <= p1) && (p1 <= max34) || (min34 <= p2) && (p2 <= max34); }

更簡潔的方式，是判斷兩條線段是否沒有相交。對一條線段而言，只要另一條線段的兩個端點都在相同外側，就是沒有相交。

實作時要小心兩條線段恰好是水平線、垂直線的情況。

bool operator>(const Point& p1, const Point& p2) { // 若寫&&，則無法處理水平線、垂直線， // 況且也無法處理斜率小於零的線段。 return p1.x > p2.x || p1.y > p2.y; } // p1與p2都都比s34高，或者都比s34低。 bool intersect(Point& p1, Point& p2, Point& p3, Point& p4) { return !(p1 > p3 && p2 > p3 && p1 > p4 && p2 > p4) && !(p3 > p1 && p3 > p2 && p4 > p1 && p4 > p2); }

兩線交點

這裡介紹一個利用外積來計算交點的方法，其實等同於數學公式解。請見下圖：

原則上，就是以p1為基準點，p34為平行四邊形的底，然後利用兩個平行四邊形的高的比例，便能求出p1到p2與p1到交點的距離比例。

平行四邊形的面積可用外積運算求出，所以這個方法相當方便。各位可依照下圖所列舉的各種情況（補上線段的延長線，使之為線），驗證此方法是有效的，並試著整理出例外情況。

實作程式碼時，要注意外積的順序，外積的順序不同會產生出正負號的差異。

Point intersection(Point& p1, Point& p2, Point& p3, Point& p4) { Point p12 = p2 - p1, p13 = p3 - p1, p34 = p4 - p3; double c1 = cross(p12, p34), c2 = cross(p13, p34); if (c1 == 0) if (c2 == 0) return INF; // 兩線重疊 else return INF; // 兩線平行但不重疊 else return p1 + (p12 * (c2 / c1)); }

兩線段交點

線段與線段的交點。跟上一段所述相同，只是要小心判斷兩個平行四邊形的高的比例是不是為負值、或者超過1，此即表示線段p34超出了線段p12的範圍，不會相交。至於範圍是指p1和p2兩點，以平行p34的方向所畫出的邊界線作為範圍，如下圖所示：

另外，除了以p1為基準點，還要再以p3為基準點再算一遍，才能確定兩線段到底有沒有相交。

至於兩共線線段求交點的情況，前面章節已提過，這裡就不予討論。大家可以自己揣摩看看。

小細節就略過，程式碼如下：

Point intersection(Point& p1, Point& p2, Point& p3, Point& p4) { Point p12 = p2 - p1, p13 = p3 - p1, p34 = p4 - p3; double c1 = cross(p12, p34), c2 = cross(p13, p34); Point p31 = p1 - p3; double c3 = cross(p34, p12), c4 = cross(p31, p12); if (c1 < 0) c1 = -c1, c2 = -c2; // 調整一下正負號，方便判斷 if (c3 < 0) c3 = -c3, c4 = -c4; if (c1 == 0) if (c2 == 0) return INF; // 兩線段共線，此處省略之 else return INF; // 兩線段平行但不共線 else if (c2 >= 0 && c2 <= c1 && c4 >= 0 && c4 <= c3) return p1 + (p12 * (c2 / c1)); else return INF; // 不平行、不相交 }

由於p13與p31只差一負號，故可以用p13代替p31。另外c1與c3也只差一負號，故可以用c1代替c3。於是程式碼可再精簡。

Point intersection(Point& p1, Point& p2, Point& p3, Point& p4) { Point p12 = p2 - p1, p13 = p3 - p1, p34 = p4 - p3; double c1 = cross(p12, p34), c2 = cross(p13, p34); double c4 = cross(p13, p12); // c3用c1取代，c4方向顛倒 if (c1 < 0) c1 = -c1, c2 = -c2, c4 = -c4; if (c1 != 0 && c2 >= 0 && c2 <= c1 && c4 >= 0 && c4 <= c1) return p1 + (p12 * (c2 / c1)); else return INF; // 兩線段共線的部分，此處省略之 }